0 1 1 1 2 1 3 2 4 3 5 4 6 5 7 7 8 9 9 12 10 15 11 19 12 24 13 30 14 37 15 46 16 57 17 69 18 84 19 102 20 123 21 148 22 177 23 211 24 252 25 299 26 353 27 417 28 491 29 576 30 675 31 789 32 920 33 1071 34 1244 35 1442 36 1670 37 1929 38 2224 39 2562 40 2946 41 3381 42 3876 43 4437 44 5072 45 5791 46 6602 47 7517 48 8551 49 9714 50 11021 51 12493 52 14145 53 15997 54 18075 55 20402 56 23005 57 25917 58 29169 59 32799 60 36851 61 41365 62 46391 63 51989 64 58214 65 65130 66 72814 67 81342 68 90800 69 101287 70 112902 71 125760 72 139991 73 155724 74 173109 75 192316 76 213516 77 236902 78 262693 79 291116 80 322422 81 356891 82 394816 83 436526 84 482383 85 532764 86 588090 87 648829 88 715470 89 788551 90 868669 91 956455 92 1052600 93 1157864 94 1273053 95 1399053 96 1536832 97 1687416 98 1851932 99 2031613 100 2227766 101 2441817 102 2675326 103 2929956 104 3207515 105 3509969 106 3839419 107 4198152 108 4588649 109 5013557 110 5475753 111 5978360 112 6524712 113 7118419 114 7763397 115 8463834 116 9224257 117 10049562 118 10944991 119 11916211 120 12969338 121 14110914 122 15348006 123 16688243 124 18139782 125 19711415 126 21412625 127 23253562 128 25245154 129 27399164 130 29728185 131 32245770 132 34966494 133 37905948 134 41080899 135 44509372 136 48210640 137 52205405 138 56515906 139 61165929 140 66180996 141 71588491 142 77417701 143 83700039 144 90469181 145 97761116 146 105614425 147 114070451 148 123173361 149 132970455 150 143512388 151 154853271 152 167051011 153 180167571 154 194269121 155 209426441 156 225715217 157 243216231 158 262015848 159 282206377 160 303886300 161 327160827 162 352142353 163 378950760 164 407714043 165 438568844 166 471660855 167 507145565 168 545188874 169 585967582 170 629670284 171 676498116 172 726665344 173 780400395 174 837946769 175 899563779 176 965527733 177 1036133012 178 1111693002 179 1192541489 180 1279033914 181 1371548499 182 1470487911 183 1576280768 184 1689382977 185 1810279667 186 1939487012 187 2077553867 188 2225064006 189 2382638268 190 2550936555 191 2730660482 192 2922555888 193 3127415226 194 3346080697 195 3579447242 196 3828465379 197 4094144863 198 4377558263 199 4679844369 200 5002212453 201 5345946477 202 5712409206 203 6103047219 204 6519395842 205 6963084027 206 7435840266 207 7939498442 208 8476003584 209 9047418784 210 9655932128 211 10303863555 212 10993672926 213 11727968167 214 12509513436 215 13341238595 216 14226248759 217 15167833935 218 16169480164 219 17234880766 220 18367947684 221 19572824506 222 20853899728 223 22215820166 224 23663506138 225 25202167009 226 26837317047 227 28574793213 228 30420773344 229 32381794779 230 34464775208 231 36677034017 232 39026314131 233 41520806348 234 44169174385 235 46980580555 236 49964714129 237 53131820624 238 56492731974 239 60058899658 240 63842428888 241 67856113929 242 72113476814 243 76628807316 244 81417204227 245 86494620456 246 91877909765 247 97584875085 248 103634320989 249 110046108185 250 116841210021 251 124041773636 252 131671183422 253 139754126942 254 148316666165 255 157386311430 256 166992098259 257 177164670171 258 187936364870 259 199341303780 260 211415488231 261 224196899690 262 237725604090 263 252043863619 264 267196253144 265 283229781549 266 300194021609 267 318141245295 268 337126564744 269 357208082901 270 378447050690 271 400908030814 272 424659072369 273 449771893138 274 476322069810 275 504389240394 276 534057315487 277 565414698875 278 598554522071 279 633574889157 280 670579132376 281 709676083588 282 750980357893 283 794612649732 284 840700046833 285 889376358358 286 940782457767 287 995066645876 288 1052385030248 289 1112901921737 290 1176790254141 291 1244232022762 292 1315418742705 293 1390551933487 294 1469843625716 295 1553516890611 296 1641806399255 297 1734959007453 298 1833234367209 299 1936905571943 300 2046259831127 301 2161599175770 302 2283241202472 303 2411519851385 304 2546786219589 305 2689409418423 306 2839777470142 307 2998298245373 308 3165400450374 309 3341534659659 310 3527174395881 311 3722817266328 312 3928986151443 313 4146230447805 314 4375127375775 315 4616283346909 316 4870335393810 317 5137952673670 318 5419838040710 319 5716729690326 320 6029402886856 321 6358671770588 322 6705391247349 323 7070458973188 324 7454817429733 325 7859456094393 326 8285413719081 327 8733780712807 328 9205701632775 329 9702377799043 330 10225070028493 331 10775101493053 332 11353860718258 333 11962804718509 334 12603462274863 335 13277437372444 336 13986412793981 337 14732153876553 338 15516512450199 339 16341430954960 340 17208946744275 341 18121196595330 342 19080421423662 343 20088971210604 344 21149310165758 345 22264022122875 346 23435816179164 347 24667532601721 348 25962149000043 349 27322786776510 350 28752717880837 351 30255371868011 352 31834343272990 353 33493399330935 354 35236488043836 355 37067746608177 356 38991510234855 357 41012321363963 358 43134939291349 359 45364350240585 360 47705777884321 361 50164694334781 362 52746831640412 363 55458193793999 364 58305069274416 365 61294044163105 366 64432015842968 367 67726207304286 368 71184182102460 369 74813859978251 370 78623533168789 371 82621883457972 372 86817999979553 373 91221397805529 374 95842037373558 375 100690344769493 376 105777232901676 377 111114123626733 378 116712970846964 379 122586284620253 380 128747156348059 381 135209285066521 382 141987004887360 383 149095313660200 384 156549902886105 385 164367188935806 386 172564345652059 387 181159338370970 388 190170959422407 389 199618865197991 390 209523614828289 391 219906710536584 392 230790639766658 393 242198919134345 394 254156140279359 395 266688017724564 396 279821438800626 397 293584515723152 398 308006639941447 399 323118538825658 400 338952334790361 401 355541606987429 402 372921455646168 403 391128569170603 404 410201294140875 405 430179708309962 406 451105696720085 407 473023031101164 408 495977452656135 409 520016758374267 410 545190891053296 411 571552033150214 412 599154704619418 413 628055864939977 414 658315019470212 415 689994330307581 416 723158731877793 417 757876051412475 418 794217134516343 419 832255976072102 420 872069856664903 421 913739484753627 422 957349144865743 423 1002986852022394 424 1050744512649077 425 1100718092281077 426 1153007790299856 427 1207718221986714 428 1264958608237533 429 1324842973208603 430 1387490350216153 431 1453024996271672 432 1521576615559377 433 1593280592219727 434 1668278232865328 435 1746717019176071 436 1828750870982064 437 1914540420310659 438 2004253296791593 439 2098064424878167 440 2196156333415054 441 2298719478000308 442 2405952576656586 443 2518062959402067 444 2635266932227021 445 2757790156055685 446 2885868041352628 447 3019746158944526 448 3159680667707325 449 3305938759855432 450 3458799124478636 451 3618552430054905 452 3785501826760212 453 3959963469305482 454 4142267061118320 455 4332756420784318 456 4531790071570787 457 4739741854951278 458 4957001569152216 459 5183975633647687 460 5421087780631331 461 5668779774606418 462 5927512161137716 463 6197765045916990 464 6480038905414577 465 6774855430293190 466 7082758402875372 467 7404314610082774 468 7740114793169446 469 8090774635697196 470 8456935791336258 471 8839266952975992 472 9238464964766298 473 9655255978857778 474 10090396658509481 475 10544675429377011 476 11018913780952642 477 11513967620032968 478 12030728678243614 479 12570125975818866 480 13133127343740196 481 13720741006506096 482 14334017227985803 483 14974050022714999 484 15641978935174314 485 16338990889788057 486 17066322114287853 487 17825260139280373 488 18617145877071111 489 19443375782709778 490 20305404100432080 491 21204745198899390 492 22142975998557003 493 23121738494660757 494 24142742379765790 495 25207767769393314 496 26318668034840349 497 27477372747363930 498 28685890737899312 499 29946313276738626 500 31260817377885903 501 32631669232743782 502 34061227778075469 503 35551948403495958 504 37106386803697026 505 38727202980926842 506 40417165403580343 507 42179155326715573 508 44016171280656147 509 45931333734207022 510 47927889938982661 511 50009218961718130 512 52178836911833402 513 54440402371512440 514 56797722035961705 515 59254756571943752 516 61815626702692673 517 64484619527760876 518 67266195086814023 519 70164993176420330 520 73185840429364187 521 76333757666526525 522 79613967531427011 523 83031902418046815 524 86593212703110547 525 90303775294090405 526 94169702504765994 527 98197351270779357 528 102393332717742917 529 106764522095085276 530 111318069089479575 531 116061408531850093 532 121002271512639462 533 126148696920743440 534 131509043421711205 535 137092001891555880 536 142906608323312859 537 148962257223725643 538 155268715518254544 539 161836136983465690 540 168675077226154953 541 175796509229458814 542 183211839487145343 543 190932924747631281 544 198972089390255778 545 207342143457376145 546 216056401366269399 547 225128701325897454 548 234573425484728361 549 244405520836304996 550 254640520910428666 551 265294568279062651 552 276384437906646721 553 287927561375808633 554 299942052020813225 555 312446731001766419 556 325461154354014024 557 339005641048665598 558 353101302100955194 559 367770070764707178 560 383034733852811617 561 398918964224520176 562 415447354482080361 563 432645451921015569 564 450539794779400809 565 469157949833364416 566 488528551388008502 567 508681341714126709 568 529647212983165954 569 551458250755039467 570 574147779074748473 571 597750407236036686 572 622302078272676414 573 647840119239526492 574 674403293347991876 575 702031854023117346 576 730767600951297797 577 760653938190331142 578 791735934416397570 579 824060385384522458 580 857675878682099907 581 892632860858200935 582 928983707013616992 583 966782792939903886 584 1006086569899153122 585 1046953642138734791 586 1089444847238899627 587 1133623339394927292 588 1179554675738342539 589 1227306905805737073 590 1276950664267910599 591 1328559267035222086 592 1382208810859463807 593 1437978276557170514 594 1495949635982839271 595 1556207962885393510 596 1618841547786287257 597 1683942017021645625 598 1751604456096181770 599 1821927537502191912 600 1895013653161409690 601 1970969051653391144 602 2049903980400217153 603 2131932832982300335 604 2217174301766569409 605 2305751536035041187 606 2397792305807371908 607 2493429171558110541 608 2592799660036792800 609 2696046446405250963 610 2803317542914361586 611 2914766494350605098 612 3030552580489766014 613 3150841025803749465 614 3275803216675457586 615 3405616926384406823 616 3540466548135288819 617 3680543336411555514 618 3826045656944717472 619 3977179245600516762 620 4134157476494009785 621 4297201639655178307 622 4466541228578211830 623 4642414237999561334 624 4825067472260517902 625 5014756864622766189 626 5211747807918517476 627 5416315496928648982 628 5628745282896254920 629 5849333040597501729 630 6078385548404798006 631 6316220881792666017 632 6563168820752646747 633 6819571271598132788 634 7085782703656944222 635 7362170601366997680 636 7649115932306567455 637 7947013631709270960 638 8256273104033201994 639 8577318742171518325 640 8910590464912300614 641 9256544273276736953 642 9615652826384489053 643 9988406037517655799 644 10375311691078119473 645 10776896081154992666 646 11193704672443703823 647 11626302784283957433 648 12075276298608077348 649 12541232392618563003 650 13024800297041954521 651 13526632080832935462 652 14047403463232665042 653 14587814654116436642 654 15148591223595420454 655 15730485001870307895 656 16334275010368891980 657 16960768425232409553 658 17610801574251832117 659 18285240968392911029 660 18984984369085011707 661 19710961892488777692 662 20464137151999030730 663 21245508440279305753 664 22056109952168422569 665 22897013049844995475 666 23769327571679924631 667 24674203186255286747 668 25612830793078073919 669 26586443971565955683 670 27596320479935423433 671 28643783805677665397 672 29730204769361276528 673 30857003183559394357 674 32025649568759294587 675 33237666928171746760 676 34494632583421729442 677 35798180073168554758 678 37150001116768785303 679 38551847645165986050 680 40005533901264390102 681 41512938612115577752 682 43076007235324919712 683 44696754282164778594 684 46377265719960820460 685 48119701456403136164 686 49926297908522034957 687 51799370659155767502 688 53741317203831218145 689 55754619791075482389 690 57841848359272478034 691 60005663573281752675 692 62248819964143074885 693 64574169175296355586 694 66984663318859600221 695 69483358445624467934 696 72073418132545639505 697 74758117191624496107 698 77540845504215960553 699 80425111984915661893 700 83414548679321097009 701 86512915000101421197 702 89724102105951641300 703 93052137428156864322 704 96501189349647026505 705 100075572041577774942 706 103779750462637721511 707 107618345526452177993 708 111596139442624189390 709 115718081237134337082 710 119989292458007257776 711 124415073072340461906 712 129000907560989330766 713 133752471217406851759 714 138675636657342866518 715 143776480546325209071 716 149061290552069728118 717 154536572529192799544 718 160209057943838706930 719 166085711546080701317 720 172173739298203508879 721 178480596567237049327 722 185013996590381476789 723 191781919222237071836 724 198792619973039933577 725 206054639347400997324 726 213576812493346138123 727 221368279171770358308 728 229438494056744343892 729 237797237377441324277 730 246454625912797887484 731 255421124350379097876 732 264707557021280118786 733 274325120023275667734 734 284285393744819732793 735 294600355802895074996 736 305282394408127726838 737 316344322171010497284 738 327799390363515197792 739 339661303650828976584 740 351944235308420199146 741 364662842940117323873 742 377832284713383677241 743 391468236128486195199 744 405586907338780506080 745 420205061039882136996 746 435340030946058170829 747 451009740872748627282 748 467232724444726699259 749 484028145450025590265 750 501415818860390081249 751 519416232539668158963 752 538050569662235785098 753 557340731864238965303 754 577309363151157230255 755 597979874585935032240 756 619376469782685026057 757 641524171231755827438 758 664448847482769952093 759 688177241213067681886 760 712736998209856308723 761 738156697295254690410 762 764465881224332494675 763 791695088587189263914 764 819875886747093497380 765 849040905847698257605 766 879223873923385291491 767 910459653147857142504 768 942784277257187998931 769 976234990184677635864 770 1010850285946021339869 771 1046669949814503740291 772 1083735100827165314205 773 1122088235664169343815 774 1161773273944905584795 775 1202835604985724886810 776 1245322136065598728279 777 1289281342247430135041 778 1334763317804228454726 779 1381819829300892022289 780 1430504370383910768289 781 1480872218332926736641 782 1532980492429766099971 783 1586888214202272281668 784 1642656369602048524330 785 1700347973177051275950 786 1760028134301853492651 787 1821764125530342547329 788 1885625453137622361044 789 1951683929919943780160 790 2020013750323615064659 791 2090691567976036944249 792 2163796575694254032578 793 2239410588048741292698 794 2317618126562541773073 795 2398506507628329782892 796 2482165933228517885790 797 2568689584546147407522 798 2658173718556990079630 799 2750717767696069821213 800 2846424442694679240630 801 2945399838686904477573 802 3047753544687712283740 803 3153598756547785364660 804 3263052393493505107624 805 3376235218363803708075 806 3493271961659030742324 807 3614291449520491377158 808 3739426735762944654285 809 3868815238086090816796 810 4002598878594915131837 811 4140924228762723294210 812 4283942658974790387089 813 4431810492794739986134 814 4584689166100104625074 815 4742745391237983511188 816 4906151326356296458065 817 5075084750070868018330 818 5249729241633452559049 819 5430274366770817765659 820 5616915869370175724332 821 5809855869191576982448 822 6009303065793351818325 823 6215472948862330716825 824 6428588015146392416124 825 6648877992192860689672 826 6876580069102437949659 827 7111939134514714444158 828 7355208022047814077340 829 7606647763421470875888 830 7866527849499763347386 831 8135126499496855177459 832 8412730938596440740186 833 8699637684243162179310 834 8996152841372038934882 835 9302592406849973081657 836 9619282583411654248965 837 9946560103380673701500 838 10284772562475412547995 839 10634278764008283623930 840 10995449073796167949680 841 11368665786109440750609 842 11754323500996818411833 843 12152829513333364076337 844 12564604213949413856932 845 12990081503208917453499 846 13429709217416713941317 847 13883949568445635650006 848 14353279596986040285003 849 14838191639832401401947 850 15339193811633992049331 851 15856810501549465984799 852 16391582885258263255935 853 16944069452795296313538 854 17514846552689299458898 855 18104508952899536470832 856 18713670419060315362908 857 19342964310557945910174 858 19993044194980383143872 859 20664584481495887596833 860 21358281073733591707863 861 22074852042755880012544 862 22815038320730030180382 863 23579604415924614105551 864 24369339149674712189332 865 25185056415979113965121 866 26027595964412356193403 867 26897824207054675079485 868 27796635050163789649866 869 28724950751333880993512 870 29683722802909177028181 871 30673932842442265087013 872 31696593591010628194187 873 32752749820228925995448 874 33843479348819291396798 875 34969894069627383141851 876 36133141007998114296075 877 37334403412451943704286 878 38574901878630366806298 879 39855895507507766117112 880 41178683098896160727349 881 42544604381299624185876 882 43955041279206214301179 883 45411419218937261116104 884 46915208474206787706942 885 48467925552577686798239 886 50071134624036132703191 887 51726448992941571291114 888 53435532614646496233448 889 55200101658118180107496 890 57021926115933583844220 891 58902831463058814658202 892 60844700365865838075999 893 62849474442881675361351 894 64919156078809032122980 895 67055810293402309101417 896 69261566666829245428667 897 71538621323196038372277 898 73889238973962778526765 899 76315755023026441063182 900 78820577735300484495231 901 81406190470673440588113 902 84075153985283740077687 903 86830108802104413581779 904 89673777652889353479792 905 92608967993592530598030 906 95638574595432936371144 907 98765582213841190897485 908 101993068337588732908688 909 105324206020467298922873 910 108762266797955136153627 911 112310623691377093182086 912 115972754302138406992631 913 119752243998686791925787 914 123652789198934354687854 915 127678200750949926247496 916 131832407414813760941910 917 136119459448610228335535 918 140543532301620134333031 919 145108930417862807293129 920 149820091153229099647969 921 154681588809540009847648 922 159698138788961883957597 923 164874601872308142757705 924 170215988624859227498216 925 175727463933437134950421 926 181414351678578556620068 927 187282139545761281800436 928 193336483979752348553815 929 199583215286263472652916 930 206028342885219591080330 931 212678060720070113028846 932 219538752827699725577775 933 226616999073626398356252 934 233919581057308771211508 935 241453488192523445903196 936 249225923967914888964457 937 257244312392966899151130 938 265516304634794960990379 939 274049785851313354966682 940 282852882226489848356667 941 291933968213564218022145 942 301301673992274824392667 943 310964893146310201097667 944 320932790567380225403136 945 331214810592483966115357 946 341820685381139018370419 947 352760443539530116315040 948 364044418998733150139199 949 375683260154374668550188 950 387687939275296619100133 951 400069762189011562247907 952 412840378251955172213338 953 426011790612770617106294 954 439596366777093498948231 955 453606849482546729845044 956 468056367892902144624842 957 482958449120619921374295 958 498327030087238316383554 959 514176469731354953244699 960 530521561574217069559153 961 547377546653222055333498 962 564760126833921462992679 963 582685478511421577039777 964 601170266712381959506990 965 620231659609130299328409 966 639887343457737552271769 967 660155537972232143537193 968 681055012147476098724857 969 702605100543579550450071 970 724825720045093541794470 971 747737387108594613810272 972 771361235512658521432531 973 795719034624615000583156 974 820833208198881028600699 975 846726853722086699993705 976 873423762320636138197071 977 900948439246786022906921 978 929326124959776573254176 979 958582816819014677828421 980 988745291406786568846739 981 1019841127498468265249919 982 1051898729698706478206969 983 1084947352762561073819892 984 1119017126621132814036883 985 1154139082131747502174575 986 1190345177573330163125771 987 1227668325908180811271940 988 1266142422831957292848702 989 1305802375634280983419221 990 1346684132893008126866975 991 1388824715025853951214799 992 1432262245723718771330347 993 1477035984290745474397531 994 1523186358916836754448301 995 1570755000909078635897306 996 1619784779909254624967730 997 1670319840125392971277809 998 1722405637606068466774533 999 1776088978586980417458210 1000 1831418058940150663570082