0 1 1 1 2 1 3 2 4 2 5 2 6 3 7 4 8 4 9 6 10 8 11 9 12 11 13 14 14 16 15 19 16 23 17 27 18 32 19 38 20 45 21 53 22 62 23 72 24 84 25 97 26 112 27 130 28 150 29 172 30 199 31 228 32 260 33 298 34 340 35 386 36 440 37 500 38 566 39 642 40 727 41 820 42 926 43 1044 44 1174 45 1321 46 1484 47 1664 48 1866 49 2090 50 2337 51 2613 52 2918 53 3254 54 3628 55 4041 56 4495 57 4999 58 5554 59 6164 60 6839 61 7581 62 8395 63 9294 64 10280 65 11361 66 12551 67 13855 68 15282 69 16850 70 18566 71 20441 72 22497 73 24744 74 27196 75 29880 76 32809 77 36002 78 39490 79 43292 80 47432 81 51947 82 56862 83 62208 84 68030 85 74360 86 81237 87 88716 88 96838 89 105652 90 115226 91 125611 92 136869 93 149082 94 162316 95 176648 96 192177 97 208987 98 227174 99 246858 100 268145 101 291153 102 316029 103 342904 104 371926 105 403273 106 437107 107 473611 108 513002 109 555480 110 601271 111 650637 112 703827 113 761116 114 822824 115 889257 116 960751 117 1037694 118 1120462 119 1209466 120 1305175 121 1408049 122 1518590 123 1637364 124 1764934 125 1901911 126 2048978 127 2206820 128 2376180 129 2557882 130 2752759 131 2961710 132 3185730 133 3425828 134 3683092 135 3958721 136 4253934 137 4570046 138 4908498 139 5270764 140 5658429 141 6073222 142 6516922 143 6991436 144 7498838 145 8041270 146 8621022 147 9240580 148 9902516 149 10609580 150 11364746 151 12171098 152 13031932 153 13950802 154 14931402 155 15977675 156 17093862 157 18284382 158 19553944 159 20907606 160 22350645 161 23888678 162 25527728 163 27274088 164 29134450 165 31115979 166 33226166 167 35472976 168 37864920 169 40410908 170 43120405 171 46003510 172 49070806 173 52333526 174 55803642 175 59493709 176 63417039 177 67587810 178 72020896 179 76732060 180 81738071 181 87056529 182 92706078 183 98706528 184 105078684 185 111844571 186 119027567 187 126652237 188 134744570 189 143332132 190 152443891 191 162110481 192 172364371 193 183239686 194 194772498 195 207001013 196 219965387 197 233708051 198 248273916 199 263710190 200 280066733 201 297396283 202 315754285 203 335199268 204 355793106 205 377600851 206 400691141 207 425136501 208 451013178 209 478401594 210 507386678 211 538057711 212 570508835 213 604839412 214 641153894 215 679562378 216 720181009 217 763131875 218 808543614 219 856551874 220 907299228 221 960935843 222 1017620008 223 1077518070 224 1140805182 225 1207665892 226 1278294117 227 1352893978 228 1431680458 229 1514879426 230 1602728562 231 1695478095 232 1793390892 233 1896743478 234 2005826878 235 2120946764 236 2242424593 237 2370598566 238 2505823846 239 2648473828 240 2798941228 241 2957638383 242 3124998682 243 3301477786 244 3487554046 245 3683730094 246 3890534221 247 4108520937 248 4338272736 249 4580401666 250 4835550034 251 5104392381 252 5387637271 253 5686028154 254 6000345598 255 6331409304 256 6680079167 257 7047257793 258 7433892774 259 7840977984 260 8269556401 261 8720722689 262 9195624767 263 9695466970 264 10221512990 265 10775087745 266 11357580931 267 11970450369 268 12615224222 269 13293504994 270 14006973325 271 14757390609 272 15546603513 273 16376548264 274 17249253744 275 18166846579 276 19131555991 277 20145717447 278 21211778378 279 22332303696 280 23509980045 281 24747622249 282 26048179585 283 27414740716 284 28850540976 285 30358969477 286 31943574835 287 33608073402 288 35356357308 289 37192501112 290 39120771077 291 41145634285 292 43271766342 293 45504061828 294 47847644638 295 50307876863 296 52890370583 297 55600999596 298 58445909628 299 61431531660 300 64564595201 301 67852140024 302 71301531220 303 74920474220 304 78717028270 305 82699623417 306 86877077512 307 91258611670 308 95853869422 309 100672935972 310 105726355887 311 111025154700 312 116580860720 313 122405525234 314 128511746898 315 134912696399 316 141622139508 317 148654464632 318 156024710670 319 163748593326 320 171842536175 321 180323702156 322 189210023560 323 198520237052 324 208273919282 325 218491520997 326 229194406534 327 240404894072 328 252146294398 329 264442955450 330 277320307762 331 290804908506 332 304924491720 333 319708019592 334 335185732468 335 351389205454 336 368351406282 337 386106752050 338 404691172984 339 424142177732 340 444498917656 341 465802258658 342 488094854840 343 511421221286 344 535827814972 345 561363117805 346 588077718974 347 616024406078 348 645258258684 349 675836741482 350 707819806843 351 741270000216 352 776252565442 353 812835560132 354 851089974386 355 891089849735 356 932912408932 357 976638189630 358 1022351178620 359 1070138957830 360 1120092854743 361 1172308093840 362 1226883960780 363 1283923971590 364 1343536043448 365 1405832679203 366 1470931157648 367 1538953726004 368 1610027807232 369 1684286213960 370 1761867365277 371 1842915519600 372 1927581015114 373 2016020513816 374 2108397263032 375 2204881365517 376 2305650054059 377 2410887985092 378 2520787541992 379 2635549143944 380 2755381575451 381 2880502326805 382 3011137941344 383 3147524385100 384 3289907428920 385 3438543038643 386 3593697789675 387 3755649295720 388 3924686646964 389 4101110874934 390 4285235433293 391 4477386689769 392 4677904447227 393 4887142482650 394 5105469099216 395 5333267710131 396 5570937442675 397 5818893757509 398 6077569102630 399 6347413590128 400 6628895690575 401 6922502965325 402 7228742824489 403 7548143305178 404 7881253891310 405 8228646362219 406 8590915664559 407 8968680829793 408 9362585923950 409 9773301024120 410 10201523244885 411 10647977800957 412 11113419100415 413 11598631892626 414 12104432456840 415 12631669825603 416 13181227068191 417 13754022619663 418 14351011649430 419 14973187495800 420 15621583151549 421 16297272794337 422 17001373389689 423 17735046350954 424 18499499250154 425 19295987608548 426 20125816750917 427 20990343717447 428 21890979263192 429 22829189928846 430 23806500176458 431 24824494621543 432 25884820344887 433 26989189277480 434 28139380691634 435 29337243781002 436 30584700322969 437 31883747457993 438 33236460568066 439 34644996247886 440 36111595404790 441 37638586469231 442 39228388709464 443 40883515688014 444 42606578841432 445 44400291176938 446 46267471125333 447 48211046531334 448 50234058774840 449 52339667064552 450 54531152884590 451 56811924587737 452 59185522178810 453 61655622268232 454 64226043189784 455 66900750327954 456 69683861634695 457 72579653329838 458 75592565832550 459 78727209903592 460 81988372992686 461 85381025840781 462 88910329316754 463 92581641483000 464 96400524942360 465 100372754445508 466 104504324753743 467 108801458812270 468 113270616212744 469 117918501940674 470 122752075465376 471 127778560151217 472 133005452986316 473 138440534689158 474 144091880172022 475 149967869357856 476 156077198414213 477 162428891383287 478 169032312205210 479 175897177201716 480 183033567999200 481 190451944889255 482 198163160697353 483 206178475138736 484 214509569660814 485 223168562846296 486 232168026356509 487 241521001415449 488 251241015912528 489 261342102104184 490 271838814916008 491 282746250927663 492 294080068021489 493 305856505697642 494 318092406142856 495 330805236034301 496 344013109083125 497 357734809409687 498 371989815732684 499 386798326378936 500 402181285210723 501 418160408454219 502 434758212437951 503 451998042343466 504 469904101953422 505 488501484408221 506 507816204079381 507 527875229546561 508 548706517691862 509 570339049026162 510 592802864236149 511 616129101968779 512 640350037974789 513 665499125601970 514 691611037658520 515 718721709775243 516 746868385259961 517 776089661468353 518 806425537827512 519 837917465508926 520 870608398779069 521 904542848172359 522 939766935486783 523 976328450634762 524 1014276910503360 525 1053663619827817 526 1094541734116321 527 1136966324789953 528 1180994446545910 529 1226685206988110 530 1274099838699297 531 1323301773767915 532 1374356720820398 533 1427332744744010 534 1482300349119514 535 1539332561421193 536 1598505021181685 537 1659896071147396 538 1723586851489654 539 1789661397282534 540 1858206739280055 541 1929313008066839 542 2003073541807402 543 2079584997634580 544 2158947466761242 545 2241264593555505 546 2326643698629093 547 2415195906033878 548 2507036274823076 549 2602283935037112 550 2701062228220879 551 2803498852746868 552 2909726014015524 553 3019880579652380 554 3134104239996182 555 3252543673961617 556 3375350720410764 557 3502682555348648 558 3634701875040036 559 3771577085198004 560 3913482496582057 561 4060598527118536 562 4213111910711640 563 4371215913107038 564 4535110554938406 565 4705002842144343 566 4881107004144440 567 5063644739923968 568 5252845472235712 569 5448946610337074 570 5652193821432563 571 5862841311054012 572 6081152112828098 573 6307398387824192 574 6541861733741262 575 6784833504417101 576 7036615139878828 577 7297518507221982 578 7567866252838126 579 7847992166238706 580 8138241555793561 581 8438971636944224 582 8750551933171298 583 9073364690068410 584 9407805303126798 585 9754282759544167 586 10113220094448296 587 10485054862186922 588 10870239623035238 589 11269242445753586 590 11682547426697896 591 12110655225876332 592 12554083620430614 593 13013368076299930 594 13489062338507658 595 13981739040599074 596 14491990334048856 597 15020428538129642 598 15567686810824302 599 16134419841667254 600 16721304567061656 601 17329040908715554 602 17958352536154216 603 18609987653916562 604 19284719814145354 605 19983348755605928 606 20706701269809210 607 21455632095021208 608 22231024839278120 609 23033792933157558 610 23864880613166977 611 24725263936960934 612 25615951831219240 613 26537987173133546 614 27492447906814876 615 28480448195543123 616 29503139610901342 617 30561712360216728 618 31657396553326870 619 32791463509818660 620 33965227108280237 621 35180045178692162 622 36437320939219290 623 37738504479072490 624 39085094288684764 625 40478638838587419 626 41920738208796236 627 43413045770081490 628 44957269918643184 629 46555175866155116 630 48208587486692475 631 49919389222213556 632 51689528048726030 633 53521015504806506 634 55415929784307614 635 57376417895563779 636 59404697888933964 637 61503061154693828 638 63673874793785220 639 65919584063447156 640 68242714899934711 641 70645876521048756 642 73131764110703420 643 75703161587949692 644 78362944463412364 645 81114082785588233 646 83959644179656364 647 86902796982011992 648 89946813473213644 649 93095073212248372 650 96351066475602881 651 99718397804094961 652 103200789660647106 653 106802086202790604 654 110526257173144236 655 114377401911351095 656 118359753491589647 657 122477682989219198 658 126735703880372276 659 131138476578967314 660 135690813115046105 661 140397681958608369 662 145264212993805080 663 150295702647770794 664 155497619178660404 665 160875608128173479 666 166435497943257615 667 172183305771984384 668 178125243439339512 669 184267723608067954 670 190617366130033433 671 197181004594333925 672 203965693077803193 673 210978713103865972 674 218227580816532566 675 225720054375695847 676 233464141580253147 677 241468107726430189 678 249740483708051194 679 258290074365882794 680 267125967094071321 681 276257540711052293 682 285694474602718409 683 295446758146564368 684 305524700424879612 685 315938940235492071 686 326700456409542139 687 337820578445111831 688 349310997465992966 689 361183777515901444 690 373451367197783179 691 386126611668346821 692 399222764999029993 693 412753502913938368 694 426732935915820302 695 441175622812261005 696 456096584653610043 697 471511319094714249 698 487435815193702240 699 503886568660396274 700 520880597567521039 701 538435458539111587 702 556569263429851671 703 575300696509706400 704 594649032169508686 705 614634153162487459 706 635276569397402585 707 656597437300311529 708 678618579761323614 709 701362506683422898 710 724852436151867631 711 749112316242011995 712 774166847484170775 713 800041506005646434 714 826762567369385688 715 854357131129559868 716 882853146125940773 717 912279436538302103 718 942665728722960798 719 974042678855234258 720 1006441901400960004 721 1039895998441172263 722 1074438589875779433 723 1110104344531472994 724 1146929012200115668 725 1184949456635697962 726 1224203689537360857 727 1264730905547072385 728 1306571518292485506 729 1349767197504940474 730 1394360907243741390 731 1440396945259883571 732 1487920983531873945 733 1536980110007536274 734 1587622871587855310 735 1639899318388412210 736 1693861049315305553 737 1749561258994735490 738 1807054786094965220 739 1866398163080816816 740 1927649667443268404 741 1990869374446303643 742 2056119211434713406 743 2123463013749095964 744 2192966582293940584 745 2264697742806340722 746 2338726406875578217 747 2415124634763517816 748 2493966700077534884 749 2575329156350554046 750 2659290905582539662 751 2745933268799697343 752 2835340058690668742 753 2927597654378839676 754 3022795078391946004 755 3121024075893362736 756 3222379196239386177 757 3326957876929038668 758 3434860530016317828 759 3546190631054833994 760 3661054810647165136 761 3779562948674858431 762 3901828271285135850 763 4027967450712926226 764 4158100708020669686 765 4292351918838584624 766 4430848722190849221 767 4573722632497210134 768 4721109154839904784 769 4873147903588759292 770 5029982724481636102 771 5191761820257926471 772 5358637879945986434 773 5530768211909997194 774 5708314880762416196 775 5891444848251631866 776 6080330118239310929 777 6275147885882790526 778 6476080691141578102 779 6683316576732213732 780 6897049250656806674 781 7117478253434557359 782 7344809130171103433 783 7579253607601800364 784 7821029776249358884 785 8070362277842147086 786 8327482498140976529 787 8592628765326837623 788 8866046554108320754 789 9147988695709235304 790 9438715593901943026 791 9738495447258610843 792 10047604477794650891 793 10366327166184007814 794 10694956493733091224 795 11033794191302526244 796 11383150995371709545 797 11743346911448775925 798 12114711485031298298 799 12497584080329315776 800 12892314166970414812 801 13299261614909685021 802 13718796997774133849 803 14151301904879826312 804 14597169262163528256 805 15056803662277920839 806 15530621704108733179 807 16019052341976103039 808 16522537244790334072 809 17041531165442140998 810 17576502320711925771 811 18127932781991105541 812 18696318877119124251 813 19282171603644766088 814 19886017053829536274 815 20508396851722222461 816 21149868602639323967 817 21811006355395902067 818 22492401077643546300 819 23194661144678366734 820 23918412842092561181 821 24664300882656106273 822 25432988937822030413 823 26225160184260201722 824 27041517865838487984 825 27882785871477807561 826 28749709329319971487 827 29643055217662131635 828 30563612993120131846 829 31512195236496419300 830 32489638316844151159 831 33496803074228509293 832 34534575521700649549 833 35603867567016834376 834 36705617754645650780 835 37840792028621762223 836 39010384516823001687 837 40215418337259022093 838 41456946426976490510 839 42736052394205503332 840 44053851394384451147 841 45411491030718657673 842 46810152279949237355 843 48251050444022409140 844 49735436128369031324 845 51264596247526777269 846 52839855058852516855 847 54462575225093535881 848 56134158906610534162 849 57856048884061955940 850 59629729712381931083 851 61456728906910199305 852 63338618162550589318 853 65277014606859139374 854 67273582087990962132 855 69330032498454872983 856 71448127135651250935 857 73629678100198682746 858 75876549733076718792 859 78190660092640607832 860 80573982472596178923 861 83028546962046837821 862 85556442048755432326 863 88159816266798432728 864 90840879889815862696 865 93601906671093624149 866 96445235631752129951 867 99373272898343513912 868 102388493591195507592 869 105493443764880121502 870 108690742402216180907 871 111983083463253407841 872 115373237990728774978 873 118864056273519537272 874 122458470069659032610 875 126159494890527586507 876 129970232347867535848 877 133893872565316348622 878 137933696656201516872 879 142093079269380826108 880 146375491204960093719 881 150784502101773896356 882 155323783198558236096 883 159997110170796388602 884 164808366045276617778 885 169761544194447653673 886 174860751412714230488 887 180110211076876737664 888 185514266392970339048 889 191077383731819742158 890 196804156055692196311 891 202699306438487024936 892 208767691681965589448 893 215014306030596976042 894 221444284987655203890 895 228062909235274475763 896 234875608661245770456 897 241887966495403741482 898 249105723558529138302 899 256534782626774541772 900 264181212914692435407 901 272051254680026848944 902 280151323953518620228 903 288488017397051559908 904 297068117293555444724 905 305898596672177278833 906 314986624572315992948 907 324339571450211309148 908 333965014731880229404 909 343870744516285344050 910 354064769432722159005 911 364555322656523144024 912 375350868087274497380 913 386460106693852644324 914 397891983030706357312 915 409655691929916823513 916 421760685373687650532 917 434216679552044668764 918 447033662110640613020 919 460221899593688740800 920 473791945087186987047 921 487754646067718962512 922 502121152462257094486 923 516902924924541163098 924 532111743333740420160 925 547759715521257248522 926 563859286231689483688 927 580423246324114471082 928 597464742220019310180 929 614997285604372961440 930 633034763386493714422 931 651591447927539394392 932 670682007541631877876 933 690321517277798105554 934 710525469990097117084 935 731309787703500770528 936 752690833283280222092 937 774685422415852055308 938 797310835909251087918 939 820584832321596163468 940 844525660926132621824 941 869152075021664424104 942 894483345597404194036 943 920539275361503584914 944 947340213142773026420 945 974907068675332427328 946 1003261327776186599256 947 1032425067925984477964 948 1062420974263472303918 949 1093272356004422526930 950 1125003163296105577105 951 1157638004518642727944 952 1191202164044870757656 953 1225721620470656071890 954 1261223065327888568646 955 1297733922292700456945 956 1335282366901785410040 957 1373897346790009225264 958 1413608602462842244312 959 1454446688617498914908 960 1496442996027010604429 961 1539629774001822840584 962 1584040153443890105040 963 1629708170508608878452 964 1676668790890322644132 965 1724957934747543337587 966 1774612502284430196380 967 1825670400005490015250 968 1878170567660904582676 969 1932153005900318635292 970 1987658804653377012133 971 2044730172255774781476 972 2103410465340045117678 973 2163744219510799774206 974 2225777180824647903992 975 2289556338095515953043 976 2355129956046618760114 977 2422547609330881381394 978 2491860217442146826192 979 2563120080540072436178 980 2636380916212208371309 981 2711697897197328956238 982 2789127690094698322990 983 2868728495084586944718 984 2950560086685977710126 985 3034683855578057222547 986 3121162851512770913462 987 3210061827346390738384 988 3301447284218751074098 989 3395387517909542642794 990 3491952666401776197855 991 3591214758683288099658 992 3693247764817949219020 993 3798127647319016130152 994 3905932413857881481640 995 4016742171342328928033 996 4130639181399235320022 997 4247707917297542581154 998 4368035122348233769112 999 4491709869818949400186 1000 4618823624401826233473