0 1 1 1 2 0 3 1 4 3 5 3 6 1 7 3 8 10 9 10 10 4 11 10 12 27 13 27 14 13 15 28 16 69 17 69 18 37 19 72 20 161 21 162 22 96 23 171 24 361 25 364 26 230 27 388 28 768 29 777 30 522 31 836 32 1581 33 1605 34 1128 35 1739 36 3145 37 3203 38 2345 39 3495 40 6094 41 6225 42 4712 43 6831 44 11511 45 11794 46 9198 47 13010 48 21293 49 21875 50 17496 51 24239 52 38605 53 39763 54 32537 55 44240 56 68791 57 71024 58 59280 59 79298 60 120597 61 124791 62 106038 63 139773 64 208356 65 216048 66 186522 67 242657 68 355081 69 368905 70 323116 71 415371 72 597629 73 622005 74 551904 75 701882 76 994121 77 1036393 78 930530 79 1171768 80 1635838 81 1708023 82 1550087 83 1934437 84 2664442 85 2785993 86 2553354 87 3160115 88 4298665 89 4500703 90 4162093 91 5111919 92 6873049 93 7204899 94 6718142 95 8193029 96 10896552 97 11435582 98 10744302 99 13017371 100 17137306 101 18003882 102 17034681 103 20512752 104 26748569 105 28128311 106 26787074 107 32073153 108 41449970 109 43626966 110 41796976 111 49779155 112 63792702 113 67198456 114 64739093 115 76719083 116 97538978 117 102824460 118 99575191 119 117450315 120 148210276 121 156350879 122 152140486 123 178663763 124 223866546 125 236314826 126 230984748 127 270130729 128 336220120 129 355126102 130 348570956 131 406053522 132 502208307 133 530736522 134 522979149 135 606975380 136 746220110 137 789002800 138 780314959 139 902480411 140 1103219339 141 1167002380 142 1158104630 143 1334984319 144 1623129523 145 1717687669 146 1710057967 147 1965049802 148 2376944185 149 2516374246 150 2512730819 151 2878797734 152 3465240757 153 3669779368 154 3674805390 155 4198222903 156 5029970795 157 5328541869 158 5349979946 159 6095483017 160 7270773260 161 7704542441 162 7754803707 163 8812651716 164 10467431369 165 11094750319 166 11193284391 167 12688911170 168 15010744361 169 15914001135 170 16090723844 171 18197904296 172 21444783313 173 22739865997 174 23040114444 175 25998853346 176 30524633502 177 32373956719 178 32865558241 179 37006361910 180 43295000566 181 45925385203 182 46708725769 183 52485412635 184 61197023094 185 64924157183 186 66146379531 187 74180363688 188 86212928395 189 91474739389 190 93349718159 191 104489585244 192 121061560667 193 128463607707 194 131299835069 195 146701354135 196 169461878457 197 179838932516 198 184078343536 199 205311614259 200 236487351426 201 250986700245 202 257258390363 203 286451076679 204 329041308827 205 349235168340 206 358429510856 207 398457810682 208 456493265321 209 484530068537 210 497900444035 211 552643251161 212 631528594819 213 670336115220 214 689638152363 215 764314507167 216 871280876549 217 924838271180 218 952519582697 219 1054135908471 220 1198837424923 221 1272538749145 222 1311996770659 223 1449938290827 224 1645237177698 225 1746375994077 226 1802307011269 227 1989118460156 228 2252116159006 229 2390530168271 230 2469400540452 231 2721814605996 232 3075203905369 233 3264130549647 234 3374810725945 235 3715100507345 236 4188935074492 237 4446144787333 238 4600760198739 239 5058514283653 240 5692520938647 241 6041814998052 242 6256884494139 243 6871332809696 244 7717927362419 245 8191113702422 246 8489069021546 247 9312124723924 248 10440339569450 249 11079833874435 250 11491042001093 251 12591273361059 252 14091863491669 253 14954106917612 254 15519555565327 255 16987363083592 256 18979434347666 257 20139375735211 258 20914230232170 259 22868584021709 260 25508183177046 261 27065146552087 262 28123450550528 263 30720643587211 264 34211874823208 265 36297226407164 266 37738099499331 267 41183102449922 268 45792490793172 269 48579639852269 270 50535431696131 271 55096599071198 272 61171623075189 273 64889044408739 274 67536039292322 275 73564127749441 276 81557095796675 277 86505258283193 278 90077699888544 279 98030425559147 280 108529194675900 281 115102530931681 282 119910959079370 283 130384661511015 284 144152102933301 285 152867475171389 286 159322654805015 287 173093064308403 288 191117699248870 289 202651223400581 290 211295310509760 291 229369963004306 292 252930840850356 293 268165449098513 294 279712508804809 295 303398041040566 296 334147759183785 297 354234538270152 298 369623124569450 299 400611557647821 300 440682355433622 301 467119532349333 302 487580802150039 303 528060021129140 304 580199191869519 305 614933694316094 306 642079491462017 307 694874521403156 308 762617024366031 309 808174879839101 310 844111455713084 311 912864882476787 312 1000753107732097 313 1060406632512565 314 1107881221405380 315 1197283311727310 316 1311146535451549 317 1389128395288792 318 1451717837535350 319 1567799677997014 320 1715109002745679 321 1816885910812681 322 1899239002505728 323 2049745457121540 324 2240064092449081 325 2372686290199665 326 2480834690376861 327 2675698331125526 328 2921252171209210 329 3093799086149236 330 3235555573672241 331 3487498204486569 332 3803898012709365 333 4028045824779141 334 4213513703207424 335 4538808926419861 336 4945963395435068 337 5236706938042052 338 5478930667390549 339 5898369491846886 340 6421638347025900 341 6798208160288568 342 7114003206873234 343 7654115360070201 344 8325764042846128 345 8812789898530149 346 9223799703084893 347 9918396630312496 348 10779429461847908 349 11408414814811809 350 11942455226699794 351 12834577344166516 352 13937045219934600 353 14748233445683506 354 15441000531116553 355 16585371971352609 356 17995274391283310 357 19040008143723679 358 19937244770240576 359 21403364549744330 360 23204295329855991 361 24547995872517823 362 25708236795609981 363 27584267290798993 364 29881989892164428 365 31607915040548164 366 33105960615452687 367 35503613882708485 368 38431797701616739 369 40645776552098379 370 42577083050665166 371 45637754744631558 372 49365159866741168 373 52201551633999909 374 54687773344249732 375 58590234953468970 376 63329702428079967 377 66958887731356765 378 70154864688931835 379 75124900339399978 380 81144590922360856 381 85782379561592009 382 89884937746375505 383 96207405225890488 384 103844835714592536 385 109764268789462991 386 115023290181273378 387 123057201341416246 388 132736758546024546 389 140282898938253303 390 147015231236597411 391 157212589527040086 392 169467363462518267 393 179075812400424128 394 187682727444098743 395 200612036358527811 396 216111013134454115 397 228331068177170666 398 239320150570592727 399 255695723746925427 400 275277623610972066 401 290801212715102147 402 304813773408711829 403 325532244484522031 404 350247591652536602 405 369945388601053800 406 387790761804960889 407 413976521144679991 408 445139902387526878 409 470106362446803548 410 492804769638638650 411 525866459805202052 412 565121383387530006 413 596730848949877296 414 625566915251883518 415 667267614418785582 416 716666939094707172 417 756643470713888193 418 793232973627146275 419 845777306938946294 420 907882894850732655 421 958387104866223933 422 1004760144704352756 423 1070902312949140437 424 1148908398818945114 425 1212645328695754343 426 1271349859600238739 427 1354527493458570162 428 1452413288897106523 429 1532766309269484405 430 1606996891299474522 431 1711496765068240252 432 1834215072985596873 433 1935411935813201497 434 2029169700379073821 435 2160332717256894044 436 2314042866823147941 437 2441361449173742781 438 2559652659312996655 439 2724127206102908296 440 2916482495027394845 441 3076505500999920356 442 3225587791294396575 443 3431642621283117823 444 3672144742517929616 445 3873074743383074684 446 4060762211631647033 447 4318672531624193112 448 4619108256318862278 449 4871157033565277046 450 5107197911527223840 451 5429721421893767545 452 5804700217170759078 453 6120569531511289349 454 6417113288305606029 455 6820076672861632002 456 7287692084108580240 457 7683166850036089297 458 8055341402974108274 459 8558362334290276637 460 9141005015089251683 461 9635684566278344775 462 10102308941839940167 463 10729684232371255865 464 11455040654336915579 465 12073239522777583818 466 12657703007457161277 467 13439500310930639439 468 14341778661643487355 469 15113635284282595154 470 15844981053932219955 471 16818379761083864638 472 17939813623011563085 473 18902653901478818686 474 19816913586229783299 475 21027850575508476029 476 22420542009423561254 477 23620555004949480485 478 24762390960938646660 479 26267579032281475117 480 27995756075489721221 481 29490051713321574344 482 30914776324099851787 483 32784177915616126812 484 34926957738944492915 485 36786091696807600314 486 38562148292659300115 487 40882005000557630886 488 43536773644035069324 489 45847843177110749503 490 48059851711542057485 491 50936391861428996995 492 54222935299212346606 493 57093372297074230601 494 59845865450002838772 495 63409838293411129701 496 67475388426239288588 497 71037603333168624449 498 74459606052630627551 499 78871823040793168359 500 83897217110646541337 501 88314280467484113916 502 92564919123662899399 503 98023021286372132058 504 104230215399427969749 505 109702803883112145712 506 114978171399525467582 507 121724888510703778525 508 129386116931501356055 509 136160999322515278688 510 142702551329843521530 511 151035774928164556288 512 160484708367321146620 513 168865105601920725870 514 176969921582013996211 515 187254982026124906706 516 198900312434326923547 517 209258536884969536218 518 219291851548020289444 519 231976471507676762919 520 246318440495944140758 521 259111305375724459696 522 271521801673797773457 523 287154297657726733972 524 304804793677933324494 525 320592386991650486155 526 335930846263571963124 527 355182269394485448304 528 376889248947783157511 529 396357791321570685738 530 415299821736719436320 531 438990873122427540938 532 465668017950665182850 533 489657674290615056288 534 513031390397950503885 535 542165120041567978347 536 574927830818132354323 537 604466527259284211035 538 633286236301202160798 539 669087743447176659368 540 709296797268444991481 541 745641313487437146502 542 781148484503971529331 543 825113088686153682981 544 874427560280218922982 545 919113430387587663610 546 962826487546007812885 547 1016778141834865324499 548 1077219515923633227610 549 1132121587714752894160 550 1185896388777920311434 551 1252058469900864297720 552 1326088265430784710558 553 1393494148384844590844 554 1459597393561293383368 555 1540678439749062945689 556 1631292138683271811012 557 1713991228458709350964 558 1795189506963319734677 559 1894486997939544559745 560 2005327637440670412185 561 2106718953891325613136 562 2206386690792031327214 563 2327912592447653346860 564 2463408057989387060732 565 2587630793027715078499 566 2709881025774663845565 567 2858513575225866946439 568 3024042445428288228079 569 3176133907995255705136 570 3325976622384709609722 571 3507643731721405183464 572 3709735499662815104019 573 3895822093396120323371 574 4079355808831501935369 575 4301256547003716823439 576 4547833208596331121361 577 4775361214230099944204 578 5000004659248586844299 579 5270876565860235217102 580 5571543960661496633734 581 5849558256332001416590 582 6124330354724570409709 583 6454771888235858842399 584 6821170845945536608587 585 7160651327986023387737 586 7496509367806284881177 587 7899368642859957248919 588 8345597982178047245420 589 8759865398517988831608 590 9170113233687445388384 591 9660956416306943906922 592 10204082224188780747811 593 10709287463813670208001 594 11210067963733010126349 595 11807743338359117031539 596 12468411801074883277826 597 13084125469501620919584 598 13695014260852605897115 599 14422331141978798930744 600 15225505592780237525738 601 15975428032329082132791 602 16720148957968036149006 603 17604694389374450153639 604 18580541285404272907016 605 19493357173754544096056 606 20400643931897185788420 607 21475764614312236911108 608 22660717981602774384247 609 23771124385654377774944 610 24875757633859032061953 611 26181739885131130491131 612 27619779522039947263567 613 28969721942387189726749 614 30313776904106908559343 615 31899263848073381616606 616 33643449428515350514266 617 35283607115965708406709 618 36917953589347338528126 619 38841646384310912455587 620 40955957759010793924207 621 42947527623793785701601 622 44933632472569809377123 623 47266331457182621199884 624 49827875158356580493807 625 52244713168209494675241 626 54656805121394147725275 627 57483857546718905632873 628 60585511048404415013708 629 63516701411756748204999 630 66444369606876987547891 631 69868603460295952223590 632 73622182475432620182312 633 77175118471650805639018 634 80726429994101726068681 635 84871668684487344771565 636 89411719095737129389203 637 93715795549701203682022 638 98021033661401709461512 639 103036304476035854353548 640 108524639879096775457247 641 113735676460054671677292 642 118951820762403419295503 643 125016391557218422069212 644 131647520408835939164400 645 137953057728552855677256 646 144269150745674481037530 647 151598554920949353847757 648 159606168597506624723746 649 167231806158085457299072 650 174875378439712884154151 651 183728618627062054849512 652 193393344102808059529837 653 202610321289362206276641 654 211855079925952974406796 655 222543236847352513230563 656 234201896125795434696717 657 245336155585432154171418 658 256511179955091565303085 659 269407695647296657767274 660 283464359624245823494547 661 296907377620892309196265 662 310408112374793523284368 663 325961067625626642258710 664 342900246024396096010429 665 359121968007311277271971 666 375423358076948810185469 667 394170123935843626740417 668 414572496862577954166277 669 434136780066573389022564 670 453808957410952558649882 671 476393671714987212647590 672 500954844036251615309507 673 524537884249617100884355 674 548264893003088062733876 675 575459297005173210647308 676 605012146272522283409068 677 633424455092931588037930 678 662026592905538497537985 679 694754862663504565319300 680 730296157199290467630674 681 764508761656221520456951 682 798969222907637166648676 683 838337547870795331134899 684 881059636826679716486906 685 922235298134364007524553 686 963731932376492648084553 687 1011063732860755361012620 688 1062392258025623721409178 689 1111922653919784900363319 690 1161865803925480015119909 691 1218743643747983113945801 692 1280382397684813780441124 693 1339932387380491550977295 694 1400009949740894270764720 695 1468325394716564965946205 696 1542309656233337564562535 697 1613869953332088174096348 698 1686101015587140972169444 699 1768113918194443696145538 700 1856873839825689846770907 701 1942823662156721570297568 702 2029622319765572854863048 703 2128031281320630606158292 704 2234467191020615812190451 705 2337648744072553580879476 706 2441899994954457774543126 707 2559926076439077633809872 708 2687497894823427159584987 709 2811304884925407397200249 710 2936454846843827473919490 711 3077940976741494346144336 712 3230774351070113666650851 713 3379257124990139034377992 714 3529420231129338536233877 715 3698949203362516199330042 716 3881961430721725234377337 717 4059951810641282671016461 718 4240038122392851778724678 719 4443072601610183501511483 720 4662121968965773859331141 721 4875381408507697358393080 722 5091247754722247663732709 723 5334296323697684365022977 724 5596359146357437557978733 725 5851754489323704482452143 726 6110383813318412252002653 727 6401197824444394782099554 728 6714578234226428560051129 729 7020290130341279242122161 730 7330004217647418449698793 731 7677811066594938296930377 732 8052389506846376178100323 733 8418159448492859495763754 734 8788871140620103444675784 735 9204650587655102402736321 736 9652178037866784229571099 737 10089601052452060325720609 738 10533113149381295336618916 739 11029924498873054514234479 740 11564370704698798089609095 741 12087241996883882038334191 742 12617601342333172824696339 743 13210970684465574086445196 744 13848936141915496031969096 745 14473661461286107169219704 746 15107578223702746735077761 747 15815956580355815789583545 748 16577159753748594731661466 749 17323241004967471279975371 750 18080584953111959223823339 751 18925890094503890364668634 752 19833743380834709101644210 753 20724353039817411726022975 754 21628740710867959615705342 755 22636997670181985143634695 756 23719288009813521326314455 757 24781948313551713646985899 758 25861437437858438930900610 759 27063535405423780400415887 760 28353228241135446031664864 761 29620613941896897548301298 762 30908524384992791254638615 763 32341110779090943909373681 764 33877299353457482774139436 765 35388186142047537336784114 766 36924070025097494722312968 767 38630606191936013803656432 768 40459632029614448242833805 769 42260016621126234495718889 770 44090804271938427311692254 771 46122811554837206880473726 772 48299586498389611897457346 773 50444008935455177198880910 774 52625362004285840780554504 775 55043891949160058935009870 776 57633457417501885614318194 777 60186561494993415864672860 778 62784470060366142271891741 779 65661838416661796093997699 780 68741203765945181851635892 781 71779577751045333999989690 782 74872244678121247606796750 783 78294075757912048152323049 784 81954384899451419713033376 785 85568732068023752075417204 786 89248795426111546294711061 787 93316431469945233366898866 788 97665515418066462394997901 789 101963212534318357696826732 790 106340365718065035201411000 791 111173705383591937417431753 792 116339088377202429690172373 793 121447200321011600232519682 794 126651279869962621627911004 795 132392121040668785932695140 796 138524559549694252847945905 797 144593390092145123455312350 798 150778013320237703521034558 799 157593988397447866581479078 800 164871635973123496347138723 801 172078908504209103480939515 802 179425757231043642952763565 803 187514964238154402755238968 804 196148271125367586182562903 805 204704049284523339804697367 806 213427912549644170023644184 807 223024363110641385212444763 808 233261838196387242096681505 809 243414315237971189617882323 810 253769023280562278887768828 811 265149049262988236124322332 812 277284033736019380057676835 813 289326341533823088850677282 814 301611746002103755835115885 815 315101530835623520594690902 816 329480158400485682072171609 817 343758372788391458902650959 818 358328554651446457376241125 819 374312983626333473106080330 820 391343531857372272103286206 821 408266081134733541419712881 822 425538998739777359329403734 823 444472055628885975052140087 824 464635927772661431187160280 825 484684646391052945703795343 826 505153472280234678618300223 827 527570448197022256145131608 828 551435065255906605256126954 829 575178175783765530619513329 830 599424613116065486836545143 831 625956438531020286550631559 832 654190368740870973831112700 833 682297723145208017215734760 834 711007641860052191107627911 835 742397705207297342950301451 836 775788413166824170430787188 837 809049380385120536928749201 838 843031170756519559698742742 839 880155048301582423092517628 840 919629710308399569971242342 841 958974162320184955609476997 842 999180270633050345686354301 843 1043068863670670021560469070 844 1089718770764777773233774850 845 1136241695434152053961183934 846 1183793884735591894535567863 847 1235660543402106107177176408 848 1290769700948122206880055434 849 1345760058564041659410196902 850 1401979028622285621871755415 851 1463251338566518436851445709 852 1528329972936642945587560299 853 1593304516679953007412829211 854 1659744623535388576791510887 855 1732101644630026649568985710 856 1808925446018684235180168569 857 1885668346915902561445984041 858 1964158286185079644999854008 859 2049574163970142676818966114 860 2140230232290595515904362965 861 2230839489338095445322154079 862 2323529951577948453283354047 863 2424324975216314980773357059 864 2531265596544158291536511513 865 2638207375808103544834398746 866 2747626850064400424541604213 867 2866527208743159146112877518 868 2992632776527166805810111393 869 3118805012860903784142728817 870 3247925109838906840978724673 871 3388132806811110838291079544 872 3536785419293411788256950683 873 3685592235173080513307370758 874 3837904128715623872713916580 875 4003178753228169321907899497 876 4178348271098243529875792253 877 4353787023951302542101934292 878 4533390873830679288753142929 879 4728145211451013491540124334 880 4934489853371240136684136724 881 5141252921444726619190831308 882 5352962447825575101976603395 883 5582374235446281629270728465 884 5825358130295943646267417745 885 6068951894279533122677389482 886 6318416631488113363702217713 887 6588559141829307246177910773 888 6874589652919043660698073976 889 7161473533957333011115892573 890 7455321706384910658558748371 891 7773316286550826957168805681 892 8109904383455957350042532631 893 8447653266831266561312485699 894 8793658712150745891322538505 895 9167852911473544905255821324 896 9563800399698623326294136284 897 9961294317727267439989364987 898 10368571442811179463643419553 899 10808746958105010221194404672 900 11274364997293781454298575994 901 11742010576871794880690823009 902 12221241982243267733061065135 903 12738857336732976896056417271 904 13286221398188326710275197194 905 13836210311844688742464246872 906 14399912475486084814592739801 907 15008386146142532644237252882 908 15651633395754564959872402802 909 16298243906089892746129294351 910 16961077193528268307778345519 911 17676117827761386349067750157 912 18431793889243314128527959355 913 19191742563823872210052090819 914 19970872847741375253593523745 915 20810864284509814573198408025 916 21698327461122134782366208317 917 22591179279727094753965588936 918 23506699631018710465854663423 919 24493149686675419776593621938 920 25535042021649301429723704940 921 26583688425030880591315284608 922 27659110703796706757191784526 923 28817174126273149999274712190 924 30039970190951902670495618815 925 31271186158603881676735952068 926 32534013917523381041791994467 927 33893101584788012282629690534 928 35327747631449361843566364214 929 36772840658360105729419297904 930 38255236606321149081037076081 931 39849724982247046728400856877 932 41532383122997152578337675002 933 43227949030164398671254686587 934 44967512430240403755638658444 935 46837569534418388018166807531 936 48810483951557927630703275048 937 50799286856221763719627751821 938 52839958694496521026556350128 939 55032505439826399689418572577 940 57345010346396750746045495743 941 59677006886336616310912412372 942 62070123499040084148896674996 943 64639952257137077368943149385 944 67349644466300448326477530891 945 70083175576775172238484301615 946 72888694723125064742504846813 947 75899770456131969009949258480 948 79073873050737546234174711114 949 82277050300339087686188741082 950 85564977487047740451455264094 951 89091950808487294972784106029 952 92808898603838377843434064864 953 96561216384631686415549489446 954 100413263665552697498048351385 955 104543229846692357893283174621 956 108894512197987462214004391825 957 113288722025666724775608234353 958 117800236609095563529829097756 959 122634779928073008944399102566 960 127727082050441484479140550331 961 132871370965376102886519096827 962 138153576868758060161969683239 963 143811145919343872518414922576 964 149768836379396490119474997218 965 155789358068634559399739820088 966 161971960888764129780658252530 967 168590627653014068814527690479 968 175558647190613288083956265714 969 182602462111516997857179042948 970 189836674869274144264792522233 971 197577338661865706812042982447 972 205724554163930367690956780033 973 213963043800298230038316690934 974 222425100935533972834192405620 975 231475207918146112612133131502 976 240998305370621389942832605436 977 250631135973973667596315483293 978 260526373095940704766553676604 979 271104233134258428583579798615 980 282232234928597823377112132236 981 293491957900298442452500831943 982 305059547057939126831086426246 983 317419342477998981555001459424 984 330418847780113124985802562250 985 343576237475260276371831160998 986 357094681748147524663709476050 987 371532277303052202111551171142 988 386713539576538540998212108783 989 402083785035399540431820381776 990 417877292445952763382869665221 991 434736972827794466159571806923 992 452460946350835785228988251382 993 470410831606957049300621696099 994 488856707046378355204287328556 995 508538987915675341159292363672 996 529225495600352291647609809835 997 550181724143028570876835310243 998 571718939565096410114627591357 999 594689620716772986139264845946 1000 618826819142226889805257969695