0 1 1 0 2 1 3 1 4 1 5 2 6 3 7 3 8 4 9 5 10 8 11 9 12 12 13 13 14 17 15 22 16 28 17 34 18 42 19 48 20 59 21 71 22 88 23 106 24 130 25 151 26 181 27 210 28 250 29 295 30 354 31 417 32 494 33 577 34 675 35 780 36 909 37 1053 38 1231 39 1431 40 1668 41 1930 42 2240 43 2573 44 2963 45 3392 46 3896 47 4461 48 5129 49 5873 50 6742 51 7710 52 8816 53 10043 54 11439 55 12981 56 14742 57 16708 58 18957 59 21482 60 24364 61 27582 62 31236 63 35299 64 39876 65 44949 66 50645 67 56949 68 64039 69 71923 70 80805 71 90693 72 101822 73 114193 74 128064 75 143455 76 160630 77 179633 78 200777 79 224122 80 250078 81 278782 82 310713 83 346067 84 385409 85 428959 86 477361 87 530882 88 590220 89 655710 90 728161 91 807934 92 896008 93 992902 94 1099791 95 1217401 96 1347180 97 1490009 98 1647625 99 1821084 100 2012333 101 2222652 102 2454261 103 2708625 104 2988300 105 3295025 106 3631721 107 4000560 108 4405040 109 4847890 110 5333374 111 5864905 112 6447516 113 7085353 114 7784285 115 8549161 116 9386758 117 10302778 118 11304945 119 12399902 120 13596542 121 14902580 122 16328378 123 17883167 124 19579173 125 21427644 126 23443206 127 25639360 128 28033429 129 30641496 130 33483705 131 36578947 132 39950576 133 43620504 134 47615639 135 51961404 136 56688616 137 61826778 138 67411448 139 73476976 140 80064844 141 87215761 142 94978365 143 103401028 144 112540967 145 122455161 146 133210485 147 144873685 148 157522172 149 171233646 150 186097405 151 202203136 152 219653574 153 238552184 154 259016688 155 281166397 156 305136715 157 331065668 158 359110092 159 389430862 160 422210315 161 457636580 162 495921918 163 537285560 164 581973884 165 630241502 166 682372890 167 738662378 168 799437340 169 865036526 170 935835617 171 1012223616 172 1094630404 173 1183502077 174 1279330680 175 1382628090 176 1493958990 177 1613913140 178 1743140631 179 1882322921 180 2032210249 181 2193590158 182 2367328009 183 2554332769 184 2755600032 185 2972176090 186 3205203616 187 3455883113 188 3725522772 189 4015497121 190 4327300166 191 4662502357 192 5022807615 193 5410007820 194 5826045703 195 6272967226 196 6752989836 197 7268453778 198 7821895663 199 8415996367 200 9053661211 201 9737963705 202 10472230625 203 11259982919 204 12105026300 205 13011387418 206 13983412532 207 15025698859 208 16143200410 209 17341156473 210 18625204963 211 20001306233 212 21475867357 213 23055661461 214 24747962475 215 26560463789 216 28501425009 217 30579588624 218 32804341821 219 35185629901 220 37734130963 221 40461167121 222 43378890867 223 46500191134 224 49838894666 225 53409665844 226 57228221905 227 61311229714 228 65676535880 229 70343058790 230 75331037827 231 80661920447 232 86358630495 233 92445453889 234 98948327708 235 105894724495 236 113313969672 237 121237127221 238 129697347443 239 138729759196 240 148371850542 241 158663363994 242 169646713060 243 181366878015 244 193871855519 245 207212556668 246 221443290059 247 236621658413 248 252809081866 249 270070693596 250 288475903531 251 308098298467 252 329016250513 253 351312820131 254 375076418034 255 400400713225 256 427385351040 257 456135875433 258 486764512182 259 519390110337 260 554139007938 261 591145001890 262 630550301939 263 672505538517 264 717170810452 265 764715726002 266 815320551075 267 869176282100 268 926485892008 269 987464440251 270 1052340421257 271 1121355908848 272 1194768021968 273 1272849109167 274 1355888335698 275 1444191922319 276 1538084866762 277 1637911239022 278 1744036058283 279 1856845655437 280 1976749717444 281 2104181743086 282 2239601281633 283 2383494501644 284 2536376667344 285 2698792848236 286 2871320656334 287 3054571126207 288 3249191734356 289 3455867452797 290 3675324074312 291 3908329444435 292 4155697098479 293 4418287689965 294 4697012955828 295 4992837347773 296 5306782362731 297 5639928396314 298 5993419462667 299 6368465308289 300 6766346558859 301 7188417116732 302 7636109789292 303 8110939005589 304 8614506970958 305 9148506765495 306 9714729094542 307 10315065834590 308 10951517486586 309 11626197257585 310 12341339308856 311 13099303472908 312 13902584386571 313 14753816903590 314 15655786197361 315 16611433922284 316 17623869337931 317 18696376282061 318 19832425379567 319 21035681874365 320 22310019017796 321 23659526832250 322 25088526763677 323 26601581485210 324 28203510930011 325 29899403231934 326 31694632287243 327 33594869956508 328 35606105293728 329 37734658172006 330 39987200358999 331 42370770741120 332 44892798498268 333 47561120172099 334 50384005216878 335 53370175223473 336 56528832169700 337 59869680085652 338 63402956334009 339 67139455992538 340 71090566432062 341 75268294682245 342 79685305568770 343 84354952282900 344 89291318369889 345 94509251759869 346 100024410889597 347 105853302514128 348 112013332314621 349 118522846818370 350 125401188920546 351 132668744315270 352 140347002370598 353 148458607549636 354 157027426153594 355 166078603223459 356 175638635770983 357 185735435772441 358 196398410577087 359 207658532781654 360 219548428698573 361 232102456005824 362 245356801329412 363 259349566695889 364 274120877291104 365 289712977797395 366 306170351404642 367 323539827021902 368 341870710623822 369 361214904330606 370 381627051105985 371 403164666766581 372 425888299138389 373 449861674074227 374 475151870327665 375 501829480818360 376 529968804566056 377 559648024648450 378 590949418735046 379 623959555280436 380 658769524425719 381 695475154178040 382 734177263559862 383 774981900791181 384 818000620857890 385 863350747945677 386 911155680026836 387 961545178262023 388 1014655701606062 389 1070630726426590 390 1129621114604810 391 1191785466911164 392 1257290528426468 393 1326311579445004 394 1399032882076171 395 1475648112572956 396 1556360853067434 397 1641385069190716 398 1730945651050646 399 1825278940198406 400 1924633324085000 401 2029269816772025 402 2139462711493936 403 2255500219821978 404 2377685187496506 405 2506335797303030 406 2641786353776546 407 2784388055683065 408 2934509855841141 409 3092539309599868 410 3258883516730842 411 3433970053027093 412 3618248001876603 413 3812188977053940 414 4016288252662507 415 4231065886265898 416 4457067957319579 417 4694867801293532 418 4945067368075943 419 5208298579254012 420 5485224819352517 421 5776542429453868 422 6082982345175598 423 6405311740661542 424 6744335827741662 425 7100899665002626 426 7475890133226267 427 7870237924754161 428 8284919711149106 429 8720960329020070 430 9179435156752749 431 9661472514270876 432 10168256267156366 433 10701028459212964 434 11261092164079346 435 11849814371353417 436 12468629107574122 437 13119040598770053 438 13802626684874203 439 14521042283588988 440 15276023124731372 441 16069389542877347 442 16903050560677866 443 17779008040911120 444 18699361151390627 445 19666310910766017 446 20682165072080270 447 21749343101395421 448 22870381521662003 449 24047939368140083 450 25284804038954355 451 26583897275373167 452 27948281569524588 453 29381166721305260 454 30885916856823243 455 32466057616982754 456 34125283843447681 457 35867467456882709 458 37696665870765041 459 39617130621076635 460 41633316572149119 461 43749891364271055 462 45971745480859684 463 48304002585623931 464 50752030526424685 465 53321452640051773 466 56018159774544010 467 58848322646852477 468 61818404972938627 469 64935176971033214 470 68205729697115895 471 71637489795144948 472 75238235144363304 473 79016110967943669 474 82979646909566346 475 87137774623619105 476 91499846411953200 477 96075654433306331 478 100875451046191407 479 105909969791435072 480 111190447603624517 481 116728647736536160 482 122536884021629033 483 128628045921554128 484 135015625028521628 485 141713742445414133 486 148737177730776295 487 156101398820361520 488 163822593639619381 489 171917702793009056 490 180404454079607171 491 189301398193856066 492 198627946397372262 493 208404409492933608 494 218652038925690546 495 229393069313581851 496 240650763273342746 497 252449457814662416 498 264814613211738834 499 277772863594475296 500 291352070214281123 501 305581376594684247 502 320491266569914199 503 336113624389449389 504 352481797942001968 505 369630664244335235 506 387596698302797835 507 406418044459518398 508 426134591389327793 509 446788049826334235 510 468422034247014378 511 491082147554843120 512 514816070057544038 513 539673651745358573 514 565707009227769558 515 592970626298744518 516 621521459555326355 517 651419047998819897 518 682725628113869295 519 715506253310829499 520 749828919300273796 521 785764694240418061 522 823387855302721687 523 862776030450839979 524 904010347159883817 525 947175586823811051 526 992360346664519716 527 1039657207843338084 528 1089162911679200468 529 1140978542626362391 530 1195209720012842881 531 1251966797142711382 532 1311365069865718489 533 1373524993167642955 534 1438572407991802343 535 1506638776794701244 536 1577861430160785655 537 1652383822927866432 538 1730355802270619577 539 1811933886144644905 540 1897281554668848027 541 1986569552801222125 542 2079976207026581057 543 2177687754363571117 544 2279898686558499282 545 2386812107725801086 546 2498640108456909414 547 2615604154607073896 548 2737935493942731309 549 2865875578803499733 550 2999676508127576472 551 3139601486936866909 552 3285925306801736207 553 3438934845321447627 554 3598929588320759484 555 3766222172735932847 556 3941138954081108231 557 4124020596407154024 558 4315222688844269172 559 4515116386580495538 560 4724089080581759690 561 4942545093845586759 562 5170906408721746341 563 5409613423035347856 564 5659125739785286094 565 5919922988098725014 566 6192505680470074608 567 6477396103910507579 568 6775139250307422099 569 7086303783570019817 570 7411483049147062986 571 7751296123448736256 572 8106388909068122174 573 8477435273296435605 574 8865138236161258184 575 9270231205456159846 576 9693479265347685133 577 10135680516011461171 578 10597667471265204222 579 11080308511637060600 580 11584509400238618677 581 12111214858870892872 582 12661410212148592173 583 13236123097059678151 584 13836425246179429748 585 14463434341940918273 586 15118315950632994810 587 15802285533515497491 588 16516610544193817675 589 17262612609634799155 590 18041669804465436524 591 18855219015934227405 592 19704758409706613903 593 20591849993885679191 594 21518122291991006970 595 22485273122311977532 596 23495072494969058680 597 24549365624136847441 598 25650076067402236017 599 26799208989767479887 600 27998854564949452165 601 29251191511558220511 602 30558490777530207415 603 31923119370489359653 604 33347544348184215355 605 34834336966792404655 606 36386177002066668540 607 38005857241265638098 608 39696288161738479784 609 41460502794296145735 610 43301661788206509493 611 45223058676182326878 612 47228125357237898227 613 49320437796059851432 614 51503721957877943972 615 53781859977786410992 616 56158896584673040647 617 58639045779038533740 618 61226697786087153327 619 63926426283723609395 620 66742995928120541895 621 69681370176862311125 622 72746719433675530852 623 75944429515155260238 624 79280110464912321995 625 82759605715993192935 626 86389001628501141456 627 90174637403758536504 628 94123115403539046819 629 98241311876261100424 630 102536388120374493417 631 107015802087450847789 632 111687320457032619884 633 116559031186440525513 634 121639356569540653105 635 126937066808443713453 636 132461294134210849404 637 138221547481396975722 638 144227727754723656267 639 150490143693662586242 640 157019528375595270420 641 163827056364397457122 642 170924361547661833635 643 178323555670612412152 644 186037247612682161003 645 194078563416167881319 646 202461167115919418126 647 211199282381016338448 648 220307715020605263558 649 229801876366562501984 650 239697807588605548066 651 250012204956383551236 652 260762446107836933424 653 271966617340370158190 654 283643541987994696704 655 295812809903135525962 656 308494808110336228433 657 321710752652839394104 658 335482721703575473939 659 349833689963982990371 660 364787564426731096007 661 380369221528398039009 662 396604545772998538944 663 413520469855254218060 664 431145016369635904786 665 449507341137166325528 666 468637778241489325447 667 488567886809566377097 668 509330499634369284575 669 530959773678599556134 670 553491242563074151816 671 576961871082812742266 672 601410111861165289699 673 626875964189372872604 674 653401035169072127152 675 681028603209870863742 676 709803684007184054781 677 739773099057629342520 678 770985546845409345635 679 803491676762647146159 680 837344165905990918999 681 872597798818684332007 682 909309550330029031955 683 947538671568310682929 684 987346779309495976534 685 1028797948745321251480 686 1071958809844272068631 687 1116898647397292217325 688 1163689504933711449027 689 1212406292608114824452 690 1263126899256405312972 691 1315932308731308005646 692 1370906720729114399333 693 1428137676228074026193 694 1487716187764577852960 695 1549736874678384621592 696 1614298103568224515090 697 1681502134100616673687 698 1751455270429370319500 699 1824268018381010458566 700 1900055248680771668344 701 1978936366387744089144 702 2061035486832125950895 703 2146481618237544939358 704 2235408851340980217700 705 2327956556208751559557 706 2424269586582049239728 707 2524498491967219918842 708 2628799737826679358252 709 2737335934103746548671 710 2850276072461246555810 711 2967795772486674311500 712 3090077537269426524704 713 3217311018623950579516 714 3349693292391792470278 715 3487429144119157950339 716 3630731365572473414713 717 3779821062413230660543 718 3934927973526362667028 719 4096290802350273165774 720 4264157560737017995758 721 4438785925719983444438 722 4620443609754533790027 723 4809408744840731608910 724 5005970281133424338253 725 5210428400483207015279 726 5423094945556270564638 727 5644293865013717111603 728 5874361675444012771062 729 6113647940568896431534 730 6362515768465047315230 731 6621342327364311947559 732 6890519380826475660406 733 7170453842892716323987 734 7461568354068658794080 735 7764301878793546723096 736 8079110325302872349717 737 8406467188592703371841 738 8746864217455253527748 739 9100812106349311999693 740 9468841213141448853955 741 9851502303540974424501 742 10249367323335461207839 743 10663030199313548705261 744 11093107670057609173555 745 11540240147561465468647 746 12005092610936793760985 747 12488355533236946366562 748 12990745842748532078499 749 13513007919858512406647 750 14055914630939887603090 751 14620268400448629650838 752 15206902322774200623968 753 15816681315127565439848 754 16450503313115387162788 755 17109300510382580609138 756 17794040644086035313684 757 18505728327687697898101 758 19245406432952561073998 759 20014157522754290105097 760 20813105336706163657048 761 21643416331343899418336 762 22506301277020224325629 763 23403016913371458848736 764 24334867665668756569271 765 25303207424058209590867 766 26309441388166178246801 767 27355027979228575804002 768 28441480822395397139461 769 29570370801534599067898 770 30743328189373169315074 771 31962044855476113517058 772 33228276555099859984503 773 34543845301609319027908 774 35910641825706571488875 775 37330628124361600648651 776 38805840102918299950684 777 40338390313480985987446 778 41930470793294761857916 779 43584356006454601175757 780 45302405892912655494118 781 47087069028364335657169 782 48940885899256216619725 783 50866492296759306619567 784 52866622834242983707309 785 54944114592374827416750 786 57101910896693956775332 787 59343065232084831334946 788 61670745299332963146725 789 64088237218512668810988 790 66598949884745161544090 791 69206419481423351204271 792 71914314156823193717379 793 74726438869569055999019 794 77646740409281246517535 795 80679312598271283992930 796 83828401681050500292954 797 87098411907945262109574 798 90493911320053653993885 799 94019637742296933212462 800 97680504992304478267008 801 101481609312380518161520 802 105428236032832422504136 803 109525866474441203810316 804 113780185098934424147278 805 118197086915813864068551 806 122782685155019834714233 807 127543319214397207023917 808 132485562892109655158955 809 137616232913622642148462 810 142942397764110928751946 811 148471386836611182527585 812 154210799907531619972544 813 160168516950586195776949 814 166352708301570902478495 815 172771845185846484324567 816 179434710621803411925513 817 186350410713023480755771 818 193528386343328646838574 819 200978425288338696985502 820 208710674758703784302818 821 216735654389602259528247 822 225064269692710403762465 823 233707825986269535604049 824 242678042820567728679903 825 251987068915567696853316 826 261647497629183761337415 827 271672382974121751448451 828 282075256203050671924460 829 292870142981283769229148 830 304071581168089602376791 831 315694639227161648695923 832 327754935288810639935781 833 340268656885852563017470 834 353252581387298659497801 835 366724097153365452994594 836 380701225437559750629029 837 395202643061010709732275 838 410247705886567866301978 839 425856473119609626974742 840 442049732464970007315392 841 458849026168828573790148 842 476276677976995087362597 843 494355821040471811847800 844 513110426801892817502049 845 532565334895907802992429 846 552746284099430234625814 847 573679944367156543054488 848 595393949990757333445455 849 617916933919648888516839 850 641278563284395519551726 851 665509576163322919560512 852 690641819636219363694162 853 716708289168555794017780 854 743743169373114147691885 855 771781876195494850772189 856 800861100573602444358712 857 831018853620820939658118 858 862294513386397090139820 859 894728873246197915779656 860 928364191981003830422205 861 963244245599187308859135 862 999414380964821146252768 863 1036921571291995051140626 864 1075814473570523688920541 865 1116143487988016221277385 866 1157960819417903976690142 867 1201320541042868380796652 868 1246278660187972610656346 869 1292893186437711391523114 870 1341224202116302349374928 871 1391333935210526106625579 872 1443286834819792812501060 873 1497149649218177194647151 874 1552991506618811133700064 875 1610883998731176813708491 876 1670901267207782946488157 877 1733120093076960738059429 878 1797619989264766343831686 879 1864483296309342673218218 880 1933795281377673996310277 881 2005644240695158273910063 882 2080121605505354203254924 883 2157322051677890955187362 884 2237343613089833909495295 885 2320287798906584063147298 886 2406259714896089050618495 887 2495368188911094962067296 888 2587725900682284278910311 889 2683449516066276142172458 890 2782659825901018018531962 891 2885481889622420517427728 892 2992045183805097775061167 893 3102483755791603046354979 894 3216936382584039484395640 895 3335546735173671758140269 896 3458463548494158112381072 897 3585840797186002050996207 898 3717837877370346735705320 899 3854619794632466680429461 900 3996357358426393939077288 901 4143227383114619836287151 902 4295412895868486408159627 903 4453103351657680476621866 904 4616494855569541350392044 905 4785790392702011860422364 906 4961200065887022063538673 907 5142941341504560704758988 908 5331239303661349902586782 909 5526326917011879930260347 910 5728445298513963462289905 911 5937843998415216421621110 912 6154781290782060401416254 913 6379524473887528352867264 914 6612350180790174385315980 915 6853544700441548717941508 916 7103404309676598306451473 917 7362235616447025262571769 918 7630355914675467655998304 919 7908093551114592345779050 920 8195788304614013014450015 921 8493791778204771797867929 922 8802467804431001224206348 923 9122192864365860784152340 924 9453356520769844235732232 925 9796361865857740261560186 926 10151625984162727364154773 927 10519580430995038021643219 928 10900671727016097078011409 929 11295361869458821012880779 930 11704128860549581791743048 931 12127467253698007808640412 932 12565888718047034464448803 933 13019922621987231722793483 934 13490116636267175528790586 935 13977037357344250807735302 936 14481270951649591112457592 937 15003423821454549534942394 938 15544123293057073609946117 939 16104018328021182076356833 940 16683780258235469382784316 941 17284103545572598272242504 942 17905706566966315079100250 943 18549332425739847470476847 944 19215749790056070364635352 945 19905753759378530547411181 946 20620166759871012599974751 947 21359839469683511027743497 948 22125651775113254426222235 949 22918513758651193185332789 950 23739366719967463906575970 951 24589184230912805915849063 952 25468973225658467897993166 953 26379775127122422614218982 954 27322667010877879198517244 955 28298762807767308908684547 956 29309214546496137472464639 957 30355213637509566080483560 958 31437992199509852129282707 959 32558824430002918003575671 960 33719028021320133397338894 961 34919965623595039201565856 962 36163046356235056811754244 963 37449727369464705230852753 964 38781515457580629705354516 965 40159968725597968110947135 966 41586698311035092878020824 967 43063370162625938335396062 968 44591706877820608514094223 969 46173489600980303288843818 970 47810559984248318329690850 971 49504822213127622143515392 972 51258245098875732953382013 973 53072864239880013359944503 974 54950784254261499470056051 975 56894181086011670488186437 976 58905304387056625498318631 977 60986479977703569200140119 978 63140112388019919105004107 979 65368687482760185387951623 980 67674775172556833299895549 981 70061032214160848089366742 982 72530205102624741243465740 983 75085133058395202386823457 984 77728751112395911166103758 985 80464093292260749473467585 986 83294295912997611438216515 987 86222600975448324362749509 988 89252359676037181707328221 989 92387036031391852397999901 990 95630210621554862392562520 991 98985584455601441995792519 992 102456982963621852324112011 993 106048360119130652139577323 994 109763802696116050115117558 995 113607534665054032063132010 996 117583921732371506337322542 997 121697476027961927798139564 998 125952860945525822073211957 999 130354896140636026775725707 1000 134908562691606404928183067