1 2 2 4 3 4 4 6 5 16 6 6 7 9 8 36 9 36 10 9 11 13 12 81 13 82 14 81 15 14 16 18 17 169 18 217 19 193 20 196 21 21 22 25 23 324 24 499 25 611 26 488 27 441 28 31 29 34 30 625 31 1014 32 1602 33 1910 34 1087 35 961 36 46 37 46 38 1156 39 2141 40 3513 41 5904 42 5132 43 2305 44 2116 45 68 46 62 47 2116 48 4188 49 8327 50 14184 51 18055 52 13067 53 4932 54 4624 55 100 56 83 57 3844 58 8150 59 17568 60 38911 61 45520 62 52240 63 33937 64 10416 65 10000 66 147 67 111 68 6889 69 15670 70 36988 71 90670 72 140295 73 135686 74 156473 75 86899 76 21716 77 21609 78 216 79 148 80 12321 81 29517 82 76723 83 211626 84 349415 85 467686 86 417772 87 460171 88 218763 89 45333 90 46656 91 317 92 197 93 21904 94 55523 95 153865 96 485438 97 877101 98 1233127 99 1623957 100 1253238 101 1324209 102 551672 103 94798 104 100489 105 465 106 262 107 38809 108 103348 109 308777 110 1060958 111 2164569 112 3284096 113 4556171 114 5467589 115 3651096 116 3824481 117 1390836 118 198291 119 216225 120 682 121 348 122 68644 123 191593 124 608391 125 2325765 126 5025447 127 8655283 128 12881467 129 16290023 130 17779942 131 10647801 132 11017816 133 3491934 134 415803 135 465124 136 1000 137 462 138 121104 139 353916 140 1189918 141 4961769 142 11757247 143 21076355 144 36421182 145 48655983 146 56079282 147 57847658 148 30923564 149 31464850 150 8760137 151 874740 152 1000000 153 1466 154 613 155 213444 156 651316 157 2313136 158 10471731 159 26570861 160 52058229 161 93059536 162 147304457 163 175714664 164 193343270 165 186862280 166 88853464 167 89582619 168 21976254 169 1845166 170 2149156 171 2149 172 813 173 375769 174 1196664 175 4458599 176 21898109 177 59370361 178 123345376 179 242917481 180 394269475 181 567847595 182 633289287 183 662104533 184 594627012 185 254267485 186 254431356 187 55062713 188 3902324 189 4618201 190 3150 191 1078 192 660969 193 2193747 194 8562580 195 45173720 196 131185317 197 288255238 198 603940244 199 1086013840 200 1585504597 201 2184649657 202 2260218336 203 2231855068 204 1880223340 205 725590642 206 719347025 207 137841712 208 8273999 209 9922500 210 4617 211 1429 212 1162084 213 4017137 214 16354499 215 92638142 216 285043185 217 665907876 218 1474775916 219 2831401682 220 4589934595 221 6351729691 222 8317472940 223 7909990480 224 7477113335 225 5915390781 226 2060214105 227 2026808124 228 344913621 229 17581622 230 21316689 231 6767 232 1894 233 2042041 234 7347906 235 31118601 236 188237183 237 615447774 238 1506716940 239 3560878335 240 7221420937 241 12514951202 242 19287063332 243 25160147201 244 31000517564 245 27430596029 246 24933220927 247 18465652946 248 5827339605 249 5696170867 250 862466304 251 37429453 252 45792289 253 9918 254 2510 255 3587236 256 13429145 257 59018399 258 379950333 259 1313196034 260 3386544920 261 8379145101 262 18223380471 263 33225465436 264 54941384974 265 80023297510 266 97414879427 267 114414998273 268 94461585960 269 82481020796 270 57306451587 271 16437397037 272 15961932156 273 2155128256 274 79812519 275 98366724 276 14536 277 3326 278 6300100 279 24530862 280 111556847 281 762511989 282 2780365566 283 7505699199 284 19572461770 285 44604493157 286 87409857505 287 151488939070 288 238059851454 289 323826250864 290 373045289714 291 419100496742 292 321924134488 293 271267875359 294 177068551553 295 46220378910 296 44610315375 297 5382374565 298 170419522 299 211295296 300 21304 301 4407 302 11062276 303 44784850 304 210352934 305 1520880047 306 5844983027 307 16482389432 308 44982053999 309 108328922059 310 222008099824 311 414840698474 312 681060707141 313 1005050679531 314 1293727841483 315 1416917572986 316 1517789758909 317 1088342769271 318 888443096434 319 544446252694 320 129590864085 321 124409802922 322 13435295369 323 364296166 324 453860416 325 31223 326 5839 327 19421649 328 81739060 329 395641010 330 3019622080 331 12192162619 332 35903584588 333 102215310151 334 258316480119 335 559311099818 336 1091380259817 337 1940166820652 338 2978868599222 339 4186147184625 340 5119428070901 341 5316986435949 342 5449130090909 343 3657304955042 344 2895560952114 345 1666721759718 346 362487844504 347 346245984652 348 33519373349 349 779456642 350 974875729 351 45760 352 7736 353 34093921 354 149141623 355 742567333 356 5966608758 357 25292923072 358 77477997261 359 230168113921 360 607849823297 361 1381204793433 362 2846551701285 363 5284179517245 364 8818360996022 365 12834603243934 366 17263478355132 367 19983428899448 368 19765984560244 369 19436633298400 370 12208587576507 371 9395735566374 372 5084288683371 373 1011664530775 374 961805475293 375 83589288631 376 1669010171 377 2093977600 378 67065 379 10249 380 59845696 381 272067741 382 1391072247 383 11740776248 384 52147005064 385 166138926351 386 512495689738 387 1416160229243 388 3359381198251 389 7267699722401 390 14259213084041 391 24841294021177 392 39439742845417 393 54697602396408 394 70193217794109 395 77163329102680 396 72973473369690 397 68826327304196 398 40508405546484 399 30383065117851 400 15456590300469 401 2817477642474 402 2667346798257 403 208367881512 404 3575965948 405 4497714225 406 98289 407 13578 408 105042001 409 496250336 410 2601239676 411 23016781362 412 106956186914 413 353659351084 414 1132696909180 415 3256506845043 416 8084778688208 417 18235683911427 418 37622585591007 419 69285437236998 420 114796105350934 421 174354454607454 422 229603139246218 423 282204231198735 424 295528858428626 425 267349814438682 426 242119031246634 427 133747336362463 428 97918149920842 429 46839696098171 430 7832260039474 431 7386351612768 432 519216523680 433 7665561753 434 9660727521 435 144050 436 17988 437 184362084 438 905026713 439 4856734666 440 44958990760 441 218337678731 442 748199188342 443 2482216885391 444 7425659939014 445 19172204695402 446 45252821102930 447 97332457751449 448 188785842546128 449 330536453345497 450 524049798168960 451 758639551271774 452 952012927369698 453 1125021469640483 454 1121793545174351 455 972698613506709 456 847202639412082 457 439501746018126 458 314568519674780 459 141554423722101 460 21736552696703 461 20426324585865 462 1293368267324 463 16438759769 464 20750402500 465 211116 466 23830 467 323568144 468 1650411906 469 9054612019 470 87542343008 471 443614127427 472 1574147935893 473 5399694679351 474 16769075576000 475 45043716056648 476 110471128665203 477 248935137523049 478 503208498743321 479 929236477009868 480 1556494209845373 481 2353308940308585 482 3258043957471699 483 3910889232869159 484 4443811091438481 485 4223507009079385 486 3519283284184937 487 2949103245032830 488 1437788343745195 489 1007856440113462 490 426719664767500 491 60231685478438 492 56419328413427 493 3220837778821 494 35264212106 495 44569965456 496 309406 497 31569 498 567868900 499 3009485364 500 16858616412 501 169943518119 502 897718025186 503 3293273296238 504 11671045960809 505 37547192539493 506 104701577240801 507 266933875813416 508 625296037858164 509 1325618312011291 510 2549329161051902 511 4512268202500938 512 7204844308501887 513 10424143061388804 514 13853882403920672 515 15906613480103738 516 17405201170085549 517 15794987808930970 518 12664525402266670 519 10215672829160160 520 4685373156396059 521 3221118789967958 522 1283358859440802 523 166671744533184 524 155667720387865 525 8018654186674 526 75667862252 527 95732072836 528 453457 529 41821 530 996601761 531 5487423878 532 31350934975 533 328991800617 534 1809473187978 535 6857261646053 536 25059302858909 537 83460002378986 538 241043824341185 539 637568789582010 540 1553172011684976 541 3424418632035502 542 6910802424713706 543 12733017384829087 544 21528139307626777 545 32870079608035300 546 45697535228671792 547 58289791867243039 548 64103724599891642 549 67702691790830680 550 58687824891627144 551 45344510562348455 552 35237568331438027 553 15213891383445729 554 10270844526177555 555 3851668058016359 556 460641170050698 557 429086274606653 558 19958741222331 559 162397147690 560 205623250849 561 664574 562 55402 563 1748996041 564 10005351901 565 58235326887 566 635268320234 567 3634039613205 568 14211034156384 569 53507035009310 570 184099177389759 571 550488529048841 572 1506599533715934 573 3810229440484326 574 8739395721873929 575 18343725387761661 576 35497970235444990 577 62452275142605559 578 101175268407665715 579 148308802793434559 580 198142876801100831 581 242855304376049958 582 256391916851030611 583 261599933497352168 584 216724963112758552 585 161650478591368693 586 121071253189498598 587 49235661094835823 588 32682229524788365 589 11537983937897759 590 1271669829114784 591 1181706729392296 592 49667952942902 593 348591546717 594 441658601476 595 973981 596 73393 597 3069381604 598 18242346423 599 108063030380 600 1223707152023 601 7274014622283 602 29323698526380 603 113622513807253 604 403501254055556 605 1246440086205867 606 3529190422312916 607 9237286287700730 608 22011084242802143 609 48056615427699515 610 96763777933121596 611 178971446398667700 612 301539324633363968 613 470039857440029540 614 661454300187203274 615 850404169719426295 616 1003629680028064997 617 1018053600503297864 618 1004446717281718421 619 796050431703580572 620 573981514752045930 621 414447732679564767 622 158857841406160366 623 103802238102090795 624 34502823317178099 625 3507074638261228 626 3251873074663066 627 123578039115181 628 748362908204 629 948638988361 630 1427439 631 97226 632 5386532449 633 33259948278 634 200331422198 635 2351980784762 636 14513018430027 637 60267619586984 638 240052156439367 639 878812034710997 640 2802128294257554 641 8189237951984606 642 22184240908958381 643 54725201310487667 644 124162909779015552 645 260071232109467536 646 500803258164984371 647 887739032057392840 648 1438461218657559419 649 2157718483679441114 650 2918222802988855187 651 3619069039306903001 652 4115393448032546439 653 4014637986435065356 654 3835578861917535381 655 2909450130581246815 656 2030465438442017724 657 1414014446617735956 658 511140600119684169 659 329115446007363917 660 103013098458069028 661 9663165564314436 662 8942294039768291 663 307423937328512 664 1606767178315 665 2037582098721 666 2092014 667 128798 668 9452895076 669 60639484381 670 371050951206 671 4511080381307 672 28870980257132 673 123387256169338 674 504814784841670 675 1902776589540611 676 6255331303334170 677 18853318659016817 678 52729956209860903 679 134697860818088190 680 316332748911471557 681 688935021025394505 682 1380307820306258521 683 2548705628275866926 684 4348329953628654971 685 6777334774925061939 686 9794151303288404310 687 12758668510251476704 688 15277589130509411272 689 16750374554356487654 690 15736590110080649751 691 14572166612938600089 692 10583685771408623203 693 7158933818880826156 694 4809642790124436974 695 1640428521760873555 696 1041851869657132922 697 307118675227808818 698 26603260998945664 699 24574577685941284 700 764670003562388 701 3450083752061 702 4376522576196 703 3065996 704 170622 705 16588924804 706 110556272720 707 686687176348 708 8635283358809 709 57272072159866 710 251724284960270 711 1056806206221153 712 4097907231875792 713 13871937773965686 714 43071502301813898 715 124257817634644860 716 327857636276617847 717 797370435220099251 718 1797637134754701613 719 3747599329243789395 720 7199798451278650828 721 12803116304075130878 722 21027241364489543430 723 31559659226765968826 724 44040180111793492224 725 55302469140500379490 726 63998476682497496610 727 67733362624477669283 728 61342181967357778764 729 55096671227510191456 730 38336413791472303127 731 25164542824651204364 732 16312870578819317370 733 5252345289455423013 734 3293380496197325430 735 914421617375766888 736 73185634744303698 737 67495205883358568 738 1901769874280937 739 7408578497536 740 9400331472016 741 4493436 742 226027 743 29111866884 744 201561930830 745 1269833374769 746 16499802950855 747 113311703938167 748 511816296341897 749 2203276248881148 750 8779468803349151 751 30579862523606222 752 97682268174737567 753 290377087898498099 754 790587971550684574 755 1986029939653809825 756 4638008533582477770 757 10011398743932402260 758 20025466855632314368 759 37050721067576349116 760 63472177715863524575 761 100452498656721227112 762 145522999787870415199 763 196265287885455991421 764 237744016687486338152 765 266284577874328756653 766 272238424796189719144 767 237861637266244656645 768 207413449765961424927 769 138318741968543946032 770 88208384663128121423 771 55183369478072577778 772 16780837714100571446 773 10396874350971028619 774 2719329121235274984 775 201198350089044676 776 185282233376616800 777 4729290780263621 778 15909729200860 779 20190967086096 780 6585451 781 299423 782 51088204729 783 367476861050 784 2346503848073 785 31472436442614 786 223629902375777 787 1037337062306810 788 4575461345510457 789 18720010234825579 790 67017599927828819 791 220089982549796160 792 673162809203392805 793 1889368652382184886 794 4897175851368309973 795 11815151294558058479 796 26429752014435536176 797 54744315153309975978 798 105525767917549821814 799 188094834138119761312 800 310750983598087588016 801 474985268027082679250 802 664786600639995309561 803 867213121944960751674 804 1014647483470487106694 805 1101036799380962625461 806 1087923060714400472683 807 917961570675847422982 808 777697526811447287958 809 497218732842564339532 810 308405918948829607531 811 186224782016948316653 812 53506444285259063228 813 32782013418024112404 814 8077883801736787460 815 552788047246726320 816 508382234359051234 817 11759642306146901 818 34167141126128 819 43368164873401 820 9651448 821 396652 822 89654132929 823 669961098561 824 4333128207684 825 59934850318767 826 440308405257544 827 2096189870348907 828 9466429650988428 829 39734946253778151 830 146089745153898991 831 492700903891421836 832 1549467990170928732 833 4476164536255290703 834 11960640118894244043 835 29776559713077410272 836 68841520656303075161 837 147812706679408784826 838 295082933363643002007 839 548397513177258639013 840 942633008266505565821 841 1505338750760914111715 842 2224262630143836307796 843 3009993661647339769990 844 3802928407508846808700 845 4301232791981930441124 846 4525620420510919661560 847 4324862075232466850008 848 3527182860409996819285 849 2905026531806752433694 850 1781287490419640495779 851 1075791006026147603157 852 627029678898130702896 853 170293070487781898636 854 103248780952534558847 855 23971378816269072776 856 1517936967949394355 857 1394320517479142574 858 29238656959098957 859 73378480766465 860 93150448496704 861 14144885 862 525453 863 157332809104 864 1221427519663 865 7996610669708 866 113963390591207 867 865004982493518 868 4223773222664510 869 19517746983777052 870 83978852861135445 871 316839657148591485 872 1096494145046579016 873 3541493368696784036 874 10523371452105407097 875 28940140110735555399 876 74287273861350212891 877 177268070966093388776 878 393495689427949644813 879 814534670475164870665 880 1568082654531841033049 881 2812341700149563373479