0 1 1 1 2 1 3 1 4 2 5 2 6 3 7 4 8 5 9 6 10 8 11 9 12 12 13 14 14 17 15 20 16 25 17 29 18 35 19 41 20 49 21 57 22 68 23 78 24 93 25 107 26 125 27 144 28 168 29 192 30 223 31 255 32 294 33 335 34 385 35 437 36 501 37 568 38 647 39 732 40 833 41 939 42 1065 43 1199 44 1355 45 1523 46 1717 47 1925 48 2166 49 2425 50 2720 51 3040 52 3405 53 3797 54 4244 55 4727 56 5272 57 5863 58 6528 59 7247 60 8057 61 8933 62 9912 63 10975 64 12162 65 13446 66 14878 67 16430 68 18152 69 20021 70 22092 71 24335 72 26819 73 29510 74 32478 75 35698 76 39246 77 43087 78 47315 79 51895 80 56923 81 62370 82 68343 83 74806 84 81889 85 89552 86 97929 87 106996 88 116899 89 127604 90 139287 91 151915 92 165673 93 180542 94 196727 95 214204 96 233215 97 253737 98 276026 99 300085 100 326197 101 354357 102 384898 103 417826 104 453497 105 491945 106 533564 107 578393 108 626890 109 679107 110 735539 111 796283 112 861889 113 932460 114 1008633 115 1090544 116 1178881 117 1273839 118 1376183 119 1486137 120 1604580 121 1731778 122 1868692 123 2015678 124 2173805 125 2343473 126 2525904 127 2721578 128 2931833 129 3157269 130 3399377 131 3658841 132 3937360 133 4235730 134 4555821 135 4898608 136 5266173 137 5659619 138 6081309 139 6532529 140 7015885 141 7532903 142 8086491 143 8678385 144 9311875 145 9988954 146 10713259 147 11487140 148 12314650 149 13198445 150 14143101 151 15151662 152 16229196 153 17379234 154 18607429 155 19917779 156 21316645 157 22808578 158 24400630 159 26098054 160 27908711 161 29838518 162 31896309 163 34088806 164 36425812 165 38915013 166 41567333 167 44391437 168 47399572 169 50601532 170 54010914 171 57638873 172 61500555 173 65608490 174 69979635 175 74628130 176 79572796 177 84829651 178 90419649 179 96360772 180 102676439 181 109386863 182 116518046 183 124092817 184 132140103 185 140685466 186 149761187 187 159395962 188 169625615 189 180482430 190 192006235 191 204233138 192 217207527 193 230969820 194 245569265 195 261051230 196 277470416 197 294877465 198 313333260 199 332894409 200 353628419 201 375598641 202 398880008 203 423543151 204 449671366 205 477343432 206 506651654 207 537684036 208 570542939 209 605326312 210 642147809 211 681116521 212 722358311 213 765994768 214 812165355 215 861005242 216 912669091 217 967307190 218 1025090691 219 1086186834 220 1150785092 221 1219071097 222 1291254754 223 1367542186 224 1448165500 225 1533353651 226 1623363363 227 1718448496 228 1818893141 229 1924978759 230 2037019249 231 2155326805 232 2280248312 233 2412129453 234 2551353710 235 2698303890 236 2853403358 237 3017076087 238 3189789519 239 3372012603 240 3564261570 241 3767055044 242 3980962498 243 4206557604 244 4444468569 245 4695329161 246 4959832483 247 5238678673 248 5532631679 249 5842464945 250 6169020486 251 6513151886 252 6875787270 253 7257868501 254 7660417750 255 8084474322 256 8531163858 257 9001632116 258 9497118716 259 10018886621 260 10568299938 261 11146750676 262 11755739779 263 12396800342 264 13071583810 265 13781778316 266 14529199686 267 15315706641 268 16143295475 269 17014011266 270 17930048574 271 18893657129 272 19907248010 273 20973295711 274 22094448790 275 23273427348 276 24513140506 277 25816577685 278 27186932510 279 28627489959 280 30141755384 281 31733336474 282 33406080279 283 35163948137 284 37011160046 285 38952064880 286 40991290907 287 43133610137 288 45384097880 289 47747989252 290 50230847350 291 52838414375 292 55576786929 293 58452260493 294 61471515306 295 64641452004 296 67969387345 297 71462883813 298 75129953790 299 78978881710 300 83018440243 301 87257702603 302 91706270312 303 96374078634 304 101271634148 305 106409811819 306 111800106581 307 117454419444 308 123385322283 309 129605836303 310 136129708469 311 142971180618 312 150145281903 313 157667585715 314 165554517649 315 173823103836 316 182491292394 317 191577691435 318 201101909114 319 211084278166 320 221546213752 321 232509928492 322 243998806354 323 256037106183 324 268650356930 325 281865046350 326 295709037077 327 310211244847 328 325402073140 329 341313078842 330 357977431713 331 375429563770 332 393705652807 333 412843260273 334 432881836856 335 453862346570 336 475827800859 337 498822865018 338 522894420414 339 548091158434 340 574464168347 341 602066516353 342 630953866749 343 661184041750 344 692817675207 345 725917759009 346 760550327187 347 796783986303 348 834690637882 349 874344988240 350 915825309050 351 959212932868 352 1004593049228 353 1052054183134 354 1101689035975 355 1153593942058 356 1207869753760 357 1264621283164 358 1323958229221 359 1385994601545 360 1450849699400 361 1518647512423 362 1589517751631 363 1663595234700 364 1741020966255 365 1821941504755 366 1906510103462 367 1994886053393 368 2087235884757 369 2183732694539 370 2284557406313 371 2389898079238 372 2499951238424 373 2614921159515 374 2735021270305 375 2860473420316 376 2991509351043 377 3128369947461 378 3271306790977 379 3420581386681 380 3576466799534 381 3739246867871 382 3909217921104 383 4086687976214 384 4271978552039 385 4465423842468 386 4667372628934 387 4878187442020 388 5098246569988 389 5327943205727 390 5567687568902 391 5817906031607 392 6079043355830 393 6351561810926 394 6635943525370 395 6932689593065 396 7242322558242 397 7565385504122 398 7902444674110 399 8254088557406 400 8620930645357 401 9003608511382 402 9402786724575 403 9819155917245 404 10253435859211 405 10706374529580 406 11178751352088 407 11671376268922 408 12185093161001 409 12720778917500 410 13279347046645 411 13861746759491 412 14468966771941 413 15102034401270 414 15762019587247 415 16450033995339 416 17167235263194 417 17914826131857 418 18694058920439 419 19506234684650 420 20352707950277 421 21234885893680 422 22154233343384 423 23112272006548 424 24110585742320 425 25150819835063 426 26234686575135 427 27363964574454 428 28540504665399 429 29766229286390 430 31043138705817 431 32373310479811 432 33758906040882 433 35202170224914 434 36705438239285 435 38271135290732 436 39901783941540 437 41600003843005 438 43368519525932 439 45210160238500 440 47127868188592 441 49124698522639 442 51203828033146 443 53368555285767 444 55622309843819 445 57968652545205 446 60411285267093 447 62954051395012 448 65600946144147 449 68356117231754 450 71223875815871 451 74208697375775 452 77315233295900 453 80548312003598 454 83912951221455 455 87414359377983 456 91057948596927 457 94849336390445 458 98794359421240 459 102899075535484 460 107169778326530 461 111612999529214 462 116235524465990 463 121044394817484 464 126046924994054 465 131250705349963 466 136663619518727 467 142293848099875 468 148149887050123 469 154240551865135 470 160574997081324 471 167162721031353 472 174013586504025 473 181137826111786 474 188546064217310 475 196249322944433 476 204259045437196 477 212587102607501 478 221245817788085 479 230247974266432 480 239606841456661 481 249336183262824 482 259450285852588 483 269963966959637 484 280892605334600 485 292252151050689 486 304059156779582 487 316330789157784 488 329084861987131 489 342339848792245 490 356114918041857 491 370429946978654 492 385305559032880 493 400763139000160 494 416824872771428 495 433513764013277 496 450853676331711 497 468869351558546 498 487586454552085 499 507031593187160 500 527232365942486 501 548217383778397 502 570016320658758 503 592659937446052 504 616180135594892 505 640609983189975 506 665983771996000 507 692337045857775 508 719706661286594 509 748130818385250 510 777649125252740 511 808302631593021 512 840133897161348 513 873187028318702 514 907507750743723 515 943143449135235 516 980143244520389 517 1018558037306342 518 1058440589458533 519 1099845571214248 520 1142829648403590 521 1187451533076404 522 1233772076359949 523 1281854323250506 524 1331763611338380 525 1383567630138918 526 1437336526020945 527 1493142966388038 528 1551062251274639 529 1611172382691521 530 1673554183293805 531 1738291371338785 532 1805470686834136 533 1875181972491493 534 1947518307908646 535 2022576096908274 536 2100455210241460 537 2181259079849539 538 2265094850589371 539 2352073481889181 540 2442309909150985 541 2535923153282306 542 2633036492369511 543 2733777579729661 544 2838278626461089 545 2946676528593472 546 3059113061298019 547 3175735015729495 548 3296694405611357 549 3422148614543275 550 3552260615701340 551 3687199130317571 552 3827138861423919 553 3972260664233516 554 4122751794796820 555 4278806093212391 556 4440624248089908 557 4608413993453964 558 4782390390123419 559 4962776037201979 560 5149801371419728 561 5343704894324345 562 5544733490672969 563 5753142672375331 564 5969196917255187 565 6193169930838670 566 6425345006751036 567 6666015307686853 568 6915484248755128 569 7174065798910865 570 7442084888825830 571 7719877734114025 572 8007792269251343 573 8306188494199430 574 8615438935965431 575 8935929020177576 576 9268057562162856 577 9612237165097476 578 9968894742441514 579 10338471944589035 580 10721425714577315 581 11118228745120543 582 11529370069839205 583 11955355552648305 584 12396708516717255 585 12853970268522769 586 13327700766856180 587 13818479183821831 588 14326904616567677 589 14853596687620542 590 15399196302003750 591 15964366289679150 592 16549792210839662 593 17156183043216385 594 17784272038745037 595 18434817458633302 596 19108603484598650 597 19806441005018557 598 20529168584099941 599 21277653302442590 600 22052791787954727 601 22855511114330919 602 23686769897560008 603 24547559256298890 604 25438903978009390 605 26361863545246012 606 27317533375979894 607 28307045920027915 608 29331571978175265 609 30392321873517284 610 31490546854236215 611 32627540344695637 612 33804639437307575 613 35023226228477813 614 36284729405100275 615 37590625671066940 616 38942441434213231 617 40341754329218864 618 41790195011496849 619 43289448782625060 620 44841257497810351 621 46447421300691393 622 48109800651369963 623 49830318177588259 624 51610960831068760 625 53453781862453685 626 55360903113902132 627 57334517125976025 628 59376889574868760 629 61490361519650130 630 63677351993367184 631 65940360399524648 632 68281969266567061 633 70704846803383014 634 73211749827204116 635 75805526488226385 636 78489119381939474 637 81265568453522894 638 84138014305985677 639 87109701296036292 640 90183981050036430 641 93364315763445261 642 96654281937724246 643 100057573896135431 644 103578007755194292 645 107219525170799418 646 110986197558594179 647 114882230084920675 648 118911966151738594 649 123079891647716410 650 127390639713957258 651 131848995271914462 652 136459900087078780 653 141228457591062675 654 146159938261898020 655 151259784758617900 656 156533617637556102 657 161987240819341526 658 167626647661690494 659 173458026779551517 660 179487768496590876 661 185722471040409135 662 192168947395862580 663 198834231899101131 664 205725587517169848 665 212850512865646143 666 220216749940954379 667 227832291587796373 668 235705389711762579 669 243844563224866233 670 252258606767608530 671 260956599162194548 672 269947912675495042 673 279242222011219240 674 288849514146647825 675 298780097897487031 676 309044614363110005 677 319654047099378099 678 330619733209792203 679 341953374163590849 680 353667047571949145 681 365773218691506962 682 378284752926993344 683 391214928062243359 684 404577447533699209 685 418386453433393303 686 432656540599909850 687 447402770441112072 688 462640685891798905 689 478386326106275851 690 494656242335531473 691 511467513542630006 692 528837763254801621 693 546785176158476226 694 565328515984855148 695 584487143144217692 696 604281033707697866 697 624730798143925911 698 645857701462860171 699 667683683122293910 700 690231378403346887 701 713524139557768387 702 737586058489553130 703 762441989218046830 704 788117571943898446 705 814639256908186352 706 842034329925398921 707 870330937722892733 708 899558115029236390 709 929745811483156384 710 960924920370107310 711 993127307195935130 712 1026385840169832028 713 1060734420542868688 714 1096208014942095452 715 1132842687579841065 716 1170675634549129191 717 1209745218016735750 718 1250091002596390544 719 1291753791644479951 720 1334775665835189563 721 1379200021684554843 722 1425071612458196301 723 1472436589057702669 724 1521342543399049465 725 1571838551802355425 726 1623975220988075860 727 1677804734119243652 728 1733380899570261850 729 1790759199780422570 730 1849996842958955538 731 1911152814917036561 732 1974287933883241918 733 2039464905490814965 734 2106748380886921316 735 2176205015063258462 736 2247903528452925969 737 2321914768802500967 738 2398311776462631111 739 2477169850010995980 740 2558566615453709395 741 2642582095821826161 742 2729298784512982762 743 2818801719096047045 744 2911178559036774940 745 3006519663958558153 746 3104918176008950746 747 3206470102839954717 748 3311274404886818146 749 3419433083345486440 750 3531051272651889171 751 3646237333749952832 752 3765102952075085227 753 3887763236424270619 754 4014336822764658962 755 4144945979034094338 756 4279716715115359889 757 4418778893914104625 758 4562266347857689591 759 4710316996618684778 760 4863072970517516356 761 5020680735279653758 762 5183291222744277569 763 5351059963065222267 764 5524147223149630738 765 5702718146737547880 766 5886942901018431942 767 6076996825047900598 768 6273060585016876364 769 6475320331489854875 770 6683967863827216669 771 6899200796758444647 772 7121222734486258176 773 7350243447136123603 774 7586479055102390932 775 7830152215945903033 776 8081492319572708609 777 8340735686185595982 778 8608125772919097571 779 8883913383483740680 780 9168356886917918968 781 9461722439599512204 782 9764284216811112915 783 10076324647833480926 784 10398134661059565010 785 10730013932923167653 786 11072271147340375040 787 11425224259268983666 788 11789200769298264397 789 12164538002681306601 790 12551583399939881247 791 12950694812257722578 792 13362240809017737810 793 13786600990493836104 794 14224166313287626376 795 14675339421310936983 796 15140534990142967441 797 15620180077349676642 798 16114714486841461036 799 16624591139633845295 800 17150276459344459969 801 17692250764563284077 802 18251008676690952339 803 18827059535150389111 804 19420927828837577733 805 20033153635474843471 806 20664293078014313673 807 21314918789507757305 808 21985620395877171737 809 22677005007750880216 810 23389697731096552527 811 24124342187553549738 812 24881601054504864669 813 25662156615523024619 814 26466711331544540283 815 27295988423134569751 816 28150732474521987222 817 29031710049482198162 818 29939710330086344089 819 30875545768103760418 820 31840052760420920786 821 32834092337968256164 822 33858550879875000947 823 34914340842035503753 824 36002401512178079441 825 37123699780305319148 826 38279230936974741930 827 39470019487968749698 828 40697119998214046158 829 41961617953166266014 830 43264630650926500830 831 44607308112965146439 832 45990834027134023623 833 47416426710496069909 834 48885340106082537087 835 50398864800746674995 836 51958329078669446805 837 53565099997318379324 838 55220584500869371781 839 56926230557518408102 840 58683528336163372864 841 60494011408493695419 842 62359257992456527198 843 64280892222739809896 844 66260585464739179204 845 68300057657245019407 846 70401078700832450810 847 72565469876770449952 848 74795105313968503727 849 77091913488348249140 850 79457878772705019102 851 81895043021010807438 852 84405507205789367202 853 86991433092061991085 854 89655044967082072013 855 92398631408894776242 856 95224547113539533654 857 98135214763461867045 858 101133126957572958985 859 104220848185035551085 860 107401016863858858892 861 110676347425883402322 862 114049632469896407275 863 117523744963952852450 864 121101640519323910190 865 124786359716622898957 866 128581030507237359132 867 132488870670082011134 868 136513190347523405501 869 140657394639947134704 870 144924986283565947030 871 149319568390375445761 872 153844847275631443673 873 158504635351180546285 874 163302854110810933250 875 168243537185370744808 876 173330833494641740527 877 178569010473110120167 878 183962457397473710840 879 189515688792410340532 880 195233347943317377898 881 201120210491920755657 882 207181188144364740287 883 213421332467031696185 884 219845838800638181221 885 226460050267195516531 886 233269461901337771761 887 240279724879934294040 888 247496650882479840254 889 254926216555484792748 890 262574568114385653068 891 270448026055491014399 892 278553090012534475247 893 286896443729632200904 894 295484960186304696748 895 304325706845618157308 896 313425951062233664639 897 322793165620664232785 898 332435034441683689150 899 342359458426421426989 900 352574561477283266770 901 363088696664440607684 902 373910452578268917528 903 385048659835672365373 904 396512397781946734070 905 408311001355301287488 906 420454068157007419655 907 432951465693451589974 908 445813338834425020250 909 459050117453070724529 910 472672524293218903838 911 486691583028663371866 912 501118626561557762855 913 515965305523588301492 914 531243597028603423911 915 546965813639447075883 916 563144612599215529367 917 579793005288763704957 918 596924366962274578942 919 614552446721767837505 920 632691377784014328798 921 651355687999768590143 922 670560310680481579723 923 690320595691431174906 924 710652320868187970550 925 731571703714349521135 926 753095413439281183173 927 775240583292778236589 928 798024823257255848716 929 821466233053352720178 930 845583415521489445283 931 870395490334208138965 932 895922108103840754064 933 922183464839259708736 934 949200316818318232188 935 976993995828651239520 936 1005586424845577179170 937 1035000134098658070041 938 1065258277597870538165 939 1096384650069818325695 940 1128403704377211603586 941 1161340569370907932626 942 1195221068250093551037 943 1230071737378733121902 944 1265919845636307613832 945 1302793414249789599067 946 1340721237187384144448 947 1379732902059798004843 948 1419858811612163325998 949 1461130205751161158714 950 1503579184193165900744 951 1547238729676727619880 952 1592142731827984126128 953 1638326011621085459563 954 1685824346525092658272 955 1734674496278168768055 956 1784914229383501181719 957 1836582350266499531032 958 1889718727190770619831 959 1944364320871137048280 960 2000561213884373565420 961 2058352640814620930434 962 2117783019237442638163 963 2178897981478170614354 964 2241744407251892329255 965 2306370457119410868214 966 2372825606870039820057 967 2441160682764222141250 968 2511427897750475979235 969 2583680888588310598220 970 2657974753995364189331 971 2734366093749063238486 972 2812913048864940059069 973 2893675342780539286152 974 2976714323671080952030 975 3062093007824442148822 976 3149876124205777073084 977 3240130160137975784204 978 3332923408232584988683 979 3428326014496007118928 980 3526410027750066989095 981 3627249450290383255610 982 3730920289926236302082 983 3837500613324003169940 984 3947070600802622112259 985 4059712602501772667541 986 4175511196076185448951 987 4294553245835393658069 988 4416927963487445717532 989 4542726970404536404661 990 4672044361574369059620 991 4804976771153838689703 992 4941623439794342903510 993 5082086283653961176429 994 5226469965271476766125 995 5374881966216159672905 996 5527432661694162165073 997 5684235397024117119000 998 5845406566168892068611 999 6011065692234788016460 1000 6181335510131432340019