0 0 1 0 2 1 3 2 4 4 5 5 6 8 7 12 8 18 9 25 10 35 11 47 12 66 13 87 14 118 15 155 16 207 17 264 18 348 19 443 20 571 21 725 22 923 23 1155 24 1466 25 1821 26 2275 27 2821 28 3501 29 4293 30 5307 31 6477 32 7933 33 9658 34 11750 35 14198 36 17251 37 20746 38 24986 39 30009 40 36024 41 42983 42 51446 43 61176 44 72839 45 86497 46 102538 47 121133 48 143471 49 168971 50 199055 51 234123 52 275128 53 322240 54 377889 55 441547 56 516039 57 602092 58 701519 59 815655 60 949727 61 1101791 62 1277784 63 1480635 64 1714248 65 1980709 66 2289417 67 2639824 68 3043880 69 3505822 70 4033640 71 4633963 72 5327052 73 6109259 74 7003264 75 8024085 76 9186033 77 10500521 78 12004608 79 13701263 80 15636888 81 17829086 82 20309221 83 23111510 84 26308419 85 29899510 86 33962080 87 38558213 88 43749426 89 49584507 90 56199898 91 63615205 92 71992890 93 81419687 94 92008573 95 103904682 96 117341893 97 132349643 98 149212861 99 168156360 100 189418942 101 213171959 102 239870385 103 269663879 104 303083949 105 340482684 106 382220386 107 428818445 108 481094397 109 539218370 110 604160182 111 676644317 112 757484989 113 847401245 114 947819113 115 1059426769 116 1183815249 117 1322195874 118 1475944086 119 1646767932 120 1837319630 121 2048232421 122 2282528189 123 2542828474 124 2831700677 125 3151770402 126 3507160291 127 3900322384 128 4336505559 129 4819538911 130 5354112321 131 5945259272 132 6600952494 133 7324388964 134 8124412579 135 9009629574 136 9987451754 137 11066192292 138 12258934513 139 13573633421 140 15026412880 141 16628195465 142 18393335081 143 20338607070 144 22486687513 145 24849547974 146 27451558874 147 30318274386 148 33474022082 149 36943433456 150 40765443353 151 44962968544 152 49581757593 153 54658014631 154 60233037189 155 66357782179 156 73092859068 157 80476217477 158 88581355117 159 97479690093 160 107245450543 161 117945659085 162 129687684671 163 142548344109 164 156651679611 165 172106790666 166 189023696837 167 207546110799 168 227850925159 169 250047585248 170 274344997121 171 300930693692 172 330011240374 173 361791848208 174 396558317517 175 434542076298 176 476059770283 177 521413264895 178 570931072021 179 624996932298 180 684096318074 181 748525055602 182 818837898262 183 895572556721 184 979279189829 185 1070539836262 186 1170074064295 187 1278515543023 188 1396750155024 189 1525574291238 190 1665896160029 191 1818687296037 192 1985207001268 193 2166351980645 194 2363534517807 195 2578220583914 196 2811792126230 197 3065778232631 198 3342139123008 199 3642530801530 200 3969295387942 201 4324408391907 202 4710247416079 203 5129476734242 204 5585226549613 205 6080007941720 206 6617261748674 207 7200728478889 208 7834172380054 209 8521480438508 210 9267729660775 211 10076993890317 212 10955144658711 213 11907546386657 214 12940139679309 215 14059823135681 216 15274140916623 217 16589581587906 218 18015091798510 219 19559892933605 220 21233717512348 221 23045961218569 222 25009076083135 223 27134064348927 224 29435162177235 225 31926058160321 226 34621004648104 227 37536992150757 228 40693260287592 229 44105877600734 230 47797280877334 231 51789260346953 232 56105585611198 233 60770638024972 234 65814133398168 235 71264018316006 236 77153403192740 237 83515865813061 238 90387811458568 239 97809546868003 240 105828316255457 241 114482172952143 242 123824708497612 243 133910417934365 244 144795988667239 245 156541816860429 246 169215975145446 247 182886077269864 248 197633780384675 249 213538260860579 250 230688293121876 251 249177055786873 252 269115521321750 253 290599648053230 254 313754017263633 255 338709840674810 256 365597218533918 257 394558264272917 258 425758795122836 259 459357010366174 260 495545922125885 261 534506756512763 262 576447164928488 263 621592803560112 264 670197093619922 265 722493143218265 266 778761500452436 267 839304455616874 268 904436083886651 269 974483209006095 270 1049833734550404 271 1130844377273759 272 1217959098461797 273 1311611799839095 274 1412273939119505 275 1520473647480430 276 1636773861407425 277 1761715378491223 278 1895955718512904 279 2040179805091368 280 2195118836674636 281 2361496932721617 282 2540192662882067 283 2732051200369726 284 2938063943626527 285 3159233736640177 286 3396608055383249 287 3651378379967845 288 3924843000205419 289 4218222170745611 290 4533014878173158 291 4870724029580257 292 5232988176823882 293 5621498878088098 294 6038196801401128 295 6485008993683172 296 6964099433342208 297 7477708494941361 298 8028247010617889 299 8618336040918799 300 9250902155751274 301 9928625176286763 302 10654801856302893 303 11432859468660695 304 12266399090748646 305 13159226411466176 306 14115519486685111 307 15139563222089099 308 16236232356475134 309 17410412419849121 310 18667497654614835 311 20013125366198220 312 21453687072665385 313 22995255534650825 314 24644993025346249 315 26410490602692442 316 28299434692076307 317 30320165576386278 318 32481973503307105 319 34794149472803902 320 37267377852072118 321 39912120607174248 322 42740094805994977 323 45763765564612320 324 48996829672275580 325 52452713759462175 326 56146572459456110 327 60094725839864432 328 64314230259194932 329 68822932230054652 330 73640942053749840 331 78787977585792700 332 84286878941830163 333 90160681864447669 334 96434265318611163 335 103134705052290087 336 110290738365507855 337 117931088779117092 338 126088759103985741 339 134798261418898796 340 144096346503859310 341 154020402965664917 342 164613148212286313 343 175917502050046109 344 187981337193738572 345 200854125256557623 346 214587797554697940 347 229239537773373381 348 244870951983418803 349 261542856009196474 350 279325400087429036 351 298289942260508846 352 318513955840979323 353 340077723691809418 354 363070225275938148 355 387582617851687757 356 413713866123427253 357 441567818734202072 358 471254947293866023 359 502894170421313523 360 536615194370411754 361 572543568462630444 362 610825026266309921 363 651611278334757964 364 695062656867932696 365 741347680659654343 366 790648530847857207 367 843154783422765870 368 899074879290575256 369 958622510257341153 370 1022029379632520831 371 1089538196104717130 372 1161415389970206671 373 1237926651755627117 374 1319370247162557655 375 1406061454685953400 376 1498326062841456314 377 1596511809611868379 378 1700998747632087305 379 1812173792986450781 380 1930467890629236365 381 2056314646505988019 382 2190188682868501191 383 2332593651150139137 384 2484072222203006104 385 2645173797453124509 386 2816498027333445533 387 2998688272138498124 388 3192418543975853424 389 3398394981787508181 390 3617394318140678562 391 3850197900350529829 392 4097679793874363955 393 4360731510464701428 394 4640312803749960071 395 4937451926428338333 396 5253233647758299222 397 5588772028809170538 398 5945297493027671552 399 6324102904912689845 400 6726557042660684455 401 7154070704532916213 402 7608206763613523554 403 8090563481045778686 404 8602885865452236953 405 9146987561887974564 406 9724776741740522599 407 10338311494201101564 408 10989795599198230839 409 11681457276151119801 410 12415775292081709722 411 13195306769780140750 412 14022793707842045602 413 14901097511264692182 414 15833313448605850569 415 16822659602005494037 416 17872578859826996640 417 18986683150426586984 418 20168816632920757087 419 21423063502432952874 420 22753825038730632213 421 24165489909468054119 422 25662973430857962776 423 27251406448060044738 424 28936202616316335028 425 30723059574847031896 426 32618055114818609998 427 34627560881499497065 428 36758432172953703872 429 39017790497662293839 430 41413266874535253770 431 43952841597558404348 432 46645166811968291195 433 49499016330019371238 434 52524019045809067349 435 55730297399607536096 436 59128407189261963406 437 62729547439832499251 438 66545752925442014323 439 70589469107168255871 440 74874220920687053038 441 79413839422449994632 442 84223226253169786310 443 89318158862695478574 444 94715454207672912350 445 100432392080090341078 446 106487567163259573776 447 112900743105405371548 448 119692706471399002662 449 126885147980928720972 450 134501614740970627044 451 142566138659102225696 452 151104960446390055451 453 160145209919809664617 454 169715763614410073388 455 179847368663517533582 456 190572295983147841583 457 201924074151145332783 458 213939008832957794847 459 226655193952779040567 460 240112949984535699128 461 254354007000153083794 462 269423753212433053914 463 285368948367512533060 464 302240028699809483828 465 320089517524748897610 466 338972648248605936103 467 358948496830075742861 468 380079700881125848943 469 402430634656567847262 470 426071161252530052582 471 451073927013747966923 472 477516289066507738151 473 505478927640343599235 474 535048399249654083058 475 566314861296946140796 476 599374082187893417687 477 634326422750672623118 478 671278344437872922969 479 710342320496580384242 480 751638336012454856888 481 795288401614361930597 482 841425804600710132676 483 890190024128496415181 484 941727642579160694738 485 996193102048712017955 486 1053749834610439462481 487 1114569222458857632580 488 1178834318789942545505 489 1246735372063638352689 490 1318475272389540906419 491 1394265583263618641473 492 1474333496364048798261 493 1558912271903423258727 494 1648253244796306480623 495 1742620988642102176427 496 1842291428927948178617 497 1947556284671458597658 498 2058725715120915760804 499 2176122726140500897544 500 2300093466067759975068 501 2430994795066562609852 502 2569208392918983069445 503 2715135877970352930274 504 2869203488305755428283 505 3031851088954915524637 506 3203548607605437237706 507 3384792693191624698157 508 3576104741992904271384 509 3778030725007823572811 510 3991154598916039120821 511 4216078768934165925286 512 4453450261240378685803 513 4703941918098108814238 514 4968266127039490927102 515 5247176305265698392110 516 5541463479267192718978 517 5851951607168131906686 518 6179522697095795003137 519 6525099741106181102792 520 6889658970523964280440 521 7274212565824993052452 522 7679847589329593078886 523 8107691958484244065550 524 8558947424425162740818 525 9034870175837996271670 526 9536775921470376137778 527 10066064275639361996030 528 10624211925377188399782 529 11212745056342773964541 530 11833302768755434234936 531 12487589705949645925871 532 13177413204176948855221 533 13904657585544375656079 534 14671329612692645316116 535 15479522913642057739553 536 16331448034180135084955 537 17229423434926644361134 538 18175895919781811263003 539 19173443009457346468314 540 20224791388206100022297 541 21332747110177201168233 542 22500328066443397012892 543 23730690175505442037895 544 25027152450079748836548 545 26393195326509482980162 546 27832492302608309018328 547 29348887609978092747510 548 30946462560582915675574 549 32629468987770212024286 550 34402407959838944596027 551 36269983686730196380063 552 38237198139048742930996 553 40309222634741260965861 554 42491565794913163034295 555 44790021933757513442489 556 47210636974963151723661 557 49759778695955336952076 558 52444186281336468899478 559 55270879060419208637172 560 58247327488458646421570 561 61381250060368704801941 562 64680862033737430990139 563 68154780054850889161397 564 71812096528518298913859 565 75662259370018726526910 566 79715264019436684008149 567 83981651683577285857732 568 88472458301282726909440 569 93199243979844418588689 570 98174279747870953771834 571 103410270696466717291670 572 108920757938738945176420 573 114719833550269317310809 574 120822367704390322932130 575 127243997893723843218605 576 134001142739976390679874 577 141110911009890093994413 578 148591471087218186411299 579 156461847523142758992249 580 164742060404703208889278 581 173452941868856476408406 582 182616623027116653696059 583 192256161749879844625599 584 202395953935625082296278 585 213061476864565830192982 586 224279438555627755595444 587 236078045562577732785324 588 248486979866739502511656 589 261537004636344390004274 590 275260886916484909862778 591 289692733310636258026375 592 304868542720517983099559 593 320825884987283859279886 594 337604492684348052375556 595 355245864993326453764700 596 373793588866396674539426 597 393293407601228451479775 598 413793398295042384796205 599 435344037548508037615816 600 457998577190766708497171 601 481811997023730020405870 602 506842936209482212880593 603 533152594657787535468371 604 560805264700247205334865 605 589868280302202950276741 606 620412382762494504883304 607 652511670703311577143598 608 686244299014442646475524 609 721691771717634325891371 610 758939944855000536696885 611 798078571041303130149635 612 839202495626600790426454 613 882410082457119059847074 614 927805509513115651345483 615 975497980268013398768695 616 1025601571265311724973602 617 1078235879022921625643225 618 1133527109472159287848975 619 1191606765769741384938907 620 1252613833063278582183625 621 1316692595590471509874387 622 1383995463353284909482314 623 1454682164331330768565249 624 1528920465560664377492859 625 1606885097092904182121754 626 1688760066531792804020029 627 1774738691637057379307579 628 1865023395811415606436813 629 1959825774544674689287522 630 2059369316389777361931755 631 2163885688334335767449838 632 2273620507124607882557648 633 2388829370088843179333073 634 2509781069695182107324260 635 2636757784888238532290298 636 2770054797351973386145554 637 2909980389683205522985856 638 3056859507902061433384266 639 3211032434774822455963936 640 3372856229591408797250526 641 3542702387172493455055105 642 3720963885408303476767954 643 3908049864222947395697505 644 4104391477902711801766493 645 4310438493537803998775251 646 4526662035785032413210537 647 4753557525988395285795703 648 4991644752434931790522894 649 5241463807009582144820821 650 5503585875425245887515843 651 5778606055032285082721005 652 6067149509852888730124744 653 6369869344498896432430522 654 6687452695766334765897045 655 7020616885699064390229793 656 7370114212793629089165404 657 7736731736174699022957680 658 8121295413625394243712433 659 8524669522350074107585392 660 8947763307631288637854000 661 9391518408102295049880455 662 9856931399169441555052024 663 10345042983267329724256691 664 10856943286960822074714146 665 11393772469318231130185396 666 11956724648218608400903588 667 12547049841948589074536602 668 13166061159521697489845299 669 13815127795488593497911789 670 14495688362468899465910902 671 15209243882358143554871119 672 15957375094244728891266647 673 16741721961663814895792292 674 17564014680961835580007052 675 18426063083820476128074761 676 19329755367351038741921259 677 20277070182988840477992596 678 21270084830205411806445955 679 22310965496496860129644061 680 23401989771678799403731925 681 24545525801959392423546548 682 25744065536284828012507551 683 27000214187562457711647356 684 28316703623604208789067277 685 29696378067503509296899565 686 31142223573139442064079255 687 32657366821287919667966365 688 34245080273950747832762539 689 35908778768032660953454754 690 37652054037341986861206084 691 39478637784987828116660408 692 41392461522090079153786869 693 43397621661588039248585379 694 45498408281256260152645505 695 47699318921084209519922190 696 50005052056633100555084135 697 52420507385672401157254062 698 54950836068286718738422316 699 57601418592470931394849002 700 60377891712071675563066692 701 63286117221198867541880044 702 66332270816526236008239770 703 69522780992355223063229981 704 72864397391107820849097226 705 76364160611456472475205636 706 80029429317835336788468220 707 83867922077068360309312667 708 87887710658250479784841804 709 92097198243672512976301102 710 96505224411023129563192075 711 101120995112615557845940835 712 105954164574607454369131051 713 111014798144349751744816402 714 116313460443581200911061290 715 121861162019259197340307307 716 127669431329490218379417141 717 133750313236821339138143391 718 140116412489487186885013987 719 146780906873271821678370866 720 153757609337995545917838868 721 161060848222112028891837950 722 168705707292365434862480393 723 176707932266928956793381686 724 185083981470572363313915394 725 193851044231756740803235161 726 203027095910883510560736206 727 212630913645132305532126921 728 222682177030264891655390086 729 233201374926255952176522753 730 244209995468526828447216319 731 255730433677796025263577700 732 267786184630798214794597823 733 280401670487660209753616041 734 293602527751239257748971556 735 307415545964428240064920239 736 321868638255559245448475726 737 336991005139418563682237390 738 352813224366589489342212432 739 369367149456795731800720077 740 386686191462616061633766867 741 404805081401684157969307663 742 423760255940920140614491203 743 443589726725387764939096876 744 464333291191579825168870843 745 486032361448117177751334001 746 508730292114683693508257831 747 532472424007641431090487960 748 557306092077794827433350684 749 583280683191999718846208419 750 610447925483705074930030119 751 638861619963373203128808936 752 668578233352049594359249892 753 699656541387829274196084566 754 732158039071884727616460911 755 766146995157550176734701839 756 801690487591972444581440568 757 838858385652475453400920742 758 877723946421197710171602807 759 918363580356655865026249995 760 960857164088515267111215504 761 1005287788382856789890834643 762 1051742635986896623069264773 763 1100312471798383316294862863 764 1151092251062044988462984587 765 1204181030117071274884462395 766 1259682132288291491248475302 767 1317703658158954308265970212 768 1378358541903008475241709509 769 1441764224266449699714137076 770 1508043908315995648641786979 771 1577325740571375956066689959 772 1649743872694995540970449587 773 1725438048278368888191821601 774 1804554486058057156799565252 775 1887245560828835461831803826 776 1973670420429405947802062827 777 2063995135646693435040928497 778 2158393105753458041195964590 779 2257045404320434506790068493 780 2360141331559852544081717855 781 2467877394331481915484883166 782 2580459769705942033865622651 783 2698103331216356027543135387 784 2821032416274343658755249520 785 2949480832063884566634957539 786 3083692828461670466876529332 787 3223923140371830266985058926 788 3370438033316728411208347379 789 3523514800617612364515046835 790 3683443334105555650072582282 791 3850525604931480140000688613 792 4025077446522028905145120321 793 4207427225849722358116501299 794 4397918689206099893750035048 795 4596910383592556435739647093 796 4804775787987895518469091830 797 5021904767082309729972184029 798 5248704728899279562818768894 799 5485599607871018062272756394 800 5733033133998439828442789558 801 5991466349686383403028828192 802 6261381638102316500412468392 803 6543281901534708031321137454 804 6837692228090545997426547591 805 7145159115938956195647106078 806 7466253011229741410292404098 807 7801569744580042826670640624 808 8151730510811449521461185046 809 8517382362099612311182396694 810 8899201977080756421420963253 811 9297892475033410746275388533 812 9714189967005533696354983857 813 10148859980368494511392709031 814 10602702126722307529935209635 815 11076550560503172941266029272 816 11571274617834692560671305925 817 12087779494790915379175982963 818 12627011451011708107686573670 819 13189956629527119389840104516 820 13777643452488441336159216165 821 14391142033662940167112857024 822 15031571626948666491397579895 823 15700096588654436130340071455 824 16397933217669810170446453948 825 17126347973562773494331515652 826 17886661013223318698017848992 827 18680249857326213194900216939 828 19508551888606242260571438381 829 20373061295716748813171206947 830 21275340726308283510032633894 831 22217015558651696722033245367 832 23199783016737943428410689293 833 24225409708006013740814413905 834 25295739597214433976654775264 835 26412693322014872941104012779 836 27578273037180394455491443353 837 28794565377280661050748519870 838 30063746162803568155968007444 839 31388083175871526610495009535 840 32769943588338500260322890140 841 34211783210546341256350059970 842 35716172905296706471845160862 843 37285788522554520460280509056 844 38923419133574715676697446294 845 40631970060533930678405601212 846 42414469418578869454677380543 847 44274072332319830871292807966 848 46214069397297687607826893325 849 48237885379830997473511258812 850 50349093933623990425194123935 851 52551413134600397612913748483 852 54848725143301883020312777130 853 57245063849357500425926942912 854 59744642428417288518495026921 855 62351848119114344755051958275 856 65071248386245812888476709716 857 67907602596363308261788480122 858 70865875017537762399304034637 859 73951229532343490936396554409 860 77169056348966193323737222431 861 80524956591753349756650452406 862 84024774865145106091627994707 863 87674599154876786743741155332 864 91480775406684102200402352769 865 95449900921826385354900104160 866 99588855217848006993160978920 867 103904808237125907635516634652 868 108405227413834667289535716890 869 113097881120435491672216554312 870 117990878066705243078875280980 871 123092640463391238428039138729 872 128411963538406886594666424967 873 133957990883985483540155655060 874 139740253594375558774383947993 875 145768682604236707108721437593 876 152053610168692416653730982955 877 158605790869118308458894048535 878 165436441019239564158829066274 879 172557234476436740064505599618 880 179980334973053205428919990479 881 187718381731452720795771659093 882 195784571606016447938143252034 883 204192616218838598153563256463 884 212956817729515821721500363566 885 222092053916777923660835495047 886 231613808999983278918073625912 887 241538221287593443173573918896 888 251882098635351929336948138753 889 262662906191254675178900595574 890 273898864103561018493203909268 891 285608916340879060098010108883 892 297812805362005805141544976418 893 310531063202410068195448954825 894 323785088802584159700748546899 895 337597139716776903105003669534 896 351990393156575555454621087499 897 366988961207945018939167503452 898 382617964425412007769044566811 899 398903544919373833966681042831 900 415872940396416705244431569908 901 433554418397850323888214677618 902 451977485114311042544976752558 903 471172829615613482088746866300 904 491172387515516474463930648014 905 512009392871389848129884283787 906 533718437537996946724685309234 907 556335515656821553511149720276 908 579898118693860532975698339549 909 604445223649736903149436399920 910 630017436525345297243545675973 911 656656954664744705358734505971 912 684407774065648830614880898991 913 713315574129022679280795959946 914 743427973134612323861215023677 915 774794514077061398567616461526 916 807466703686501301878508557921 917 841498159550719475635466994453 918 876944693753057853417675132120 919 913864331136069605624536699119 920 952317531155387071260201023029 921 992367064475211380654041835514 922 1034078349785382059537986523351 923 1077519420289988872108330827119 924 1122761101144311357489542859704 925 1169876958641877176343323178464 926 1218943597143703100367032010376 927 1270040741519150024565071867171 928 1323251314521908776308808756071 929 1378661519598647984110806472591 930 1436361157248458309850796097916 931 1496443464656383329413492383657 932 1559005585559623092936328705796 933 1624148476671550155025496819972 934 1691977200362888495824164113275 935 1762601064439525173135250428016 936 1836133722555751423475034196257 937 1912693292601633134056733608147 938 1992402807272094155336736720005 939 2075390131174003974877679752298 940 2161788346288520464983586307058 941 2251735646437467105224812164076 942 2345376010154918281540992148224 943 2442858988979137586105096534344 944 2544340270444953941784545168469 945 2649981668332089000374355818811 946 2759951365264558170390292273498 947 2874424440398358184181643482244 948 2993582972928643042367486382025 949 3117616035617570200707191314929 950 3246720563462486160998874154490 951 3381101082434132826418621572930 952 3520970489823465985885680934923 953 3666549885565199741814122026428 954 3818069456394969260691391524166 955 3975768349421439878956243823596 956 4139895247186691576535269846359 957 4310708697392301299709156560013 958 4488477577033997498281646173882 959 4673481440074978023453985621822 960 4866011061630231891186151696301 961 5066368140644152230926716277773 962 5274866987442385387267765977578 963 5491834150606424474411348790452 964 5717609120848963869860825787172 965 5952544752194911685125217984727 966 6197007885619242885873570617690 967 6451379714399018185183059744902 968 6716056856684759793387409129693 969 6991451184405041288587236356811 970 7277991191965439327599189281806 971 7576121877687401256200863289044 972 7886306323693431805904661108493 973 8209025167048512734363366121803 974 8544778462171284339575275962593 975 8894086034413020981279823518595 976 9257487782075537938779368318825 977 9635544910214775113604428757770 978 10028841051103313842054844545029 979 10437982255510392673761487320749 980 10863599101786133608513869743161 981 11306345789835922194263843805751 982 11766903120487661199161129658251 983 12245978349214370538549906752506 984 12744306747164111729345642579803 985 13262651595666050200333075282563 986 13801806478229661950163031807434 987 14362596382760065043321958618965 988 14945878234247203910646317930570 989 15552542282212908517494563466855 990 16183514391306291834836802512112 991 16839755125568016359077554560672 992 17522264079916578795180911876653 993 18232078788597994065288358992454 994 18970277911327586674491990881294 995 19737982033949084693429129967828 996 20536355304090919613131138214592 997 21366606572972071549239101323352 998 22229992829894533337810581632556 999 23127819591984113543778539694234 1000 24061443581706886096257604971526