0 1 1 0 2 3 3 4 4 4 5 4 6 7 7 12 8 13 9 16 10 22 11 28 12 38 13 44 14 55 15 72 16 83 17 104 18 129 19 156 20 187 21 220 22 273 23 328 24 384 25 452 26 539 27 652 28 757 29 880 30 1041 31 1220 32 1428 33 1652 34 1924 35 2244 36 2585 37 2992 38 3458 39 3992 40 4581 41 5244 42 6053 43 6936 44 7910 45 9024 46 10303 47 11784 48 13380 49 15176 50 17257 51 19584 52 22188 53 25068 54 28354 55 32052 56 36111 57 40712 58 45858 59 51604 60 57974 61 65040 62 73071 63 81944 64 91714 65 102612 66 114796 67 128400 68 143295 69 159816 70 178274 71 198684 72 221246 73 246080 74 273689 75 304244 76 337754 77 374872 78 415862 79 461036 80 510671 81 565276 82 625748 83 692104 84 764834 85 844816 86 932877 87 1029772 88 1135589 89 1251680 90 1379375 91 1519216 92 1672316 93 1839716 94 2023303 95 2224280 96 2443560 97 2683552 98 2945959 99 3232596 100 3545196 101 3886268 102 4259295 103 4665748 104 5108316 105 5590816 106 6116932 107 6690344 108 7313503 109 7991672 110 8730414 111 9533688 112 10406688 113 11355008 114 12386249 115 13506520 116 14721773 117 16041512 118 17473969 119 19027920 120 20712309 121 22538140 122 24518963 123 26664472 124 28987160 125 31502692 126 34227072 127 37176424 128 40365187 129 43814456 130 47546406 131 51580672 132 55940248 133 60649812 134 65739245 135 71236164 136 77168638 137 83573544 138 90486452 139 97944676 140 105987517 141 114660172 142 124014143 143 134094960 144 144955368 145 156656384 146 169261982 147 182838092 148 197449415 149 213176720 150 230105566 151 248318540 152 267907916 153 288973068 154 311626264 155 335978772 156 362146681 157 390266992 158 420479078 159 452929556 160 487773175 161 525182284 162 565346605 163 608449332 164 654693930 165 704306820 166 757526619 167 814602692 168 875790114 169 941382816 170 1011693109 171 1087036432 172 1167755780 173 1254219636 174 1346831859 175 1446004904 176 1552173495 177 1665825792 178 1787468222 179 1917635192 180 2056892446 181 2205855808 182 2365191879 183 2535573592 184 2717730524 185 2912458164 186 3120597379 187 3343030692 188 3580677908 189 3834558200 190 4105752493 191 4395377340 192 4704631568 193 5034795832 194 5387251756 195 5763433396 196 6164855101 197 6593173144 198 7050122995 199 7537535596 200 8057350157 201 8611652384 202 9202674851 203 9832721264 204 10504260488 205 11219947940 206 11982592957 207 12795152160 208 13660727743 209 14582686560 210 15564594606 211 16610171780 212 17723384478 213 18908452776 214 20169885038 215 21512398192 216 22940975335 217 24460982392 218 26078065285 219 27798180400 220 29627627521 221 31573131640 222 33641847158 223 35841230440 224 38179219120 225 40664283572 226 43305375025 227 46111923784 228 49093852747 229 52261797696 230 55627007174 231 59201272048 232 62997102318 233 67027765864 234 71307356004 235 75850664996 236 80673311112 237 85791961224 238 91224168730 239 96988443124 240 103104333888 241 109592599056 242 116475233721 243 123775271856 244 131517122334 245 139726697876 246 148431348921 247 157659881200 248 167442626399 249 177811855832 250 188801638056 251 200447755756 252 212788051348 253 225862543608 254 239713581976 255 254385670232 256 269925737514 257 286383580640 258 303811636813 259 322265142872 260 341802355212 261 362484905616 262 384377901418 263 407549661948 264 432072360868 265 458022331140 266 485480031394 267 514530144544 268 545261798804 269 577769368640 270 612152324092 271 648515179792 272 686968198546 273 727627716860 274 770616499249 275 816063567660 276 864104797376 277 914883798640 278 968551684922 279 1025267465076 280 1085198583093 281 1148521703568 282 1215423030343 283 1286098040752 284 1360752762044 285 1439604497060 286 1522881961830 287 1610825658904 288 1703688498978 289 1801737374936 290 1905253166516 291 2014530904124 292 2129881220756 293 2251631224764 294 2380125359549 295 2515725427104 296 2658811942665 297 2809785953312 298 2969069014221 299 3137104201280 300 3314357432916 301 3501319207068 302 3698505556193 303 3906458066692 304 4125746465884 305 4356970374824 306 4600760045219 307 4857777495092 308 5128718174031 309 5414314159176 310 5715334789199 311 6032587599912 312 6366921416770 313 6719228563944 314 7090447009655 315 7481561195864 316 7893605123324 317 8327666238584 318 8784886314474 319 9266464009156 320 9773658098815 321 10307791400300 322 10870253383033 323 11462501379076 324 12086066003964 325 12742555319552 326 13433657354287 327 14161143281732 328 14926871635962 329 15732795040664 330 16580962805398 331 17473524066468 332 18412734575476 333 19400962160080 334 20440692011365 335 21534530019828 336 22685209878169 337 23895601542472 338 25168714946745 339 26507706412676 340 27915886403405 341 29396728512828 342 30953876306778 343 32591148092816 344 34312548624330 345 36122278957488 346 38024743679429 347 40024559341624 348 42126564849260 349 44335835925592 350 46657693136381 351 49097710891396 352 51661732530750 353 54355883600748 354 57186584767228 355 60160561905208 356 63284862552298 357 66566874659784 358 70014337967291 359 73635359824880 360 77438433598994 361 81432459272012 362 85626760749376 363 90031100216080 364 94655703804504 365 99511284797912 366 104609062749062 367 109960784782812 368 115578750675259 369 121475844544152 370 127665556670337 371 134162007279264 372 140979980420698 373 148134955532700 374 155643138580871 375 163521489286804 376 171787759028311 377 180460532865384 378 189559260342692 379 199104293650116 380 209116930850994 381 219619463048256 382 230635216699270 383 242188592157152 384 254305120606600 385 267011518001104 386 280335733095163 387 294306999520932 388 308955894992382 389 324314411526152 390 340416010933786 391 357295684212304 392 374990027924360 393 393537318050196 394 412977583631914 395 433352675656580 396 454706353856243 397 477084380980064 398 500534600743354 399 525107028113716 400 550853949330191 401 577830029420776 402 606092413037861 403 635700821108588 404 666717677722710 405 699208234106448 406 733240684625881 407 768886290752664 408 806219518415498 409 845318193936560 410 886263639045239 411 929140813767092 412 974038487989758 413 1021049411669864 414 1070270486072254 415 1121802930301732 416 1175752478445054 417 1232229590566808 418 1291349640979364 419 1353233128006480 420 1418005902361384 421 1485799409962336 422 1556750927017046 423 1631003792119628 424 1708707688325082 425 1790018924747700 426 1875100708752788 427 1964123434002692 428 2057264994095135 429 2154711128209256 430 2256655738702031 431 2363301225230616 432 2474858867788978 433 2591549212863092 434 2713602465068634 435 2841258877093984 436 2974769192444110 437 3114395114928432 438 3260409748825439 439 3413098077337916 440 3572757477197151 441 3739698261594876 442 3914244217103298 443 4096733143778080 444 4287517478847794 445 4486964927867940 446 4695459088668454 447 4913400107315920 448 5141205383053345 449 5379310330335768 450 5628169106997292 451 5888255377021176 452 6160063158561706 453 6444107687552488 454 6740926298668979 455 7051079315819896 456 7375151035131642 457 7713750760357544 458 8067513806223621 459 8437102571862312 460 8823207684482069 461 9226549200095100 462 9647877808193661 463 10087976057227556 464 10547659722837556 465 11027779204488132 466 11529220926836618 467 12052908807142904 468 12599805817021463 469 13170915648495656 470 13767284348660626 471 14390002026777808 472 15040204712432496 473 15719076260648120 474 16427850303470209 475 17167812240954904 476 17940301397921232 477 18746713284912272 478 19588501837268652 479 20467181786563440 480 21384331169159336 481 22341593950390544 482 23340682684112693 483 24383381236828072 484 25471547760197364 485 26607117742684832 486 27792107102294059 487 29028615415567840 488 30318829330563299 489 31665026174991256 490 33069577558882263 491 34534953129504284 492 36063724599089158 493 37658569891293756 494 39322277402689608 495 41057750375147924 496 42868011570545735 497 44756208155683704 498 46725616610151400 499 48779647888905356 500 50921852854978619 501 53155927947438416 502 55485720964852725 503 57915237015277388 504 60448644907513680 505 63090283735554736 506 65844669597814873 507 68716502597352692 508 71710674202455755 509 74832274980946544 510 78086602413441006 511 81479169024109632 512 85015711014573002 513 88702197174338228 514 92544838058845975 515 96550095440787640 516 100724692322412649 517 105075623372974912 518 109610165517788481 519 114335889024602152 520 119260669123321821 521 124392698106184140 522 129740497730991845 523 135312932015068640 524 141119220830794560 525 147168953941649408 526 153472105391388452 527 160039048472251412 528 166880571401882082 529 174007893725655032 530 181432683017582875 531 189167072238446464 532 197223678036282718 533 205615619661858184 534 214356538481726148 535 223460618116101876 536 232942605635042563 537 242817833614669080 538 253102242658621523 539 263812404901438400 540 274965548566710885 541 286579583502914012 542 298673127440646608 543 311265533118687512 544 324376916891966034 545 338028188304332164 546 352241080497663625 547 367038181806331612 548 382442968750628714 549 398479840451024336 550 415174153852608584 551 432552260300994956 552 450641543905876888 553 469470461226095048 554 489068582251095195 555 509466632748094056 556 530696538627620570 557 552791472046831304 558 575785898687061658 559 599715626977371796 560 624617859406532117 561 650531245815019392 562 677495938304287933 563 705553648013455308 564 734747704675865744 565 765123118225306100 566 796726642273259767 567 829606839995408264 568 863814152778702699 569 899400971667000560 570 936421710741648069 571 974932883255232396 572 1014993181190573698 573 1056663557590733680 574 1100007311632255083 575 1145090176595756724 576 1191980411715735955 577 1240748897523944472 578 1291469233899141769 579 1344217841975488120 580 1399074070177437352 581 1456120304243292232 582 1515442080735364348 583 1577128204460213232 584 1641270871163071230 585 1707965794480727732 586 1777312336918372610 587 1849413645688618824 588 1924376793988698029 589 2002312927793087032 590 2083337416965229040 591 2167570011927096628 592 2255135006926895388 593 2346161409011793040 594 2440783112690875844 595 2539139080603211512 596 2641373531678264070 597 2747636136277279192 598 2858082217241290485 599 2972872958577418640 600 3092175622272786357 601 3216163773085000604 602 3345017510644239261 603 3478923709581818548 604 3618076269732621548 605 3762676375035001648 606 3912932760845202480 607 4069061990981105972 608 4231288745449951193 609 4399846119025652736 610 4574975929056205939 611 4756929034394470384 612 4945965667070443198 613 5142355775524996592 614 5346379379456076010 615 5558326936887809560 616 5778499725729838763 617 6007210239196144592 618 6244782593659322190 619 6491552951559929676 620 6747869960261069933 621 7014095206733746624 622 7290603687242850936 623 7577784293252972756 624 7876040316642908530 625 8185789972423085056 626 8507466938679452614 627 8841520915822195200 628 9188418206731648842 629 9548642318172134560 630 9922694581346497773 631 10311094794511318536 632 10714381890201628776 633 11133114625576395464 634 11567872296118985158 635 12019255473855257496 636 12487886773572132625 637 12974411646346726800 638 13479499198592908232 639 14003843040619498956 640 14548162166306906862 641 15113201863964356072 642 15699734657428271833 643 16308561279493136096 644 16940511682386192362 645 17596446083023987456 646 18277256042925671530 647 18983865586116557304 648 19717232357694305126 649 20478348823870144736 650 21268243510829945460 651 22087982286965425860 652 22938669692537701428 653 23821450315050611960 654 24737510211000880944 655 25688078376181128944 656 26674428269957696694 657 27697879392956578024 658 28759798916073996023 659 29861603366984350080 660 31004760377028027657 661 32190790489024594572 662 33421269025175650265 663 34697828018661825492 664 36022158216204892794 665 37396011148991947972 666 38821201272319097334 667 40299608179373078824 668 41833178893689553405 669 43423930242012611112 670 45073951304502595044 671 46785405949492845500 672 48560535459349032050 673 50401661245750623820 674 52311187656029365045 675 54291604874585771680 676 56345491927939542839 677 58475519793435001488 678 60684454609536655647 679 62975160997388303520 680 65350605498815631474 681 67813860132438953328 682 70368106067683615100 683 73016637422961048584 684 75762865199390051564 685 78610321347527120848 686 81562662968679273627 687 84623676659721775772 688 87797283009200391402 689 91087541248304129416 690 94498654053731622737 691 98034972514019294372 692 101701001270072093136 693 105501403828959945676 694 109441008054644954310 695 113524811843036687892 696 117757988995071381661 697 122145895289426997120 698 126694074753657048034 699 131408266149130467672 700 136294409679081775596 701 141358653923871510860 702 146607363005004483461 703 152047123988894141188 704 157684754548447278108 705 163527310881048466000 706 169582095887218535055 707 175856667624865910132 708 182358848052570551093 709 189096732069173144640 710 196078696848002181368 711 203313411484604816800 712 210809846975835508448 713 218577286531706061360 714 226625336227755659574 715 234963936011479769764 716 243603371085108288998 717 252554283669984372112 718 261827685154015405273 719 271434968647095912720 720 281387921961203812854 721 291698741024262552624 722 302380043733456742691 723 313444884267347071052 724 324906767885985430014 725 336779666221052618508 726 349078033065910811822 727 361816820690839908332 728 375011496706883693802 729 388678061492728192632 730 402833066186959612721 731 417493631276970518732 732 432677465814575494090 733 448402887265375103572 734 464688842007709966706 735 481554926505871337096 736 499021409194405583993 737 517109253086490932584 738 535840139114349189415 739 555236490242636606792 740 575321496384829964487 741 596119140141584892556 742 617654223375595064038 743 639952394657202212560 744 663040177628675786944 745 686945000297412314372 746 711695225279218845365 747 737320181034953166892 748 763850194141611488494 749 791316622625984289840 750 819751890372787208863 751 849189522659825030656 752 879664182871442682908 753 911211710409452073308 754 943869159832964049023 755 977674841271956723700 756 1012668362176304969562 757 1048890670428820012960 758 1086384098844339069826 759 1125192411123180409952 760 1165360849312893952422 761 1206936182816438362316 762 1249966758979188468188 763 1294502555315607562348 764 1340595233455432940520 765 1388298194837262365248 766 1437666638192637021338 767 1488757618895467330904 768 1541630110249203175854 769 1596345066765708567480 770 1652965489468271700680 771 1711556493308155685756 772 1772185376782945230978 773 1834921693800614654596 774 1899837327850278075153 775 1967006568560842205112 776 2036506190752317135471 777 2108415536038670881792 778 2182816597032900454507 779 2259794104269847975764 780 2339435615943556987366 781 2421831610533658370092 782 2507075582388165576011 783 2595264140370917787352 784 2686497109708464998224 785 2780877637099990133236 786 2878512299175098988140 787 2979511214429879804156 788 3083988158769277600198 789 3192060684757873542000 790 3303850244652946826375 791 3419482317373484982416 792 3539086539558267490718 793 3662796840805341783836 794 3790751583209108500476 795 3923093705341662107428 796 4059970870857977985267 797 4201535621841644233280 798 4347945536997781800665 799 4499363394890635160076 800 4655957342399394115584 801 4817901068534671073088 802 4985373983749687741150 803 5158561404938961802268 804 5337654746354469630344 805 5522851716572397465044 806 5714356521673515154546 807 5912380074865510261852 808 6117140212774143788045 809 6328861918594128518952 810 6547777552254149005699 811 6774127087862160723984 812 7008158358698218487966 813 7250127309939290213132 814 7500298259334363476909 815 7758944166093808756840 816 8026346908303259566657 817 8302797569086828688104 818 8588596731732898634570 819 8884054784122846295876 820 9189492232773299743997 821 9505240026759801039708 822 9831639891780616601016 823 10169044674703955816884 824 10517818698994340083360 825 10878338131283006802544 826 11250991359389848330466 827 11636179382198104779680 828 12034316211783910128937 829 12445829288153842378896 830 12871159906897470388486 831 13310763660218270523984 832 13765110891811059459498 833 14234687165942513019212 834 14719993751139707670634 835 15221548118960128349816 836 15739884458382220897591 837 16275554206240580610000 838 16829126594117896710024 839 17401189212283879287928 840 17992348591235580536898 841 18603230801336057096112 842 19234482071039995385991 843 19886769424316627498216 844 20560781337955040081638 845 21257228419261859461348 846 21976844104722604417965 847 22720385380332814210852 848 23488633524311339748509 849 24282394872842796013696 850 25102501609439499071261 851 25949812578732498793140 852 26825214125513307267556 853 27729620959699378713296 854 28663977047966507690085 855 29629256532894057022344 856 30626464680562964688592 857 31656638857393737381784 858 32720849537001837507075 859 33820201338097947707232 860 34955834094419951771453 861 36128923957607893443760 862 37340684533929114159213 863 38592368055936639072996 864 39885266590251434292208 865 41220713282427423357984 866 42600083639947706529680 867 44024796854594842480652 868 45496317165455405514369 869 47016155263734061903464 870 48585869740485668554923 871 50207068578682263546400 872 51881410691057718297226 873 53610607504977802087200 874 55396424595686655815729 875 57240683369435266359216 876 59145262798133703238460 877 61112101206969248651032 878 63143198116430616001610 879 65240616140530506257432 880 67406482942977227855316 881 69642993252949987600284 882 71952410942139373925056 883 74337071164969874815112 884 76799382564078078316360 885 79341829542817543882824 886 81966974606694313345855 887 84677460775918814522652 888 87476014071298417362142 889 90365446075588570180776 890 93348656572347441016683 891 96428636264774120020584 892 99608469577062229467898 893 102891337540549716037912 894 106280520767099940241799 895 109779402512382787754616 896 113391471831924545499047 897 117120326832539553311624 898 120969678021773750882640 899 124943351758488217474480 900 129045293807677310672951 901 133279573002499521364924 902 137650385016530199794301 903 142162056249617863880084 904 146819047830957797916580 905 151625959742608430152536 906 156587535066876509550977 907 161708664361408080699828 908 166994390165900268250849 909 172449911644222794936080 910 178080589365669061997791 911 183891950229674044658460 912 189889692538434783552298 913 196079691221554446786472 914 202468003217065759057675 915 209060873013544178546688 916 215864738358319494945444 917 222886236136476329379624 918 230132208425390843430014 919 237609708730259645394552 920 245326008406070183520444 921 253288603271330954816028 922 261505220418959300928100 923 269983825230272206984236 924 278732628598373719884754 925 287760094366746597189092 926 297074946989163499157818 927 306686179417636546013320 928 316603061225273972323807 929 326835146970776722090000 930 337392284811264402051001 931 348284625371002185258416 932 359522630873782384900218 933 371117084546334047511692 934 383079100300497274268919 935 395420132702440781387288 936 408151987237652616162005 937 421286830880054591762352 938 434837202973725730315783 939 448816026436735692503556 940 463236619296645380759357 941 478112706567105114633568 942 493458432475151990309625 943 509288373049619835792040 944 525617549081606143781638 945 542461439467352280743476 946 559835994944373146154083 947 577757652232566485753864 948 596243348592309947188995 949 615310536811434539815272 950 634977200632989194394587 951 655261870636981584883348 952 676183640589610030423166 953 697762184273068332935308 954 720017772809575947119469 955 742971292494119767670948 956 766644263151087657373096 957 791058857029551251372512 958 816237918252236454007743 959 842204982834688828710800 960 868984299291326443514133 961 896600849844992908250672 962 925080372256963743860761 963 954449382295573253060312 964 984735196862451074975158 965 1015965957794683204425972 966 1048170656361971061747039 967 1081379158479199309911292 968 1115622230655326589468046 969 1150931566699467033866720 970 1187339815205208399417874 971 1224880607836060114286156 972 1263588588435511188167370 973 1303499442984735133165340 974 1344649930431887514233745 975 1387077914418234333244772 976 1430822395927431518659870 977 1475923546883862570649944 978 1522422744726487900001942 979 1570362607986804980942320 980 1619787032899952807990670 981 1670741231078048171985072 982 1723271768275486255778166 983 1777426604277771866476664 984 1833255133946737276753268 985 1890808229454298312606592 986 1950138283738115622659630 987 2011299255214547441277452 988 2074346713785176834351495 989 2139337888173336889908800 990 2206331714627536672954303 991 2275388887031406154886764 992 2346571908460809895064166 993 2419945144228425745987156 994 2495574876457548261961464 995 2573529360228895856196488 996 2653878881345909532916284 997 2736695815763744682501832 998 2822054690728177899773660 999 2910032247673818929086716 1000 3000707506931912669562549