1 1 2 1 3 1 4 3 5 4 6 6 7 7 8 9 9 11 10 13 11 16 12 19 13 22 14 26 15 32 16 36 17 42 18 52 19 59 20 66 21 79 22 93 23 108 24 125 25 141 26 162 27 192 28 222 29 248 30 285 31 331 32 375 33 430 34 492 35 555 36 632 37 719 38 816 39 929 40 1051 41 1177 42 1327 43 1510 44 1701 45 1908 46 2146 47 2408 48 2705 49 3035 50 3388 51 3792 52 4257 53 4751 54 5284 55 5894 56 6572 57 7313 58 8144 59 9058 60 10049 61 11145 62 12354 63 13695 64 15190 65 16807 66 18562 67 20520 68 22687 69 25040 70 27606 71 30427 72 33523 73 36931 74 40654 75 44702 76 49147 77 54001 78 59267 79 65040 80 71383 81 78268 82 85738 83 93914 84 102835 85 112519 86 123039 87 134491 88 146989 89 160583 90 175273 91 191211 92 208606 93 227498 94 247933 95 270084 96 294097 97 320111 98 348316 99 378873 100 411957 101 447771 102 486453 103 528238 104 573512 105 622484 106 675268 107 732269 108 793920 109 860454 110 932190 111 1009554 112 1092999 113 1183038 114 1280061 115 1384481 116 1497022 117 1618314 118 1748772 119 1889146 120 2040324 121 2202906 122 2377662 123 2565618 124 2767691 125 2984843 126 3218062 127 3468373 128 3737265 129 4026232 130 4336256 131 4668653 132 5025330 133 5407964 134 5818190 135 6257993 136 6729342 137 7234398 138 7775538 139 8354981 140 8975428 141 9639950 142 10351116 143 11111896 144 11926124 145 12797252 146 13728634 147 14724473 148 15789176 149 16927211 150 18143441 151 19442627 152 20830164 153 22312475 154 23895450 155 25584995 156 27388433 157 29313250 158 31366804 159 33557540 160 35894341 161 38386234 162 41043177 163 43875458 164 46894049 165 50111378 166 53539570 167 57190805 168 61079732 169 65221847 170 69632124 171 74327030 172 79324416 173 84642754 174 90302012 175 96322894 176 102726912 177 109538201 178 116781914 179 124483195 180 132670001 181 141372308 182 150620248 183 160446621 184 170886904 185 181977449 186 193756884 187 206265998 188 219547467 189 233648137 190 248617195 191 264504000 192 281362173 193 299250319 194 318228326 195 338359109 196 359710304 197 382352483 198 406360603 199 431814196 200 458795807 201 487393825 202 517702160 203 549817258 204 583842081 205 619887744 206 658068773 207 698505003 208 741325302 209 786664969 210 834666160 211 885479095 212 939260360 213 996176752 214 1056406367 215 1120133029 216 1187549563 217 1258863105 218 1334290699 219 1414059097 220 1498409279 221 1587594220 222 1681879101 223 1781544771 224 1886885937 225 1998213345 226 2115856502 227 2240158317 228 2371478199 229 2510200111 230 2656727066 231 2811478596 232 2974898558 233 3147455232 234 3329640100 235 3521971115 236 3724990600 237 3939268140 238 4165407741 239 4404042287 240 4655832594 241 4921478408 242 5201716133 243 5497314527 244 5809084229 245 6137879479 246 6484594792 247 6850170463 248 7235593880 249 7641901851 250 8070188947 251 8521601927 252 8997337026 253 9498657221 254 10026894590 255 10583440351 256 11169754253 257 11787372306 258 12437904646 259 13123043054 260 13844563546 261 14604326009 262 15404286839 263 16246499986 264 17133112125 265 18066380128 266 19048678715 267 20082489786 268 21170414524 269 22315189381 270 23519682395 271 24786898659 272 26119988764 273 27522252567 274 28997157725 275 30548344056 276 32179612534 277 33894947450 278 35698538785 279 37594771642 280 39588235052 281 41683745661 282 43886348326 283 46201325546 284 48634215615 285 51190816686 286 53877205454 287 56699752803 288 59665117629 289 62780273241 290 66052541879 291 69489583658 292 73099403910 293 76890394538 294 80871346555 295 85051459154 296 89440363680 297 94048134089 298 98885316744 299 103962964563 300 109292631404 301 114886396283 302 120756919481 303 126917446600 304 133381818652 305 140164528727 306 147280744631 307 154746320401 308 162577840655 309 170792651433 310 179408897289 311 188445568874 312 197922507804 313 207860442190 314 218281075900 315 229207111193 316 240662253160 317 252671287508 318 265260137687 319 278455893054 320 292286872324 321 306782669764 322 321974205752 323 337893813259 324 354575273839 325 372053860494 326 390366455421 327 409551606889 328 429649549505 329 450702320367 330 472753860830 331 495850057237 332 520038829134 333 545370223478 334 571896504134 335 599672279732 336 628754571334 337 659202874368 338 691079335367 339 724448877841 340 759379245997 341 795941153663 342 834208448130 343 874258199588 344 916170848900 345 960030367807 346 1005924385002 347 1053944370029 348 1104185779808 349 1156748176148 350 1211735475190 351 1269256157030 352 1329423352647 353 1392355062037 354 1458174436571 355 1527009947950 356 1598995591647 357 1674271134947 358 1752982340270 359 1835281263405 360 1921326514033 361 2011283437911 362 2105324459699 363 2203629444417 364 2306385897437 365 2413789286411 366 2526043465096 367 2643360957102 368 2765963281804 369 2894081375623 370 3027955962588 371 3167837983499 372 3313989017167 373 3466681613249 374 3626199814776 375 3792839743046 376 3966909951824 377 4148731886369 378 4338640542880 379 4536984991644 380 4744128899042 381 4960451164516 382 5186346503125 383 5422226111463 384 5668518383488 385 5925669493241 386 6194144147350 387 6474426474270 388 6767020666719 389 7072451716309 390 7391266432100 391 7724034291930 392 8071348236850 393 8433825669751 394 8812109441585 395 9206868896127 396 9618800978143 397 10048631178289 398 10497114674789 399 10965037738130 400 11453218858623 401 11962509873748 402 12493797465862 403 13048004556750 404 13626091621415 405 14229058254045 406 14857944716518 407 15513833518587 408 16197851162561 409 16911169749814 410 17655008753700 411 18430637136736 412 19239375172680 413 20082596223391 414 20961729052164 415 21878260098556 416 22833735544992 417 23829763672899 418 24868017315033 419 25950236367743 420 27078230529824 421 28253881878634 422 29479147561797 423 30756063004118 424 32086744913629 425 33473394146632 426 34918299176711 427 36423839614231 428 37992489484429 429 39626820913874 430 41329508023662 431 43103330814729 432 44951179328342 433 46876057737765 434 48881088581067 435 50969517678784 436 53144718897710 437 55410198614203 438 57769600940876 439 60226713273054 440 62785471537934 441 65449965834320 442 68224446399353 443 71113329625963 444 74121204521987 445 77252839217495 446 80513187525331 447 83907396304570 448 87440812882892 449 91118992167317 450 94947704662403 451 98932945009985 452 103080940126444 453 107398157816095 454 111891316047343 455 116567392356488 456 121433633728958 457 126497566639552 458 131767007180054 459 137250072281657 460 142955191303942 461 148891117164043 462 155066938406794 463 161492092221368 464 168176377206728 465 175129966683791 466 182363422900383 467 189887711413670 468 197714216120701 469 205854754820602 470 214321594973793 471 223127470714339 472 232285600523690 473 241809704458351 474 251714022566786 475 262013334827822 476 272722980892240 477 283858880309723 478 295437554109121 479 307476146941762 480 319992450113883 481 333004925449983 482 346532729388507 483 360595738617075 484 375214577077003 485 390410642733881 486 406206135587113 487 422624087719388 488 439688393484335 489 457423840433616 490 475856142233397 491 495011972491040 492 514918999606232 493 535605922979981 494 557102509930493 495 579439634628565 496 602649319074432 497 626764773977287 498 651820441072511 499 677852038539880 500 704896607252944 501 732992557842190 502 762179720297387 503 792499395172820 504 823994406416687 505 856709156428181 506 890689682307952 507 925983714444803 508 962640738128120 509 1000712055868121 510 1040250851641015 511 1081312259261254 512 1123953432321332 513 1168233615288956 514 1214214218295855 515 1261958894746624 516 1311533621141040 517 1363006779923120 518 1416449244387103 519 1471934466888946 520 1529538571672108 521 1589340449367900 522 1651421853708800 523 1715867503751916 524 1782765189366572 525 1852205878766015 526 1924283830929930 527 1999096712182091 528 2076745715967348 529 2157335687281153 530 2240975250832612 531 2327776943611206 532 2417857353628341 533 2511337261877159 534 2608341787725222 535 2709000542022349 536 2813447785573225 537 2921822590521178 538 3034269008241811 539 3150936243936903 540 3271978836403629 541 3397556844415008 542 3527836038688178 543 3662988099847935 544 3803190825350082 545 3948628342506146 546 4099491326487391 547 4255977228262594 548 4418290510925529 549 4586642891193143 550 4761253590167240 551 4942349594059885 552 5130165922351691 553 5324945905178925 554 5526941469787476 555 5736413436103256 556 5953631824752084 557 6178876174527491 558 6412435867204526 559 6654610466109732 560 6905710068036480 561 7166055663545936 562 7435979509594735 563 7715825516541192 564 8005949646808521 565 8306720327286893 566 8618518875562414 567 8941739938946172 568 9276791950496790 569 9624097600273453 570 9984094318596658 571 10357234778033830 572 10743987414691881 573 11144836962581754 574 11560285005545221 575 11990850550712326 576 12437070619747296 577 12899500859236433 578 13378716171249818 579 13875311363154335 580 14389901821911828 581 14923124211628427 582 15475637189017397 583 16048122144168233 584 16641283969970549 585 17255851852911023 586 17892580088816000 587 18552248928919659 588 19235665452139983 589 19943664465264836 590 20677109433777590 591 21436893441416570 592 22223940183417370 593 23039204993707988 594 23883675900073969 595 24758374715401139 596 25664358170498964 597 26602719079287104 598 27574587538993905 599 28581132174012800 600 29623561419816396 601 30703124847506868 602 31821114532360387 603 32978866464067774 604 34177762004900307 605 35419229398729952 606 36704745323002001 607 38035836490652770 608 39414081310726350 609 40841111598593793 610 42318614337654903 611 43848333503653790 612 45432071947538012 613 47071693336184879 614 48769124157110707 615 50526355785829258 616 52345446621787724 617 54228524297220164 618 56177787949742639 619 58195510566082864 620 60284041410518029 621 62445808528321382 622 64683321322948857 623 66999173221054234 624 69396044423613086 625 71876704742286886 626 74444016528808094 627 77100937695305299 628 79850524831100391 629 82695936424656114 630 85640436182060417 631 88687396447846602 632 91840301745068893 633 95102752425325555 634 98478468425923402 635 101971293153044520 636 105585197491308065 637 109324283935961045 638 113192790857214806 639 117195096897308206 640 121335725507106254 641 125619349634238883 642 130050796552851355 643 134635052838605733 644 139377269512372839 645 144282767346850545 646 149357042330027569 647 154605771306554431 648 160034817800397429 649 165650238014780547 650 171458287023128482 651 177465425153835346 652 183678324573854805 653 190103876086735820 654 196749196137906929 655 203621634030540265 656 210728779381159982 657 218078469811347061 658 225678798865159135 659 233538124178448610 660 241665075911036974 661 250068565436656478 662 258757794305035526 663 267742263481559726 664 277031782871188065 665 286636481149516325 666 296566815896715627 667 306833584033544968 668 317447932593917212 669 328421369837703906 670 339765776692368897 671 351493418553803790 672 363616957462991070 673 376149464651507375 674 389104433474570601 675 402495792745175273 676 416337920477090541 677 430645658063207183 678 445434324888481335 679 460719733376221159 680 476518204511922395 681 492846583857589553 682 509722258040245843 683 527163171747115106 684 545187845255807426 685 563815392496494251 686 583065539668595053 687 602958644430713428 688 623515715671918548 689 644758433899319945 690 666709172251758107 691 689391018137755006 692 712827795547396198 693 737044088061331654 694 762065262540565347 695 787917493536921221 696 814627788467175787 697 842224013548397018 698 870734920518312812 699 900190174171248926 700 930620380725602648 701 962057117067173732 702 994532960886508071 703 1028081521706334042 704 1062737472858760029 705 1098536584455621446 706 1135515757338193270 707 1173713058047913677 708 1213167754875628901 709 1253920354994807635 710 1296012642711692521 711 1339487718878198886 712 1384390041487864940 713 1430765467506400023 714 1478661295971443654 715 1528126312365021024 716 1579210834330533431 717 1631966758796653745 718 1686447610495711770 719 1742708591924485352 720 1800806634831861225 721 1860800453252644549 722 1922750598124173553 723 1986719513545847713 724 2052771594714981902 725 2120973247608521869 726 2191392950468060813 727 2264101317096114318 728 2339171162044119726 729 2416677567783526103 730 2496697953863351852 731 2579312148112233817 732 2664602459994267776 733 2752653756151883141 734 2843553538183246037 735 2937392022743363162 736 3034262224023746956 737 3134260038694516631 738 3237484333389337982 739 3344037034755428574 740 3454023222170622841 741 3567551223258732626 742 3684732712222538583 743 3805682811057754638 744 3930520193792825736 745 4059367193822141709 746 4192349914399216305 747 4329598342406118699 748 4471246465475941438 749 4617432392576315283 750 4768298478177075241 751 4923991450051695663 752 5084662540833261915 753 5250467623496553007 754 5421567350815417450 755 5598127298881642551 756 5780318114879864128 757 5968315669223989489 758 6162301212138225713 759 6362461534838706842 760 6568989135439279221 761 6782082389727697352 762 7001945726980399442 763 7228789810894639857 764 7462831725788057075 765 7704295168303829174 766 7953410644722999324 767 8210415673992335671 768 8475554996711001495 769 8749080790238910864 770 9031252890052732788 771 9322339017564427298 772 9622615014579386682 773 9932365084579451482 774 10251882041061150386 775 10581467563069040967 776 10921432458124346429 777 11272096932860738622 778 11633790871527794221 779 12006854122507609982 780 12391636793168635762 781 12788499553309009377 782 13197813947364989405 783 13619962715659884197 784 14055340124947562632 785 14504352308510105146 786 14967417616132730486 787 15444966974171645666 788 15937444255967233233 789 16445306663009536917 790 16969025117121230695 791 17509084663873108198 792 18065984887647871243 793 18640240338706426418 794 19232380972506884154 795 19842952601653414108 796 20472517360848226210 797 21121654185197765865 798 21790959302298103948 799 22481046738421685112 800 23192548839155867870 801 23926116805039836047 802 24682421242597782260 803 25462152731061627586 804 26266022405317165350 805 27094762555590313665 806 27949127244249601322 807 28829892940225762223 808 29737859171559910730 809 30673849196557873071 810 31638710694135043982 811 32633316473841744200 812 33658565206046839413 813 34715382172981947468 814 35804720041222673242 815 36927559656043861431 816 38084910858360214518 817 39277813324974211419 818 40507337432658179262 819 41774585146734467374 820 43080690934879532650 821 44426822706829686831 822 45814182780775403890 823 47244008877135224376 824 48717575140360971745 825 50236193189709534307 826 51801213199826672854 827 53414025011775357090 828 55076059275424226003 829 56788788624186401937 830 58553728882880117917 831 60372440309623645623 832 62246528872768709728 833 64177647563794867107 834 66167497747214391620 835 68217830548483522832 836 70330448280849590330 837 72507205912369725222 838 74750012574272652437 839 77060833111564048640 840 79441689677098108734 841 81894663370496801525 842 84421895923021439995 843 87025591429610776115 844 89708018129452006166 845 92471510236377689726 846 95318469820528802205 847 98251368742687153081 848 101272750642554478963 849 104385232982599584161 850 107591509149117852091 851 110894350611823894213 852 114296609143607688489 853 117801219102314102948 854 121411199776096953359 855 125129657794009436530 856 128959789603726765076 857 132904884018199830539 858 136968324833164632799 859 141153593517440632244 860 145464271977815339351 861 149904045400702454953 862 154476705172847717916 863 159186151882942464786 864 164036398406308201706 865 169031573075186775870 866 174175922936852944896 867 179473817101821111360 868 184929750184704967638 869 190548345840196268504 870 196334360396781376212 871 202292686590899445102 872 208428357404059831496 873 214746550005817141244 874 221252589805691064263 875 227951954616678786740 876 234850278933308389168 877 241953358327668637707 878 249267153966491901005 879 256797797252366449470 880 264551594592564588053 881 272535032298925296960 882 280754781622357587508 883 289217703925651220213 884 297930855998065991636 885 306901495515600337866 886 316137086651181832620 887 325645305838519238268 888 335434047693576676660 889 345511431098267980116 890 355885805450660567091 891 366565757085937340662 892 377560115872861859780 893 388877961990448410799 894 400528632889643827266 895 412521730445068965303 896 424867128301675207285 897 437574979421590078105 898 450655723836875186948 899 464120096613382965954 900 477979136031097225814 901 492244191987188452955 902 506926934627736587119 903 522039363213907144988 904 537593815228964967431 905 553602975732577757159 906 570079886968988341942 907 587037958235959354702 908 604490976021162770856 909 622453114413090067231 910 640938945794227009976 911 659963451823744290808 912 679542034717058248980 913 699690528830607515841 914 720425212559987559878 915 741762820559364219998 916 763720556290850085133 917 786316104912694893792 918 809567646515200137751 919 833493869713686801106 920 858113985607696055917 921 883447742116047930417 922 909515438698241369400 923 936337941472171880535 924 963936698738129952866 925 992333756920293542294 926 1021551776936918521901 927 1051614051010099309497 928 1082544519926803831764 929 1114367790763186564003 930 1147109155084279156154 931 1180794607631764942745 932 1215450865512462343794 933 1251105387900516526592 934 1287786396267362088367 935 1325522895153153103007 936 1364344693493295576672 937 1404282426515190865847 938 1445367578220436113654 939 1487632504467266306150 940 1531110456669033678866 941 1575835606125102573024 942 1621843069000638630263 943 1669168931972456106057 944 1717850278558093950545 945 1767925216145715215919 946 1819432903743822761597 947 1872413580469572356623 948 1926908594794220598762 949 1982960434565929136936 950 2040612757830625117649 951 2099910424471145679682 952 2160899528686044542308 953 2223627432330235432818 954 2288142799139741657589 955 2354495629863725720439 956 2422737298327248053701 957 2492920588448645297152 958 2565099732237037258617 959 2639330448795454828184 960 2715669984354786648426 961 2794177153365777621908 962 2874912380677188998948 963 2957937744827625589546 964 3043317022479774599963 965 3131115734027018873497 966 3221401190402663405175 967 3314242541123126966999 968 3409710823596904213681 969 3507879013731534666845 970 3608822077872826200980 971 3712617026111004493545 972 3819342966988101615586 973 3929081163643135428812 974 4041915091432955627869 975 4157930497066078715435 976 4277215459288333312595 977 4399860451160850427097 978 4525958403971276627340 979 4655604772820360406275 980 4788897603926928564135 981 4925937603694917183293 982 5066828209588545431046 983 5211675662862521634451 984 5360589083193710830269 985 5513680545263295760404 986 5671065157340557018422 987 5832861141918962095987 988 5999189918456833574564 989 6170176188277088633213 990 6345948021681197996349 991 6526636947334197459590 992 6712378043978962864451 993 6903310034538691285771 994 7099575382669319942690 995 7301320391825093128897 996 7508695306900216081420 997 7721854418512532025912 998 7940956169997976152058 999 8166163267184234395879 1000 8397642791013872760213