1 1 2 2 3 2 4 4 5 3 6 7 7 5 8 11 9 8 10 17 11 12 12 26 13 18 14 37 15 27 16 54 17 38 18 76 19 54 20 106 21 76 22 145 23 104 24 199 25 142 26 266 27 192 28 357 29 256 30 472 31 340 32 621 33 448 34 809 35 585 36 1053 37 760 38 1354 39 982 40 1740 41 1260 42 2218 43 1610 44 2818 45 2048 46 3559 47 2590 48 4485 49 3264 50 5616 51 4097 52 7018 53 5120 54 8728 55 6378 56 10826 57 7917 58 13373 59 9792 60 16484 61 12076 62 20236 63 14848 64 24793 65 18200 66 30275 67 22250 68 36886 69 27130 70 44810 71 32992 72 54329 73 40026 74 65683 75 48446 76 79265 77 58499 78 95419 79 70488 80 114650 81 84756 82 137447 83 101698 84 164496 85 121792 86 196445 87 145578 88 234221 89 173682 90 278720 91 206848 92 331143 93 245920 94 392722 95 291874 96 465061 97 345856 98 549781 99 409174 100 649019 101 483330 102 764959 103 570078 104 900373 105 671418 106 1058191 107 789640 108 1242061 109 927406 110 1455820 111 1087744 112 1704261 113 1274118 114 1992458 115 1490528 116 2326608 117 1741521 118 2713398 119 2032290 120 3160899 121 2368800 122 3677789 123 2757826 124 4274556 125 3207086 126 4962526 127 3725410 128 5755174 129 4322816 130 6667228 131 5010688 132 7716070 133 5802008 134 8920663 135 6711480 136 10303379 137 7755776 138 11888671 139 8953856 140 13705118 141 10327156 142 15784173 143 11899934 144 18162385 145 13699699 146 20879933 147 15757502 148 23983452 149 18108418 150 27524280 151 20792120 152 31561603 153 23853318 154 36160845 155 27342421 156 41397124 157 31316314 158 47353396 159 35839008 160 54124796 161 40982540 162 61816437 163 46828032 164 70548311 165 53466624 166 80453313 167 61000704 168 91682668 169 69545358 170 104403741 171 79229676 172 118806744 173 90198446 174 135102223 175 102614114 176 153528658 177 116658616 178 174350347 179 132535702 180 197865953 181 150473568 182 224406247 183 170727424 184 254344551 185 193582642 186 288094273 187 219358315 188 326120818 189 248410816 190 368939881 191 281138048 192 417130912 193 317984256 194 471335560 195 359444904 196 532274004 197 406072422 198 600743477 199 458482688 200 677637038 201 517361670 202 763943462 203 583473184 204 860768675 205 657667584 206 969336374 207 740890786 208 1091013811 209 834194700 210 1227313238 211 938748852 212 1379921672 213 1055852590 214 1550704877 215 1186949056 216 1741741564 217 1333640710 218 1955329266 219 1497705768 220 2194025352 221 1681116852 222 2460655086 223 1886061684 224 2758359212 225 2114965120 226 3090606588 227 2370513986 228 3461249193 229 2655684608 230 3874538905 231 2973772212 232 4335193118 233 3328423936 234 4848416380 235 3723675326 236 5419976831 237 4163989458 238 6056235989 239 4654300706 240 6764237552 241 5200062976 242 7551745299 243 5807301632 244 8427348786 245 6482671322 246 9400510845 247 7233519619 248 10481691022 249 8067955712 250 11682407480 251 8994926602 252 13015380900 253 10024300890 254 14494611559 255 11166959338 256 16135550148 257 12434895064 258 17955192798 259 13841323582 260 19972281105 261 15400801856 262 22207422064 263 17129359744 264 24683321863 265 19044644146 266 27424933132 267 21166075136 268 30459731887 269 23515017984 270 33817897146 271 26114971540 272 37532635562 273 28991772486 274 41640403754 275 32173819904 276 46181288431 277 35692320960 278 51199276537 279 39581557440 280 56742704759 281 43879178240 282 62864586240 283 48626519094 284 69623137992 285 53868949522 286 77082179841 287 59656252987 288 85311752469 289 66043042088 290 94388598563 291 73089209120 292 104396892343 293 80860419136 294 115428817728 295 89428647940 296 127585424365 297 98872765938 298 140977326656 299 109279176298 300 155725707377 301 120742510607 302 171963155398 303 133366383848 304 189834848351 305 147264218618 306 209499553860 307 162560142890 308 231131016922 309 179389964242 310 254919161401 311 197902232212 312 281071716149 313 218259394656 314 309815647639 315 240639052286 316 341399073010 317 265235325352 318 376092964459 319 292260340224 320 414193392040 321 321945841664 322 456023556619 323 354544947722 324 501936417245 325 390334057172 326 552317104620 327 429614917632 328 607586006745 329 472716874732 330 668201629014 331 519999315040 332 734664208371 333 571854313990 334 807519108020 335 628709513216 336 887361047539 337 691031243770 338 974838117691 339 759327910200 340 1070656740240 341 834153664940 342 1175586408938 343 916112394270 344 1290465492317 345 1005862035461 346 1416206837527 347 1104119260918 348 1553804554720 349 1211664556454 350 1704340622478 351 1329347719190 352 1868992828810 353 1458093818816 354 2049042547063 355 1598909656578 356 2245884014803 357 1752890755072 358 2461033491872 359 1921228932216 360 2696140095414 361 2105220502772 362 2952996562191 363 2306275150210 364 3233551909601 365 2525925533946 366 3539924069015 367 2765837686784 368 3874414659252 369 3027822257408 370 4239523818817 371 3313846677248 372 4637967433491 373 3626048321048 374 5072694519260 375 3966748730794 376 5546907319230 377 4338469000206 378 6064081655433 379 4743946406976 380 6627990345061 381 5186152380864 382 7242727027088 383 5668311927092 384 7912733429227 385 6193924614094 386 8642827221949 387 6766787237064 388 9438233773909 389 7391018303854 390 10304618684909 391 8071084479444 392 11248124730538 393 8811829129614 394 12275409852680 395 9618503143424 396 13393690116142 397 10496798204736 398 14610784017405 399 11452882689344 400 15935162430094 401 12493440408000 402 17376000240645 403 13625712407808 404 18943234367521 405 14857542052794 406 20647623917857 407 16197423654282 408 22500817546623 409 17654554915430 410 24515423466364 411 19238893465516 412 26705087638248 413 20961217816576 414 29084575187450 415 22833193070488 416 31669861095285 417 24867441720078 418 34478224844431 419 27077619952640 420 37528355552507 421 29478499862528 422 40840461895119 423 32086058000384 424 44436393951213 425 34917570760097 426 48339770781532 427 37991717107136 428 52576121540041 429 41328689179000 430 57173033484293 431 44950311372460 432 62160315310815 433 48880168540672 434 67570168728394 435 53143743957460 436 73437377461183 437 57768567802880 438 79799506006691 439 62784376939520 440 86697118195159 441 68223286792200 442 94174007341306 443 74119976256080 444 102277448849429 445 80511886581728 446 111058466520179 447 87439435240798 448 120572124404604 449 94946245905984 450 130877834757685 451 103079395713070 452 142039695032663 453 111889681043072 454 154126843836906 455 121431903212544 456 167213849849794 457 131765175508648 458 181381122985037 459 142953253093376 460 196715363066560 461 155064887475476 462 213310034485304 463 168174207315550 464 231265883516899 465 182361127438194 466 250691486032853 467 197711788129024 468 271703843666019 469 214319026883034 470 294429015425803 471 232282884904960 472 319002804462098 473 251711150901902 474 345571486038567 475 272719944823232 476 374292598234247 477 295434344369603 478 405335780597953 479 319989057373738 480 438883684079789 481 346529143303468 482 475132936633678 483 375210787343946 484 514295189939789 485 406202130845496 486 556598230590652 487 439684162112802 488 602287183547709 489 475851671764998 490 651625790290250 491 514914277284172 492 704897791828492 493 557097521610170 494 762408398101066 495 602644050950309 496 824485876692460 497 651814877431176 498 891483241250951 499 704890732521792 500 963780075609705 501 762173517537344 502 1041784473016197 503 823987858076150 504 1125935129584937 505 890682769618944 506 1216703570449712 507 962633441984512 508 1314596551341993 509 1040243150979584 510 1420158612893050 511 1123945306048160 512 1533974834392132 513 1214205643293832 514 1656673763340039 515 1311524574011392 516 1788930571638096 517 1416439699443142 518 1931470413878157 519 1529528503167446 520 2085072043315158 521 1651411233432320 522 2250571659863745 523 1782753988462274 524 2428867050959454 525 1924272018606886 526 2620921998798295 527 2076733260276736 528 2827771020240842 529 2240962117491470 530 3050524412217486 531 2417843507884236 532 3290373675172518 533 2608327191289920 534 3548597286474438 535 2813432400120490 536 3826566903265960 537 3034252791967794 538 4125753966178289 539 3271961746402048 540 4447736790632365 541 3527818029248524 542 4794208116893404 543 3803171849124234 544 5166983213888109 545 4099471332835560 546 5568008507512147 547 4418269447841280 548 5999370837631106 549 4761231401798354 550 6463307314627559 551 5130142551375961 552 6962215889386573 553 5526916854475456 554 7498666608090563 555 5953605902182496 556 8075413676749216 557 6412408569364172 558 8695408307267491 559 6905681325194186 560 9361812482226190 561 7435949247529300 562 10078013611397999 563 8005917788147074 564 10847640230182108 565 8618485338726400 566 11674578714810511 567 9276756650635608 568 12562991179272305 569 9984057165275480 570 13517334530725903 571 10743948315198452 572 14542380864738839 573 11560243860059904 574 15643239180149389 575 12437027325849664 576 16825378612422262 577 13378670620050080 578 18094653169249413 579 14389853899979968 580 19457328187111548 581 15475586776823052 582 20920108496865364 583 16641230942906536 584 22490168539119176 585 17892524315337728 586 24175184423343125 587 19235606795358220 588 25983368195199163 589 20677047748880384 590 27923504313321151 591 22223875320324628 592 30004988626813367 593 23883607699335168 594 32237869862771828 595 25664286467296970 596 34632893944868228 597 27574512158560256 598 37201551162589257 599 29623482180174912 600 39956126544384332 601 31821031242764410 602 42909753466687359 603 34177674464740864 604 46076470888361447 605 36704653322667584 606 49471284256346868 607 39413984631175424 608 53110230512424147 609 42318512747302912 610 57010447263830609 611 45431965206770144 612 61190246591520453 613 48769012012411666 614 65669193578829628 615 52345328808710100 616 70468190083691939 617 56177664191435968 618 75609563859607711 619 60283911416633536 620 81117163603423724 621 64683184789593504 622 87016460062012963 623 69395901032399360 624 93334653835856315 625 74443865946867656 626 100100790042975735 627 79850366709300780 628 107345880548546164 629 85640270154839880 630 115103033958846220 631 91840127431009792 632 123407594159803523 633 98478285423449690 634 132297287640305694 635 105585005382256254 636 141812380462614174 637 113192589203419858 638 151995845168032556 639 121335513847754770 640 162893538572246567 641 130050574409982720 642 174554390792397239 643 139377036381734912 644 187030606562814216 645 149356797685522944 646 200377879244283148 647 160034561092715412 648 214655618696401211 649 171458017675660736 650 229927193490019755 651 183678041983751325 652 246260188755533387 653 196748899676004248 654 263726680225059152 655 210728468386953976 656 282403525904799158 657 225678472649866304 658 302372676029236730 659 241664733752111550 660 323721502888247539 661 258757435450198016 662 346543151285690893 663 277031406528143070 664 370936911393852837 665 296566421243219584 666 397008614882415607 667 317447518765789464 668 424871056279313066 669 339765342786728358 670 454644440579942237 671 363616502537591540 672 486456859275080349 673 389103956543205484 674 520444795970714492 675 416337420505729280 676 556753664008383427 677 445433800804233382 678 595538377435218686 679 476517655182415360 680 636963957997641000 681 509721682291305440 682 681206179708724628 683 545187241854615562 684 728452253956523450 685 583064907329563392 686 778901556931017185 687 623515053047830240 688 832766402664850314 689 666708477940781056 690 890272863720958409 691 712827068077888960 692 951661643187428123 693 762064500379931334 694 1017189000302938896 695 814626990010044184 696 1087127733777339270 697 870734084093744242 698 1161768225458784733 699 930619504576216576 700 1241419548863484196 701 994532043192721630 702 1326410645587323996 703 1062736511703408640 704 1417091574618234044 705 1135514750730008498 706 1513834837985091600 707 1213166700730163200 708 1617036788319140019 709 1296011538852931584 710 1727119122233384313 711 1384388885639414580 712 1844530465717824666 713 1478660085766970048 714 1969748055982167023 715 1579209567281427499 716 2103279526636351548 717 1686446284022472878 718 2245664801234607252 719 1800805246224619946 720 2397478102841210993 721 1922749144567113036 722 2559330085312119095 723 2052770073254433792 724 2731870094807234027 725 2191391358036657966 726 2915788567975740079 727 2339169495422851818 728 3111819576282904540 729 2496696209705056142 730 3320743523763521036 731 2664600634797244428 732 3543390008728357649 733 2843551628300021780 734 3780640857655324211 735 3034260225632153600 736 4033433342971277473 737 3237482242526609435 738 4302763594014839539 739 3454021034668672126 740 4589690214199025976 741 3684730423761609196 742 4895338114853848678 743 3930517799844061184 744 5220902580224720250 745 4192347410249609126 746 5567653575441006945 747 4471243846198231222 748 5936940313554104348 749 4768295738644494630 750 6330196094950364438 751 5084659675675275560 752 6748943437044767639 753 5421564354456374560 754 7194799509233256841 755 5780314981475902398 756 7669481893014897045 757 6162297935619707410 758 8174814684134630454 759 6568985709446779998 760 8712734958890993684 761 7001942144914244608 762 9285299623550808323 763 7462827980729244054 764 9894692671499268811 765 7953406729485749760 766 10543232869409599988 767 8475550903782345984 768 11233381899818249190 769 9031248611609428978 770 11967752984008984427 771 9622610542448775692 772 12749120015661139360 773 10251877366749901978 774 13580427232087627682 775 10921427572733267968 776 14464799456930770226 777 11633785765828776960 778 15405552944409735571 779 12391631457494629928 780 16406206862776042963 781 13197808371673868288 782 17470495450721323145 783 14055334298743378466 784 18602380888608167407 785 14967411528498953760 786 19806066922337818002 787 15937437895497941056 788 21086013286409744633 789 16969018471958594188 790 22446950968532281767 791 18065977945399587372 792 23893898367538463677 793 19232373720292328568 794 25432178392037731016 795 20472509785204469270 796 27067436557338194985 797 21790951389243426816 798 28805660133719600437 799 23192540574062407000 800 30653198410013982982 801 24682412610281394566 802 32616784131876852095 803 26266013389911124610 804 34703556185832723301 805 27949117829248335651 806 36921083595502883781 807 29737849339750236888 808 39277390909018815444 809 31638700427605669254 810 41780985051848964212 811 33658554486099838720 812 44440883732837249019 813 35804708848435100160 814 47266645486395624513 815 38084899172434148232 816 50268401448406356502 817 40507325232515026318 818 53456888958480630168 819 43080678198507903008 820 56843487096965974024 821 45814169485295430240 822 60440254260143368182 823 48717561261903748022 824 64259967894035702062 825 51801198713570368742 826 68316166502286026728 827 55076044155484162048 828 72623194061868521338 829 58553713102334907284 830 77196246975461194264 831 62246512403548480780 832 82051423709052657188 833 66167480560136966222 834 87205777258473734637 835 70330430345465913382 836 92677370609857444639 837 74749993858959671642 838 98485335354248961206 839 79441670148851154112 840 104649933639586238629 841 84421875547541659360 842 111192623638649623409 843 89707996870998899650 844 118136128736412249502 845 95318447641911228416 846 125504510635801596267 847 101272727505042773236 848 133323246607717741452 849 107591485012430987264 850 141619311107003759451 851 114296583965762716160 852 150421262005054357388 853 121411173513469673536 854 159759331685956494006 855 128959762210836804066 856 169665523284392977549 857 136968296262749272064 858 180173712340173117831 859 145464242180631569964 860 191319754178153410284 861 154476674097698088756 862 203141597319472231606 863 164036365999875151520 864 215679403266685738519 865 174175889143689803072 866 228975673003204118487 867 184929714947098946238 868 243075380587102180925 869 196334323654695984198 870 258026114217946091712 871 208428319095005537792 872 273878225198241907535 873 221252549864715044864 874 290684985210582233327 875 234850237292743767414 876 308502752378087241056 877 249267110556045123600 878 327391146576283189654 879 264551549339039858718 880 347413234514958566459 881 280754734449641432204 882 368635725110317986958 883 297930806826997905474 884 391129175722386943667 885 316137035399407747392 886 414968209835841772511 887 335433994275434973760 888 440231746821660199470 889 355885749777096359936 890 467003244421892697588 891 377560057851201255424 892 495370954664081445693 893 400528572423567315090 894 525428193918671049402 895 424867065290966672074 896 557273627882453001346 897 450655658177369330930 898 591011572280107532344 899 477979067614429745662 900 626752310151539835010 901 506926863341272619400 902 664612426604269765939 903 537593740955580698210 904 704715161992247300174 905 570079809586869714240 906 747190784496896557477 907 604490895403729929376 908 792176983175389830277 909 640938861809840788774 910 839819282558857705436 911 679541947228839136972 912 890271479980137737562 913 720425121425732873728 914 943696106832106389991 915 763720461362638982518 916 1000264915062943863688 917 809567547639319166144 918 1060159390240324602909 919 858113882624395098112 920 1123571292631029002641 921 909515331441406613044 922 1190703227772875963225 923 963936587035181776118 924 1261769248140384155431 925 1021551660608444235569 926 1336995487541370432487 927 1082544398786371565568 928 1416620830017137109883 929 1147109028938113381600 930 1500897615060744253488 931 1215450734159228878080 932 1590092381115271781507 933 1287786259497817415734 934 1684486649362632955137 935 1364344551089994484950 936 1784377749973940214961 937 1445367429957483933184 938 1890079693048760668632 939 1531110302311693280552 940 2001924086645285805769 941 1621842908304944646196 942 2120261104368352349208 943 1717850111270754672832 944 2245460505172533305481 945 1819432729601465049152 946 2377912708112055652918 947 1926908413523388672000 948 2518029924976583150957 949 2040612569147195553350 950 2666247353837243604108 951 2160899332294829327200 952 2823024436753157088546 953 2288142594734128375808 954 2988846184986098124159 955 2422737085588806034050 956 3164224575317159945216 957 2565099510834879982920 958 3349700021170126554207 959 2715669753945387483554 960 3545842922514704186965 961 2874912140903608250624 962 3753255298648657562484 963 3043316772971451122764 964 3972572508250645208495 965 3221400930774553942016 966 4204465061238181125258 967 3409710553449380120290 968 4449640527284511159183 969 3608821796790641279424 970 4708845546009493760732 971 3819342674540204977856 972 4982867944207990479441 973 4041914787171704356882 974 5272538965661393023532 975 4277215142748892965176 976 5578735619458129344236 977 4525958074670926499072 978 5902383152954219520063 979 4788897261364720340170 980 6244457655919994557575 981 5066827853243947716352 982 6605988802650027521323 983 5360588712526733770910 984 6988062739266414099436 985 5671064771790265593856 986 7391825123705077675873 987 5999189517441089061374 988 7818484326369510457576 989 6345947604595520352920 990 8269314799727594401589 991 6712377610196059013120 992 8745660625667499848870 993 7099574931537767204250 994 9248939249755082188441 995 7508694837744105125888 996 9780645412125408321243 997 7940955682115491800174 998 10342355285106537360889 999 8397642283676830881826 1000 10935730828318479156533