0 1 1 0 2 0 3 0 4 0 5 0 6 0 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 2 15 2 16 3 17 3 18 4 19 4 20 5 21 6 22 7 23 8 24 10 25 11 26 13 27 15 28 18 29 20 30 24 31 27 32 32 33 36 34 42 35 48 36 56 37 63 38 73 39 83 40 96 41 108 42 125 43 141 44 162 45 183 46 209 47 236 48 270 49 304 50 346 51 390 52 443 53 498 54 565 55 635 56 719 57 807 58 911 59 1022 60 1153 61 1291 62 1453 63 1628 64 1829 65 2045 66 2295 67 2564 68 2873 69 3207 70 3589 71 4002 72 4474 73 4983 74 5562 75 6192 76 6903 77 7677 78 8550 79 9500 80 10569 81 11733 82 13038 83 14462 84 16058 85 17795 86 19737 87 21858 88 24221 89 26799 90 29671 91 32805 92 36287 93 40090 94 44307 95 48914 96 54018 97 59588 98 65752 99 72484 100 79919 101 88036 102 96996 103 106775 104 117555 105 129322 106 142274 107 156411 108 171962 109 188923 110 207563 111 227897 112 250218 113 274555 114 301254 115 330356 116 362251 117 397011 118 435072 119 476541 120 521920 121 571333 122 625367 123 684198 124 748476 125 818431 126 894823 127 977927 128 1068615 129 1167243 130 1274797 131 1391728 132 1519173 133 1657668 134 1808524 135 1972417 136 2150825 137 2344572 138 2555378 139 2784219 140 3033073 141 3303124 142 3596630 143 3915026 144 4260912 145 4635975 146 5043219 147 5484682 148 5963775 149 6482927 150 7046091 151 7656115 152 8317547 153 9033774 154 9810002 155 10650240 156 11560488 157 12545432 158 13611988 159 14765694 160 16014457 161 17364781 162 18825791 163 20405075 164 22113125 165 23958841 166 25954248 167 28109764 168 30439231 169 32954741 170 35672232 171 38605832 172 41773787 173 45192550 174 48883125 175 52864591 176 57161066 177 61794736 178 66793253 179 72182369 180 77993852 181 84257470 182 91009716 183 98285096 184 106125393 185 114570533 186 123668492 187 133465347 188 144016108 189 155374017 190 167602063 191 180761696 192 194925133 193 210163113 194 226558399 195 244192539 196 263160194 197 283555241 198 305486116 199 329060711 200 354403114 201 381637387 202 410905393 203 442349678 204 476132491 205 512417347 206 551389758 207 593237381 208 638172055 209 686408936 210 738190098 211 793761935 212 853400863 213 917389100 214 986042027 215 1059682675 216 1138670937 217 1223376144 218 1314208826 219 1411591294 220 1515991425 221 1627891750 222 1747825629 223 1876343944 224 2014054343 225 2161585664 226 2319629777 227 2488904122 228 2670196402 229 2864324457 230 3072184768 231 3294709528 232 3532918310 233 3787873035 234 4060733262 235 4352707888 236 4665115025 237 4999330594 238 5356852190 239 5739245047 240 6148210376 241 6585527652 242 7053128655 243 7553035995 244 8087442065 245 8658644698 246 9269131676 247 9921512089 248 10618607721 249 11363380238 250 12159028855 251 13008914004 252 13916661921 253 14886083508 254 15921287531 255 17026594600 256 18206658062 257 19466374276 258 20811012188 259 22246118060 260 23777655549 261 25411905190 262 27155614288 263 29015892045 264 31000370271 265 33117092594 266 35374688305 267 37782255599 268 40349547680 269 43086851561 270 46005187862 271 49116183010 272 52432285292 273 55966630917 274 59733275645 275 63747056119 276 68023838602 277 72580373685 278 77434565439 279 82605319616 280 88112832478 281 93978434579 282 100224901532 283 106876290895 284 113958278429 285 121497989048 286 129524358191 287 138067958843 288 147161390516 289 156839100310 290 167137804244 291 178096302877 292 189755934686 293 202160389405 294 215356196860 295 229392535439 296 244321761771 297 260199215963 298 277083792473 299 295037745326 300 314127304297 301 334422478208 302 355997723344 303 378931746441 304 403308226012 305 429215619826 306 456747944770 307 486004586577 308 517091146328 309 550119255552 310 585207491452 311 622481202640 312 662073499856 313 704125091451 314 748785360079 315 796212211534 316 846573240307 317 900045599604 318 956817265045 319 1017086924893 320 1081065354723 321 1148975333926 322 1221053136596 323 1297548483392 324 1378726160191 325 1464866006908 326 1556264680292 327 1653235687284 328 1756111299383 329 1865242643491 330 1981001783566 331 2103781871653 332 2233999417227 333 2372094510115 334 2518533289045 335 2673808252521 336 2838440946481 337 3012982370080 338 3198015909157 339 3394157851965 340 3602060584389 341 3822413238166 342 4055945174764 343 4303426776498 344 4565673252560 345 4843545595513 346 5137954732786 347 5449862677032 348 5780287057934 349 6130302484592 350 6501045501749 351 6893716193506 352 7309583596020 353 7749987582213 354 8216344777539 355 8710150751806 356 9232986494373 357 9786520955207 358 10372518124682 359 10992839975217 360 11649454206877 361 12344437629570 362 13079984648908 363 13858411144921 364 14682163759458 365 15553824342147 366 16476120121197 367 17451928772640 368 18484289570794 369 19576409159156 370 20731673765716 371 21953655768062 372 23246127081247 373 24613066598909 374 26058674880902 375 27587382575085 376 29203866519676 377 30913059272073 378 32720166769980 379 34630679079617 380 36650389782041 381 38785408085084 382 41042180091850 383 43427502443489 384 45948545660064 385 48612869472973 386 51428448458190 387 54403689251500 388 57547458685322 389 60869103112754 390 64378479302166 391 68085976086308 392 72002548303672 393 76139741036051 394 80509726882605 395 85125333086017 396 90000082475118 397 95148223779036 398 100584776621152 399 106325565373120 400 112387268583274 401 118787456774553 402 125544646755088 403 132678343764667 404 140209101171563 405 148158567443968 406 156549551747937 407 165406076280314 408 174753448360588 409 184618318677359 410 195028760541710 411 206014334682625 412 217606176349246 413 229837067374443 414 242741531913601 415 256355916518868 416 270718495394788 417 285869559337112 418 301851531424681 419 318709065777296 420 336489174726498 421 355241338395138 422 375017644512063 423 395872909950244 424 417864834408050 425 441054135180414 426 465504716089368 427 491283816829378 428 518462198683658 429 547114309963357 430 577318490138256 431 609157153058588 432 642717011328118 433 678089279106984 434 715369918757429 435 754659865245619 436 796065297219810 437 839697885257357 438 885675089793917 439 934120435610246 440 985163839289184 441 1038941912627203 442 1095598322484400 443 1155284126092679 444 1218158166490900 445 1284387442922058 446 1354147545384632 447 1427623063674443 448 1505008064841590 449 1586506544815042 450 1672332952980122 451 1762712690619785 452 1857882687261457 453 1958091950648192 454 2063602199864825 455 2174688472038418 456 2291639817795932 457 2414759970311499 458 2544368109217382 459 2680799598221476 460 2824406824080148 461 2975560009654070 462 3134648135256189 463 3302079834570232 464 3478284406420721 465 3663712801774908 466 3858838734645144 467 4064159769220432 468 4280198539516200 469 4507503946445105 470 4746652496789109 471 4998249621035743 472 5262931143131463 473 5541364730997225 474 5834251509697769 475 6142327657560226 476 6466366176633957 477 6807178648666048 478 7165617177913823 479 7542576322630695 480 7938995226807439 481 8355859744183131 482 8794204777109905 483 9255116611811115 484 9739735484132975 485 10249258146608834 486 10784940682828312 487 11348101328655383 488 11940123559040612 489 12562459187969133 490 13216631753625360 491 13904239924016244 492 14626961208935825 493 15386555700592293 494 16184870143546972 495 17023842042542784 496 17905504124330627 497 18831988847992392 498 19805533295861980 499 20828484124755251 500 21903302926724214 501 23032571663340715 502 24218998540629528 503 25465423972552238 504 26774827018718250 505 28150331927332117 506 29595215188870669 507 31112912713571603 508 32707027558982218 509 34381337802275788 510 36139805005091805 511 37986582846335718 512 39926026393667243 513 41962701568692931 514 44101395300636682 515 46347125902563246 516 48705154189885247 517 51180994853294355 518 53780428632458909 519 56509514779403799 520 59374604385800861 521 62382354039277290 522 65539740411915058 523 68854075221119393 524 72333021196895159 525 75984608469357972 526 79817252042844284 527 83839769743429153 528 88061401339818645 529 92491828196170991 530 97141194192600852 531 102020127242074334 532 107139762176970716 533 112511764303435475 534 118148354435809464 535 124062334677294782 536 130267115800687263 537 136776745461631640 538 143605938141772291 539 150770106019719046 540 158285391712538034 541 166168702049639192 542 174437743870003456 543 183111060966643460 544 192208073219845472 545 201749117004207714 546 211755487963722198 547 222249485199368437 548 233254458019538886 549 244794854255121296 550 256896271348380884 551 269585509173827404 552 282890625861556327 553 296840995535806840 554 311467369304441138 555 326801938364352724 556 342878400626985821 557 359732029680186701 558 377399747562010803 559 395920200111957469 560 415333836451220417 561 435682991304215672 562 457011971792747190 563 479367147360732638 564 502797044544187219 565 527352445187974506 566 553086489912571247 567 580054785373295267 568 608315517208320242 569 637929567157720939 570 668960636347161939 571 701475373156057042 572 735543507767218895 573 771237991752626883 574 808635144901047796 575 847814807575776677 576 888860500922016858 577 931859593143537186 578 976903474289005822 579 1024087737696090437 580 1073512370660938401 581 1125281952408485556 582 1179505862064442170 583 1236298494629441795 584 1295779487797792229 585 1358073957543388563 586 1423312745464286417 587 1491632675729583034 588 1563176824776424148 589 1638094801519613785 590 1716543041387729411 591 1798685111864069488 592 1884692033021361317 593 1974742610643668684 594 2069023785608114589 595 2167730997032835498 596 2271068563059018128 597 2379250076683581057 598 2492498820716193304 599 2611048199186939149 600 2735142189494642223 601 2865035812530073386 602 3000995625293965156 603 3143300233149382542 604 3292240826471024052 605 3448121738736506843 606 3611261031077421996 607 3781991100239343814 608 3960659315239947931 609 4147628679576464997 610 4343278524558206105 611 4548005230518370687 612 4762222981782692845 613 4986364552051504861 614 5220882126393731446 615 5466248156410399382 616 5722956255105475001 617 5991522127924715443 618 6272484546858011544 619 6566406363969438357 620 6873875571631042274 621 7195506405727895831 622 7531940499513026934 623 7883848084286673543 624 8251929245003389896 625 8636915226890366003 626 9039569801632689111 627 9460690689119178165 628 9901111043783397318 629 10361701001449484057 630 10843369296223340269 631 11347064943258889676 632 11873778997478700354 633 12424546384002369829 634 13000447810932925945 635 13602611760186855222 636 14232216567621984549 637 14890492588088025043 638 15578724457297348031 639 16298253446086648586 640 17050479919649572418 641 17836865897269097590 642 18658937725852437454 643 19518288862766194109 644 20416582782044801243 645 21355555999449740776 646 22337021231270361253 647 23362870682340721042 648 24435079479030252798 649 25555709242695592562 650 26726911820275793929 651 27950933167547452295 652 29230117402704388858 653 30566911025831275746 654 31963867322978360265 655 33423650950482231018 656 34949042719352063044 657 36542944575465410639 658 38208384796575971653 659 39948523402008539602 660 41766657797300308059 661 43666228649826483979 662 45650826019010823200 663 47724195737354799900 664 49890246067314072158 665 52153054630494654908 666 54516875635715922600 667 56986147402694607507 668 59565500209518695665 669 62259764460992568645 670 65073979207750072898 671 68013401013600941148 672 71083513202846299181 673 74290035485470741829 674 77638933993911791177 675 81136431729817659872 676 84789019456589421569 677 88603467036696908726 678 92586835251796547428 679 96746488105295932965 680 101090105647779784027 681 105625697325679610053 682 110361615896148069795 683 115306571909355813233 684 120469648803886870592 685 125860318617387564252 686 131488458361049073322 687 137364367061124261034 688 143498783519159910594 689 149902904795318002178 690 156588405469776210437 691 163567457687887348074 692 170852752047629121572 693 178457519336472355526 694 186395553179982766416 695 194681233610897619856 696 203329551625033066473 697 212356134734549851844 698 221777273589259155879 699 231609949678468002174 700 241871864188671290004 701 252581468031773951335 702 263757993124093025347 703 275421484933231208677 704 287592836378365724851 705 300293823103692404396 706 313547140216232267776 707 327376440510661276886 708 341806374278426747445 709 356862630727020460891 710 372571981113160961616 711 388962323619274131017 712 406062730083970187143 713 423903494619773868106 714 442516184236237437632 715 461933691505931096312 716 482190289399406042206 717 503321688331260285689 718 525365095551932559678 719 548359276932434527048 720 572344621285778442730 721 597363207277863881154 722 623458873081371816676 723 650677288831491682857 724 679066032047519488024 725 708674666085780300360 726 739554821799148066588 727 771760282475846910942 728 805347072244856677499 729 840373548028486287704 730 876900495242352138462 731 914991227331922303730 732 954711689359701707258 733 996130565741582928589 734 1039319392361283112879 735 1084352673171580038225 736 1131308001527184132391 737 1180266186369056944297 738 1231311383522073503960 739 1284531232237908489680 740 1340016997263350722910 741 1397863716579040968537 742 1458170355108471158388 743 1521039964556503813621 744 1586579849698302197090 745 1654901741293423472653 746 1726121975968560101468 747 1800361683260498077779 748 1877746980187015800000 749 1958409173555557752128 750 2042484970403404132074 751 2130116696798988495749 752 2221452525425991472802 753 2316646712201350750545 754 2415859842378759148950 755 2519259086412104087111 756 2627018466062544942608 757 2739319131048950999856 758 2856349646759885355383 759 2978306293354231445637 760 3105393376805661051167 761 3237823552247709219749 762 3375818160214372167881 763 3519607576165123209933 764 3669431573931908111653 765 3825539703511792105790 766 3988191683888593816180 767 4157657811344836585538 768 4334219383996478642837 769 4518169143052501842803 770 4709811731584572728903 771 4909464171352929842831 772 5117456358530340816998 773 5334131578917969849587 774 5559847043555784237423 775 5794974445372903727040 776 6039900537845797741171 777 6295027736365467243869 778 6560774743351597109648 779 6837577197875072179866 780 7125888350902074419369 781 7426179766986266106561 782 7738942053603069701568 783 8064685619022882834812 784 8403941460003985256814 785 8757261980277967316586 786 9125221841201565434959 787 9508418845629798511747 788 9907474856484306661583 789 10323036751160381639753 790 10755777413353980087362 791 11206396763547872038689 792 11675622829853513311659 793 12164212860551045282468 794 12672954480147834793053 795 13202666890409367053661 796 13754202118315861024465 797 14328446312518649566131 798 14926321090392444595911 799 15548784937387228325774 800 16196834660929196603882 801 16871506900714374041753 802 17573879697808939745451 803 18305074124550757072699 804 19066255977842886686275 805 19858637537996255161605 806 20683479395902060628779 807 21542092350866454679917 808 22435839382091880276705 809 23366137696326665492472 810 24334460854886062526172 811 25342340982770093913854 812 26391371063316365622968 813 27483207321332769881148 814 28619571698400525633076 815 29802254423529078280162 816 31033116683124170413533 817 32314093393705495444334 818 33647196081626096879171 819 35034515873504467927311 820 36478226601933787368842 821 37980588030474969427162 822 39543949202833213195261 823 41170751920543188803584 824 42863534354422508622098 825 44624934794461504305815 826 46457695543795408718770 827 48364666961796153638989 828 50348811662344743171305 829 52413208872718840983541 830 54561058959601936538287 831 56795688128076482439636 832 59120553300585513922220 833 61539247182185543267646 834 64055503519588499457998 835 66673202560810944765220 836 69396376723479336579073 837 72229216479142629618488 838 75176076462232436327361 839 78241481811595585676428 840 81430134753874129350195 841 84746921437274623131046 842 88196919025683171598852 843 91785403062331690920453 844 95517855113703276128815 845 99399970703595913172323 846 103437667548817392718044 847 107637094107198270920894 848 112004638450238244355405 849 116546937471898158472103 850 121270886446757200447830 851 126183648949934970817956 852 131292667152968297765284 853 136605672508996588218475 854 142130696842486896366182 855 147876083857878103088584 856 153850501083492806306796 857 160062952266198746127988 858 166522790234367375352756 859 173239730245796244552387 860 180223863839429404988954 861 187485673208815772441852 862 195036046117520111827663 863 202886291375794845900016 864 211048154900208428430054 865 219533836377008620330329 866 228356006552505471239890 867 237527825172831766507312 868 247062959598070523429284 869 256975604114804069224419 870 267280499973903102781572 871 277992956179432885947673 872 289128871057456858818480 873 300704754632572408294166 874 312737751843063571997993 875 325245666624607872581711 876 338246986895679379558585 877 351760910476842998824996 878 365807371979503322448469 879 380407070698727419716818 880 395581499548301770207892 881 411352975075245855422647 882 427744668594727687013593 883 444780638485398547744893 884 462485863689079125188008 885 480886278457814520377251 886 500008808395433433107062 887 519881407839849614500382 888 540533098636675683331942 889 561994010353844236562053 890 584295421991489519927349 891 607469805240494650993432 892 631550869347906890833720 893 656573607646607600302251 894 682574345811673641958001 895 709590791905089543328084 896 737662088275786965447187 897 766828865381255382710398 898 797133297602567531865112 899 828619161123982562142986 900 861331893954187977408505 901 895318658165620660996288 902 930628404434521233297188 903 967311938963823352144504 904 1005421992877527637710843 905 1045013294174734737180860 906 1086142642338413478294165 907 1128868985693592451328883 908 1173253501616938838645719 909 1219359679699399022456016 910 1267253407971246939663382 911 1317003062298707133635805 912 1368679599069409921554985 913 1422356651283880261072624 914 1478110628178796166129647 915 1536020818507833668129241 916 1596169497614919641266876 917 1658642038434947167475301 918 1723527026566510175414292 919 1790916379561616094791916 920 1860905470587364758813944 921 1933593256615170014373363 922 2009082411303688923517828 923 2087479462742417192407017 924 2168894936234090067677664 925 2253443502295048033732643 926 2341244130064535069848595 927 2432420246315165914782244 928 2527099900269272864718519 929 2625415934427384272133017 930 2727506161628266612306274 931 2833513548561802815207673 932 2943586405969907707354322 933 3057878585772849482730182 934 3176549685373068190860090 935 3299765259391108156310318 936 3427697039103845329387224 937 3560523159858107282712617 938 3698428396749241172731934 939 3841604408857527713773608 940 3990249992352745050783830 941 4144571342780993482454576 942 4304782326866303972338596 943 4471104764163865995598534 944 4643768718921190395159320 945 4823012802508385145574954 946 5009084486799336069937743 947 5202240428891044228842918 948 5402746807570189659495692 949 5610879671942099660449556 950 5826925302660396259234045 951 6051180586202409827457085 952 6283953402659900119196243 953 6525563027522201682911321 954 6776340547954806930157980 955 7036629294084803093429846 956 7306785285832007667115690 957 7587177695833945514084428 958 7878189329041866926184723 959 8180217119575274074807239 960 8493672645453208668414566 961 8818982661831870661378000 962 9156589653410761064776053 963 9506952406681992638055930 964 9870546602731988745404936 965 10247865431318466657964611 966 10639420226982253937138543 967 11045741127968486006209203 968 11467377758770592209000689 969 11904899937126905603701821 970 12358898406340937137694533 971 12829985593814324477819615 972 13318796396725165364632581 973 13825988995804078009665102 974 14352245698206682971961530 975 14898273810502626349893944 976 15464806542850436649838344 977 16052603945450865527620256 978 16662453878423534498303988 979 17295173016277149640944835 980 17951607888198908565290009 981 18632635955416405913547308 982 19339166726944099515449559 983 20072142915056495472001513 984 20832541631892575904966472 985 21621375628628687699972376 986 22439694578723316339798600 987 23288586406772658906860591 988 24169178664586202000201457 989 25082639956130007332627230 990 26030181413060046408802342 991 27013058222609656312921867 992 28032571209674452995038737 993 29090068474983244791908626 994 30186947091327675794320451 995 31324654859872270686066891 996 32504692128655977667292717 997 33728613675449261921575471 998 34998030657225802079979345 999 36314612628565109016678029 1000 37680089631403320046359675