0 1 1 0 2 1 3 0 4 2 5 1 6 2 7 3 8 4 9 4 10 8 11 7 12 12 13 13 14 19 15 22 16 30 17 35 18 47 19 54 20 74 21 85 22 109 23 131 24 165 25 194 26 247 27 289 28 359 29 427 30 523 31 617 32 757 33 889 34 1078 35 1272 36 1529 37 1799 38 2154 39 2529 40 3013 41 3528 42 4187 43 4894 44 5779 45 6748 46 7937 47 9241 48 10844 49 12599 50 14724 51 17089 52 19912 53 23048 54 26801 55 30964 56 35892 57 41414 58 47886 59 55132 60 63632 61 73126 62 84195 63 96623 64 111018 65 127172 66 145861 67 166814 68 190957 69 218070 70 249193 71 284127 72 324148 73 369052 74 420343 75 477902 76 543492 77 617050 78 700691 79 794481 80 900884 81 1020119 82 1155185 83 1306426 84 1477406 85 1668830 86 1884825 87 2126452 88 2398774 89 2703151 90 3045618 91 3428283 92 3858156 93 4338071 94 4876640 95 5477410 96 6150636 97 6901286 98 7741357 99 8677259 100 9723663 101 10888496 102 12189287 103 13636521 104 15250842 105 17045491 106 19045541 107 21267341 108 23740847 109 26486921 110 29541108 111 32929345 112 36694544 113 40868609 114 45502808 115 50636973 116 56332190 117 62637436 118 69626101 119 77358216 120 85921356 121 95389352 122 105866850 123 117443827 124 130245546 125 144381771 126 160001777 127 177239263 128 196272642 129 217263739 130 240425568 131 265954521 132 294104090 133 325111738 134 359280179 135 396895323 136 438317706 137 483892561 138 534048304 139 589200059 140 649858524 141 716521257 142 789795299 143 870278534 144 958691133 145 1055748770 146 1162308025 147 1279223521 148 1407511316 149 1548193733 150 1702474288 151 1871571956 152 2056914750 153 2259953449 154 2482378542 155 2725918489 156 2992572174 157 3284393491 158 3603748372 159 3953073952 160 4335165313 161 4752915410 162 5209623394 163 5708716207 164 6254089384 165 6849797945 166 7500434630 167 8210797159 168 8986296369 169 9832599263 170 10756080085 171 11763426805 172 12862139206 173 14060106668 174 15366148087 175 16789557622 176 18340701252 177 20030520200 178 21871186328 179 23875571420 180 26057960552 181 28433479732 182 31018884570 183 33831939225 184 36892279403 185 40220751693 186 43840356323 187 47775533715 188 52053206925 189 56702013768 190 61753444243 191 67241027609 192 73201578942 193 79674321184 194 86702264263 195 94331267532 196 102611541885 197 111596663176 198 121345222685 199 131919763441 200 143388606769 201 155824726009 202 169307735396 203 183922712534 204 199762388547 205 216925883681 206 235521131734 207 255663554141 208 277478701305 209 301100878281 210 326676058885 211 354360419690 212 384323566755 213 416747016391 214 451827716474 215 489776489126 216 530821921686 217 575208724002 218 623202037511 219 675085760261 220 731167260167 221 791775685782 222 857267182568 223 928023141831 224 1004455978950 225 1087007392099 226 1176154699881 227 1272409131733 228 1376322851629 229 1488487240502 230 1609540679449 231 1740166916924 232 1881103631128 233 2033140910339 234 2197130756158 235 2373985655552 236 2564689116729 237 2770294454121 238 2991936413891 239 3230830209731 240 3488284444084 241 3765700407132 242 4064586412505 243 4386557516810 244 4733351384038 245 5106828481378 246 5508989736423 247 5941977275936 248 6408094032637 249 6909805235138 250 7449760164052 251 8030794476794 252 8655954455336 253 9328500315551 254 10051933160967 255 10829999555721 256 11666721504309 257 12566402421684 258 13533660588679 259 14573436788619 260 15691031539483 261 16892114777952 262 18182767358532 263 19569492998240 264 21059264640776 265 22659539104146 266 24378308742066 267 26224119321710 268 28206127706431 269 30334123307279 270 32618592594789 271 35070744806811 272 37702583919416 273 40526939351056 274 43557546439200 275 46809082688622 276 50297257854810 277 54038856757424 278 58051839896941 279 62355393879198 280 66970044053945 281 71917713414140 282 77221848774178 283 82907489633353 284 89001409258379 285 95532195001500 286 102530406382856 287 110028668204070 288 118061847735238 289 126667162768239 290 135884379917854 291 145755939741078 292 156327179083264 293 167646475316580 294 179765495667714 295 192739363630905 296 206626938220439 297 221491005601303 298 237398592350653 299 254421185402913 300 272635083431987 301 292121649439907 302 312967704550633 303 335265817592679 304 359114746983678 305 384619771923332 306 411893188140232 307 441054686804106 308 472231910348246 309 505560885319295 310 541186646170829 311 579263728846745 312 619956870658326 313 663441573204795 314 709904887277394 315 759546053988474 316 812577385676007 317 869224995151655 318 929729784015978 319 994348272119762 320 1063353706084787 321 1137037001612929 322 1215707987474277 323 1299696474981154 324 1389353653489502 325 1485053304026423 326 1587193364507937 327 1696197305471599 328 1812515886240273 329 1936628713290645 330 2069046209919148 331 2210311381077528 332 2361002022308433 333 2521732716496230 334 2693157311613378 335 2875971178629030 336 3070913989736590 337 3278772270823009 338 3500382516491160 339 3736634073067952 340 3988472631524611 341 4256903482441627 342 4542995431242279 343 4847884471868452 344 5172778175298852 345 5518959832675751 346 5887793374279091 347 6280728040477314 348 6699303893342320 349 7145157080783614 350 7620026012107843 351 8125757286692887 352 8664312612961667 353 9237775483524848 354 9848358924482083 355 10498413008255327 356 11190433532651848 357 11927070471479538 358 12711137693739286 359 13545622466584016 360 14433696335878726 361 15378725808613059 362 16384284533124009 363 17454165300971276 364 18592393679924590 365 19803241494991663 366 21091242082947594 367 22461205429309412 368 23918235236274296 369 25467745910978048 370 27115481658953422 371 28867535545618502 372 30730370849719860 373 32710842443495432 374 34816220671708857 375 37054215322297534 376 39433002324424198 377 41961250617304728 378 44648151992303925 379 47503451200028098 380 50537479303393698 381 53761187400249883 382 57186183892707929 383 60824772250845636 384 64689992647899527 385 68795664235359204 386 73156431649949005 387 77787812322439208 388 82706248415281464 389 87929159752411035 390 93475001808149346 391 99363324907091257 392 105614838960569487 393 112251479658063265 394 119296480720559147 395 126774447892249093 396 134711439565650925 397 143135049467693532 398 152074496613192477 399 161560717679436639 400 171626467345248693 401 182306421465680665 402 193637288971779287 403 205657927074537977 404 218409466037290597 405 231935437775715358 406 246281914953175707 407 261497654501697873 408 277634252652345762 409 294746305063666382 410 312891579583286846 411 332131194858919787 412 352529812817247288 413 374155837845537322 414 397081631195012282 415 421383733042648676 416 447143101274089089 417 474445358992684319 418 503381060396896388 419 534045966590525403 420 566541341570796252 421 600974259496670986 422 637457934137663823 423 676112061107495018 424 717063184478473947 425 760445077874352658 426 806399152364277006 427 855074880721925883 428 906630251162758931 429 961232239551904041 430 1019057314031612608 431 1080291960481286252 432 1145133243636284034 433 1213789391665736155 434 1286480419989635535 435 1363438781483406575 436 1444910059856611713 437 1531153692695043062 438 1622443742013359368 439 1719069698108584456 440 1821337335714705466 441 1929569607510100589 442 2044107595191782737 443 2165311502424243736 444 2293561711161002839 445 2429259884855732355 446 2572830141456558852 447 2724720278870737740 448 2885403077260227617 449 3055377660022720487 450 3235170939376323714 451 3425339127515932292 452 3626469340951097327 453 3839181278070823635 454 4064128999322157284 455 4302002789125907730 456 4553531130809692877 457 4819482772699514885 458 5100668918704339133 459 5397945520521765072 460 5712215706957458985 461 6044432326478907974 462 6395600640802511502 463 6766781144562261310 464 7159092551358990037 465 7573714920143591911 466 8011892964861356617 467 8474939520228889370 468 8964239209386884433 469 9481252285151434283 470 10027518693656447412 471 10604662330951401489 472 11214395544556650460 473 11858523849405502104 474 12538950913622568803 475 13257683782367737287 476 14016838398924061211 477 14818645390068349311 478 15665456178834161177 479 16559749390553912275 480 17504137619520980520 481 18501374520949722578 482 19554362300146374518 483 20666159562396238610 484 21839989600310496330 485 23079249081025538922 486 24387517215205949308 487 25768565369091736421 488 27226367207163206091 489 28765109325585937876 490 30389202469962706893 491 32103293296567105172 492 33912276777014049878 493 35821309204543718984 494 37835821908808569354 495 39961535636468203668 496 42204475711842789164 497 44570987934191455756 498 47067755333824623627 499 49701815742914103101 500 52480580311789443864 501 55411852926079749866 502 58503850664619808665 503 61765225253168829045 504 65205085663742299576 505 68833021814399471941 506 72659129529935298282 507 76694036718408532473 508 80948930935315553068 509 85435588290708691812 510 90166403883374985909 511 95154423717946708308 512 100413378302317450483 513 105957717882233518817 514 111802649524614129302 515 117964176007863089321 516 124459136746096649450 517 131305250707290568344 518 138521161568829585985 519 146126485072804025544 520 154141858842288242575 521 162588994623842668777 522 171490733236728746974 523 180871102197519849009 524 190755376321341767195 525 201170141272702988965 526 212143360389435838483 527 223704444757761555245 528 235884326886186754156 529 248715537962111248620 530 262232289064919453381 531 276470556326449943091 532 291468170440675393338 533 307264910521578134105 534 323902602741516085775 535 341425223758334470812 536 359879009396360098629 537 379312568600365393006 538 399777003163058690264 539 421326033257502786242 540 444016129313482842879 541 467906650283211156782 542 493059988876880821502 543 519541723829550400124 544 547420779824690648521 545 576769595154001847473 546 607664297787516757523 547 640184889954050704683 548 674415441958560308248 549 710444295359757041146 550 748364276291377455828 551 788272919076509021901 552 830272700980127803639 553 874471288278497012870 554 920981794557280986882 555 969923051450056915622 556 1021419892801313696678 557 1075603452502405222884 558 1132611477063039559386 559 1192588653207904773950 560 1255686951645848093643 561 1322065987347376161559 562 1391893397569863054813 563 1465345238017460761233 564 1542606398475048045540 565 1623871038360303965933 566 1709343043641344219918 567 1799236505627771616930 568 1893776223199871195482 569 1993198229054359859484 570 2097750341658901805772 571 2207692743572213128867 572 2323298587959941478288 573 2444854634050378216157 574 2572661913509995870911 575 2707036428579184795941 576 2848309884111013511851 577 2996830454460163997452 578 3152963587541217486837 579 3317092847121846194051 580 3489620795861666402133 581 3670969920292807133873 582 3861583600461197577810 583 4061927125568990603852 584 4272488758562801452641 585 4493780851167830921159 586 4726341012557821441128 587 4970733333336614219807 588 5227549668287874169526 589 5497410979762749943181 590 5780968745451127938377 591 6078906432620306746392 592 6391941042881044627903 593 6720824729800083804011 594 7066346493760762535420 595 7429333956650166777665 596 7810655221145073257205 597 8211220817460751065276 598 8631985742737919502501 599 9073951596245511889097 600 9538168816012684985366 601 10025739020412870498414 602 10537817460788821446635 603 11075615589020927372872 604 11640403746644919971872 605 12233513979837476180539 606 12856342987438039772951 607 13510355206782881079157 608 14197086045130089906736 609 14918145261953825041477 610 15675220510550420057904 611 16470081044785146597753 612 17304581600143934257818 613 18180666455523183036731 614 19100373685705742319157 615 20065839611618869133715 616 21079303459174783797120 617 22143112234515293838987 618 23259725827387836303547 619 24431722351270184433613 620 25661803732977848469574 621 26952801561243064647439 622 28307683208094397528254 623 29729558233479645510249 624 31221685088151304360504 625 32787478126302184444910 626 34430514944263571998577 627 36154544057896959193045 628 37963492936398245582755 629 39861476406395779786108 630 41852805445589897270430 631 43941996381183846689708 632 46133780514014887958695 633 48433114185131728549355 634 50845189307533699710962 635 53375444381452982445642 636 56029576017858781394152 637 58813550990352942508255 638 61733618842269575305963 639 64796325071101778541257 640 68008524919388315808138 641 71377397796316978829693 642 74910462361699043941353 643 78615592298903089088259 644 82501032811142731608163 645 86575417870251984285596 646 90847788255322217784031 647 95327610413112854676265 648 100024796180847351242931 649 104949723406340539114738 650 110113257509587057093020 651 115526774024067125060442 652 121202182165724191884482 653 127151949471481934292789 654 133389127559410871925235 655 139927379056352789526521 656 146781005749628908570865 657 153964978012936990697738 658 161494965567971729298283 659 169387369636558971334172 660 177659356550170581482637 661 186328892876720184314528 662 195414782137300422337340 663 204936703178330608357880 664 214915250278071989825931 665 225371975059048442317647 666 236329430292169442072673 667 247811215670707893090064 668 259842025647360225242329 669 272447699419746596800124 670 285655273165652404871838 671 299493034621217794496005 672 313990580112145212572526 673 329178874139681827364139 674 345090311640972016154367 675 361758783034845740131568 676 379219742182985606783603 677 397510277387674315245111 678 416669185567301928987291 679 436737049741870541503209 680 457756319981879670749033 681 479771397964839951817532 682 502828725306053301638488 683 526976875820978167781432 684 552266651900209305480332 685 578751185168615519367803 686 606486041625292159148927 687 635529331451345703921470 688 665941823699136651699949 689 697787066066831856424258 690 731131509990313617175273 691 766044641274608057642182 692 802599116516879615206733 693 840870905563065452592984 694 880939440271908869833251 695 922887769850117804892925 696 966802723055972781684239 697 1012775077558653017372156 698 1060899736776184405284858 699 1111275914504867752327942 700 1164007327690854655094739 701 1219202397684545533593014 702 1276974460358604523055485 703 1337441985460497899375341 704 1400728805613046087378913 705 1466964355366744572611049 706 1536283920752822920590147 707 1608828899776490216075397 708 1684747074337828054542319 709 1764192894058557270123678 710 1847327772543903346061544 711 1934320396599905535283327 712 2025347048980703823855732 713 2120591945231897631502534 714 2220247585253656882752388 715 2324515120199363401599393 716 2433604735386775288329444 717 2547736049891438149615548 718 2667138533557159967716040 719 2792051942151847591201611 720 2922726771466229616883549 721 3059424731147352994992302 722 3202419239132385377276960 723 3351995937543631232789792 724 3508453230984039351087911 725 3672102848169025682071197 726 3843270427913845870316856 727 4022296130493643269352104 728 4209535275482100077318313 729 4405359007174034441294853 730 4610154988791857075023124 731 4824328126676949494207530 732 5048301325767756487367901 733 5282516277669498133291264 734 5527434282727730321395598 735 5783537107523298694468751 736 6051327879320612497340436 737 6331332019008961439305733 738 6624098214198522710187512 739 6930199434143285425855647 740 7250233988293122306077262 741 7584826630290919251126728 742 7934629709369327915000599 743 8300324371118852348857113 744 8682621809746888355683812 745 9082264573968340619702478 746 9500027928826267073523042 747 9936721275766284504444316 748 10393189633456919175396135 749 10870315181878124550846539 750 11369018872380010120459229 751 11890262106449131120743256 752 12435048486111705463295604 753 13004425638944243943409700 754 13599487120867167696185594 755 14221374399944538226639247 756 14871278924632112892465987 757 15550444279970586567145153 758 16260168435454987458287278 759 17001806088373650502359566 760 17776771106660405056307402 761 18586539075374675019631934 762 19432649951191663580515656 763 20316710829365319704843996 764 21240398827912784249921618 765 22205464093859923028631411 766 23213732936693429164257894 767 24267111094267299011340298 768 25367587136738672363605385 769 26517236014222864649950613 770 27718222754207488808497424 771 28972806314894104515128465 772 30283343601010459153659884 773 31652293648779947021607241 774 33082221987135886236121633 775 34575805182428210605028697 776 36135835574299446365788045 777 37765226210584803936425332 778 39467015989550866349913111 779 41244375017984966390489913 780 43100610194139603911804728 781 45039171024755322972459264 782 47063655685912764150377656 783 49177817337707089210391765 784 51385570703302892893901482 785 53690998923195765544308395 786 56098360696111986923148895 787 58612097718273753991812778 788 61236842433406081051924526 789 63977426106187804904545994 790 66838887232544499407155751 791 69826480300540511281371878 792 72945684916372797529675753 793 76202215310364701738682631 794 79602030238657128724553248 795 83151343296729266518074552 796 86856633661738185204773322 797 90724657281144046611940156 798 94762458526007010516465348 799 98977382327865773255075491 800 103377086819093872355982779 801 107969556497204233025818232 802 112763115934630462768424794 803 117766444056142649640991586 804 122988589007190657766648704 805 128438983637156801660720292 806 134127461622718045030990579 807 140064274257271528936477880 808 146260107933684735136178837 809 152726102348455608638662940 810 159473869456771399766064966 811 166515513208855354078718336 812 173863650099496992506358403 813 181531430563644939943103169 814 189532561252558788915171119 815 197881328226089609105168351 816 206592621098395503558325655 817 215681958175569217964101722 818 225165512625519876623164120 819 235060139721727217954008813 820 245383405204489684604560603 821 256153614804678624110387343 822 267389844977162153987180079 823 279111974892577306603499590 824 291340719738439905726078446 825 304097665382231210675389836 826 317405304451582745089743308 827 331287073888476057373979417 828 345767394037041042632237307 829 360871709326489580543531463 830 376626530613586598121967555 831 393059479251184640470621611 832 410199332952426813459133295 833 428076073522531908463248989 834 446720936533383865107780340 835 466166463018656812642552462 836 486446553270762229580237027 837 507596522823630409275062190 838 529653160709159296036124125 839 552654790078123716713315885 840 576641331280444584127634370 841 601654367502930988594661889 842 627737213067021959398003981 843 654934984492542035501147199 844 683294674438229155585413150 845 712865228633577033518631537 846 743697625921634079938485933 847 775844961536504828069125364 848 809362533744782165973481621 849 844307933984588716765951494 850 880741140641799371738523167 851 918724616607841102690873428 852 958323410769802299455179256 853 999605263588812113123077927 854 1042640716929462357168992742 855 1087503228308709334135171606 856 1134269289740016908327447374 857 1183018551354638541948763083 858 1233833949989810585160607571 859 1286801842940274716169763385 860 1342012147078014279004371529 861 1399558483552284737426144819 862 1459538328291122293845984909 863 1522053168533303860224072374 864 1587208665629520558379320230 865 1655114824359956828474781902 866 1725886169025993169918422561 867 1799641926582872062294433068 868 1876506217091485108051969678 869 1956608251777307349763103341 870 2040082538996675660357747016 871 2127069098421281293010586986 872 2217713683764834452548592394 873 2312168014387400775316163828 874 2410590016126983324970551107 875 2513144071720402985211141097 876 2620001281190664244314017730 877 2731339732591483455221440599 878 2847344783515931153006227042 879 2968209353790720274589314543 880 3094134229795172900844169806 881 3225328380859653962192362497 882 3362009288217079889517414994 883 3504403286998133390255166517 884 3652745921781053189496341350 885 3807282316225257148776562923 886 3968267557339819653025018043 887 4135967094957686580987901230 888 4310657157009913323056782933 889 4492625181215661087172458025 890 4682170263828851909161047250 891 4879603626105543304445246556 892 5085249099183144187644599073 893 5299443628087597625177407058 894 5522537795613754754825213346 895 5754896366851154225816828687 896 5996898855158711456730358667 897 6248940110420951780688429817 898 6511430930452067100783536033 899 6784798696445510390169695781 900 7069488033403020421885807481 901 7365961496510886373034529119 902 7674700284470162420719209095 903 7996204980824133485579403809 904 8330996324368160167503867909 905 8679616009766501245345997650 906 9042627519545684791848799726 907 9420616988676569511630904751 908 9814194103005591892128531072 909 10223993032841603331962486398 910 10650673403056689647745925490 911 11094921301108867439480218431 912 11557450324450446229243026588 913 12039002668839215506174298102 914 12540350259129708354225667835 915 13062295924179327159303056325 916 13605674617568721055816544925 917 14171354685897819581917623141 918 14760239186488379749587723277 919 15373267256390740658852611210 920 16011415534667142746371406619 921 16675699639995994657151671090 922 17367175705721732295009761539 923 18086941974552523488535378893 924 18836140455194349190998936056 925 19615958643293607403553797498 926 20427631309153127250494639367 927 21272442354776557491333594835 928 22151726742895779650288149509 929 23066872500733023171548523347 930 24019322801356507142470506454 931 25010578125592935894404225629 932 26042198507575338477501324339 933 27115805867117284726062757522 934 28233086432228284032179501840 935 29395793255206361574717947175 936 30605748825876830029251742301 937 31864847785676760262987601698 938 33175059746427613445264474207 939 34538432217778978700870058615 940 35957093647459991217498677801 941 37433256578626234350598987904 942 38969220928755022359142808124 943 40567377394704742266800931426 944 42230210988731336728760114963 945 43960304710430210903748536612 946 45760343359762470243400510400 947 47633117496512945946448214015 948 49581527551732286330525962358 949 51608588096918288997065600578 950 53717432276911715829872913904 951 55911316412700147997776182543 952 58193624780559875781975107181 953 60567874574200701708825038327 954 63037721056832550753046461415 955 65606962910325468239170730197 956 68279547788907473700490982103 957 71059578085116554452915733864 958 73951316916016231934624798740 959 76959194337976500037028347257 960 80087813798636836285335840267 961 83341958834982429981476571464 962 86726600026803024004755628056 963 90246902215141925499250148022 964 93908231995706059343927076923 965 97716165497571569434484958808 966 101676496457909697445638337088 967 105795244603848658378207086606 968 110078664353006335664578614758 969 114533253844648990290612234660 970 119165764313881276991562304633 971 123983209821724784649819100953 972 128992877354425681532831499544 973 134202337305817851129181762173 974 139619454357086966264113418690 975 145252398768803133394415888895 976 151109658100647109305532597798 977 157200049374816334580315293482 978 163532731699695505658780772342 979 170117219370979581045839277048 980 176963395468079702004121907511 981 184081525964290695411072248180 982 191482274369888735792357339493 983 199176716928024249009383077044 984 207176358384015823188368750165 985 215493148349399260207379243391 986 224139498282881054970313908418 987 233128299111149619983481908278 988 242472939513351161213837556289 989 252187324893900878049443207165 990 262285897069216431997984189121 991 272783654694888500687673102623 992 283696174460786742317611935446 993 295039633082596156028755110674 994 306830830119334450069799487018 995 319087211647471498144546372430 996 331826894823404939683510521515 997 345068693367195638111071436043 998 358832144001682640871392128701 999 373137533882331901375494213632 1000 388005929054477914702512079698