0 1 1 0 2 0 3 0 4 0 5 1 6 1 7 2 8 3 9 5 10 8 11 11 12 15 13 21 14 28 15 38 16 49 17 64 18 82 19 105 20 134 21 168 22 211 23 263 24 327 25 406 26 501 27 616 28 757 29 926 30 1133 31 1378 32 1676 33 2031 34 2460 35 2970 36 3581 37 4306 38 5173 39 6197 40 7419 41 8855 42 10561 43 12565 44 14934 45 17712 46 20982 47 24805 48 29294 49 34529 50 40658 51 47785 52 56104 53 65760 54 76998 55 90017 56 105124 57 122589 58 142810 59 166137 60 193086 61 224110 62 259870 63 300969 64 348240 65 402474 66 464726 67 536024 68 617713 69 711118 70 817947 71 939896 72 1079134 73 1237841 74 1418748 75 1624651 76 1858981 77 2125303 78 2427950 79 2771434 80 3161207 81 3602976 82 4103580 83 4670234 84 5311497 85 6036456 86 6855799 87 7780952 88 8825254 89 10003012 90 11330860 91 12826661 92 14511109 93 16406507 94 18538523 95 20934932 96 23627544 97 26650856 98 30044246 99 33850482 100 38118210 101 42900339 102 48256896 103 54253232 104 60963263 105 68467592 106 76857080 107 86230952 108 96700804 109 108388528 110 121430968 111 135977662 112 152196134 113 170269576 114 190402797 115 212819834 116 237770718 117 265529071 118 296399720 119 330716318 120 368850047 121 411207140 122 458238963 123 510439549 124 568356974 125 632591211 126 703806998 127 782731947 128 870171320 129 967006420 130 1074211488 131 1192852624 132 1324107166 133 1469263164 134 1629741660 135 1807097073 136 2003042544 137 2219451701 138 2458387648 139 2722106047 140 3013088660 141 3334048110 142 3687966420 143 4078102181 144 4508034733 145 4981674161 146 5503312218 147 6077635853 148 6709785665 149 7405373855 150 8170551619 151 9012032062 152 9937168240 153 10953982251 154 12071255015 155 13298563343 156 14646383306 157 16126136475 158 17750309487 159 19532511136 160 21487610412 161 23631806923 162 25982790428 163 28559826747 164 31383942356 165 34478029054 166 37867056991 167 41578202073 168 45641092096 169 50087960264 170 54953930399 171 60277201387 172 66099376998 173 72465687525 174 79425371096 175 87031938731 176 95343615743 177 104423658057 178 114340862561 179 125169944015 180 136992125558 181 149895585890 182 163976143227 183 179337785148 184 196093459426 185 214365701738 186 234287550165 187 256003286450 188 279669494369 189 305455933499 190 333546763209 191 364141571846 192 397456792243 193 433726911236 194 473206106925 195 516169668794 196 562915889751 197 613767732354 198 669075015336 199 729216364351 200 794601739675 201 865674717636 202 942915410591 203 1026843133503 204 1118019775999 205 1217052914669 206 1324599707329 207 1441370522159 208 1568133432299 209 1705718444357 210 1855022685206 211 2017015322318 212 2192743548893 213 2383338304748 214 2590021178024 215 2814111053111 216 3057032067000 217 3320321325902 218 3605638076290 219 3914772654633 220 4249657053227 221 4612375293626 222 5005175595692 223 5430482389985 224 5890910329497 225 6389278190875 226 6928624999463 227 7512226106813 228 8143611741883 229 8826585589237 230 9565246126354 231 10364008077492 232 11227626943421 233 12161223762428 234 13170313299544 235 14260832603685 236 15439173392309 237 16712214966839 238 18087361400130 239 19572579453941 240 21176441266614 241 22908168002999 242 24777678839881 243 26795641186947 244 28973526872728 245 31323669896573 246 33859330849554 247 36594763285510 248 39545287558897 249 42727367059608 250 46158692808162 251 49858270976373 252 53846519770678 253 58145369852310 254 62778375253610 255 67770828541375 256 73149887744595 257 78944708362257 258 85186588559810 259 91909120403315 260 99148355895214 261 106942980151286 262 115334501188389 263 124367448137134 264 134089588096844 265 144552152890585 266 155810086757905 267 167922305642600 268 180951979995283 269 194966831128822 270 210039453988406 271 226247655713194 272 243674823889044 273 262410313157029 274 282549865192226 275 304196049990089 276 327458744660171 277 352455636896961 278 379312770629677 279 408165120195197 280 439157211942859 281 472443778767795 282 508190467986528 283 546574587158535 284 587785909917380 285 632027525466596 286 679516755579325 287 730486121794057 288 785184388546297 289 843877663918274 290 906850585836319 291 974407574321997 292 1046874179885744 293 1124598507582372 294 1207952749238570 295 1297334802246711 296 1393170010085968 297 1495913001783719 298 1606049668344672 299 1724099252177213 300 1850616590631785 301 1986194488458682 302 2131466263687795 303 2287108440464583 304 2453843637010735 305 2632443620995935 306 2823732584434228 307 3028590609129214 308 3247957379107639 309 3482836109769159 310 3734297754889493 311 4003485459953741 312 4291619328033267 313 4600001465445512 314 4930021378974352 315 5283161690659857 316 5661004247973276 317 6065236594259759 318 6497658883799530 319 6960191205304097 320 7454881405375158 321 7983913374727359 322 8549615896513909 323 9154472018716092 324 9801129058404263 325 10492409199140778 326 11231320798621706 327 12021070367283523 328 12865075345094139 329 13766977636996253 330 14730658045231218 331 15760251559008006 332 16860163651840706 333 18035087547291461 334 19290022616638699 335 20630293869942293 336 22061572718388619 337 23589898970566976 338 25221704256345727 339 26963836842649103 340 28823588052066001 341 30808720250930461 342 32927496636643423 343 35188712793915271 344 37601730270411697 345 40176512145295988 346 42923660863814504 347 45854458316279983 348 48980908459370225 349 52315782464035167 350 55872666715199420 351 59666013654667777 352 63711195822316242 353 68024563095629306 354 72623503515387460 355 77526507707850759 356 82753237327265787 357 88324597541120977 358 94262814021512896 359 100591514479361538 360 107335815248191881 361 114522412970915783 362 122179681944108165 363 130337777192550226 364 139028743881022221 365 148286633158693571 366 158147625100702201 367 168650158868328233 368 179835070815868969 369 191745740695522687 370 204428246758257957 371 217931529936469503 372 232307567983193931 373 247611559793176755 374 263902120865268886 375 281241490176484494 376 299695749520432558 377 319335055632023335 378 340233886253734651 379 362471300524016490 380 386131214956327294 381 411302695455936318 382 438080266767710794 383 466564239877757053 384 496861058899463439 385 529083668052615865 386 563351900417725352 387 599792889171197348 388 638541503150593695 389 679740807565421852 390 723542551886857879 391 770107685855736849 392 819606905845584748 393 872221232659575636 394 928142623222483736 395 987574617403981601 396 1050733022681634271 397 1117846638057109004 398 1189158020207077595 399 1264924293481330648 400 1345418007030967340 401 1430928040902994046 402 1521760564716646818 403 1618240051008930317 404 1720710347231934618 405 1829535808770922317 406 1945102497371072873 407 2067819447657683613 408 2198120006584961523 409 2336463248851817969 410 2483335473613928956 411 2639251785925977815 412 2804757768788854319 413 2980431249678442924 414 3166884168032838929 415 3364764548069439470 416 3574758584073889284 417 3797592843084852931 418 4034036592850977993 419 4284904260601305721 420 4551058031316168901 421 4833410591728576864 422 5132928029638733721 423 5450632895539581578 424 5787607437124891716 425 6144997014534304263 426 6524013707998463066 427 6925940126692948623 428 7352133431670019474 429 7804029582739385400 430 8283147823498478551 431 8791095415566782342 432 9329572637694512335 433 9900378062116922637 434 10505414125447937146 435 11146693007948662013 436 11826342840256760335 437 12546614253040934584 438 13309887290644886303 439 14118678705995105857 440 14975649660021613251 441 15883613844876687144 442 16845546056612445393 443 17864591238836088881 444 18944074025665495141 445 20087508807983951545 446 21298610354255479295 447 22581305012651565886 448 23939742528994253258 449 25378308510320474933 450 26901637572151840699 451 28514627202662036176 452 30222452385776738370 453 32030581020153527793 454 33944790180436088638 455 35971183261893602113 456 38116208059649183056 457 40386675828221765113 458 42789781377892471597 459 45333124258730168955 460 48024731094642015400 461 50873079123944143879 462 53887121015276100990 463 57076311021621182742 464 60450632548380088592 465 64020627205196289725 466 67797425425337064197 467 71792778730005151537 468 76019093730048290781 469 80489467950933990577 470 85217727583010520981 471 90218467252313488957 472 95507091924472224241 473 101099861047361548028 474 107013935056664495195 475 113267424361473063389 476 119879440946892874205 477 126870152723467472395 478 134260840774496215939 479 142073959645082884278 480 150333200839536067107 481 159063559686447475589 482 168291405755202323730 483 178044557000353664185 484 188352357836491843228 485 199245761338930263383 486 210757415793633936385 487 222921755812564530068 488 235775098260776650983 489 249355743234453091428 490 263704080361444908248 491 278862700688900720449 492 294876514457336465195 493 311792875053748256119 494 329661709473716618208 495 348535655616008064509 496 368470206773309358302 497 389523863676681695876 498 411758294494453915858 499 435238503180718294093 500 460033006614968841984 501 486214020969466349306 502 513857657790796658738 503 543044130277858956086 504 573857970292188588583 505 606388256633155994120 506 640728855168345054479 507 676978671407072000206 508 715241916167195505023 509 755628384984225300380 510 798253751978712058033 511 843239878898154898088 512 890715140121818860794 513 940814764418722108295 514 993681194326816372423 515 1049464464025113889528 516 1108322596654344773760 517 1170422022047596465664 518 1235938015922789949144 519 1305055161597154935847 520 1377967835381389507250 521 1454880716822279688247 522 1536009325067788094137 523 1621580582642872683824 524 1711833408037889193168 525 1807019338529260535931 526 1907403184774751225079 527 2013263718747561478530 528 2124894396705931679967 529 2242604118921389608402 530 2366718028031903520816 531 2497578347917778864530 532 2635545265152826457429 533 2780997855120674707526 534 2934335055053325377882 535 3095976686292870234211 536 3266364528258121745052 537 3445963446648972339149 538 3635262578616906000825 539 3834776577689251126668 540 4045046921446406429789 541 4266643285019488415661 542 4500164983704906340560 543 4746242488070677385446 544 5005539015177267339390 545 5278752199625294832692 546 5566615848410950133949 547 5869901783672050129631 548 6189421777698484339580 549 6526029584696788281610 550 6880623074113669279699 551 7254146470454747485240 552 7647592704876217245573 553 8062005883975726711352 554 8498483881578865230092 555 8958181059485256247340 556 9442311123539491137272 557 9952150121580821677624 558 10489039590260621487521 559 11054389857928643753297 560 11649683511261012782013 561 12276479033540712864648 562 12936414623013288890997 563 13631212200006840244323 564 14362681612060880021655 565 15132725046606537737495 566 15943341661343437884992 567 16796632442791311934842 568 17694805304148780585557 569 18640180433962902315024 570 19635195907823508417659 571 20682413575709900706633 572 21784525238388894960840 573 22944359126723480142532 574 24164886698589126621769 575 25449229768606563889940 576 26800667986809806273956 577 28222646682936717122128 578 29718785094017930337665 579 31292884993570896181081 580 32948939741779856243017 581 34691143776742212074132 582 36523902568028841570709 583 38451843054581157835138 584 40479824590236078315190 585 42612950421028400899559 586 44856579719798699596367 587 47216340204584508054640 588 49698141368771158181209 589 52308188352028635483587 590 55052996482690021909974 591 57939406523387274076696 592 60974600653531470605548 593 64166119223505813302658 594 67521878317365805365941 595 71050188162254952197764 596 74759772424838936796833 597 78659788436620797053875 598 82759848392277633846768 599 87070041566878713598969 600 91600957600322457758483 601 96363710899224318316376 602 101369966209182490785272 603 106631965412434916635406 604 112162555608852561044568 605 117975218540510852093975 606 124084101423270224587093 607 130504049251324110606160 608 137250638644142122056208 609 144340213308015995745431 610 151789921188190455830525 611 159617753390617372234812 612 167842584956478365423523 613 176484217575979794132635 614 185563424332392443638827 615 195101996570998114523102 616 205122792992467313052746 617 215649791074244394161988 618 226708140928806937586975 619 238324221712114558918783 620 250525700701319124865931 621 263341595165690103081354 622 276802337160973122099543 623 290939841382755385719195 624 305787576221228348355031 625 321380638165611559390211 626 337755829713919581578657 627 354951740950193406180057 628 373008834959390116954808 629 391969537257182548398561 630 411878329420705072117136 631 432781847114015287678612 632 454728982711600670981937 633 477770992731730803973499 634 501961610301858298189676 635 527357162887548932308792 636 554016695527741494202774 637 582002099829295041567068 638 611378248986099556656520 639 642213139099143564546226 640 674578037087336697002560 641 708547635491050935658507 642 744200214484930323733469 643 781617811429828439775384 644 820886398309604493060452 645 862096067413066211556585 646 905341225638617675599565 647 950720797815088708862700 648 998338439451013528346319 649 1048302759342029330166438 650 1100727552486511100314271 651 1155732043778580668809391 652 1213441142969873151885049 653 1273985711412230557467468 654 1337502841117694497795985 655 1404136146694880503162889 656 1474036070747146885616242 657 1547360203342778537123392 658 1624273616196050849458356 659 1704949212225131489499932 660 1789568091183939024699137 661 1878319932094659774027646 662 1971403393241521622081023 663 2069026530518718351965200 664 2171407234962250108105239 665 2278773690330694993615121 666 2391364851640032671305529 667 2509430945596108071503484 668 2633233993911944495289929 669 2763048360539086636001679 670 2899161323889596274135394 671 3041873675171109777737850 672 3191500344008961771696579 673 3348371052579319028464642 674 3512830999533377402067180 675 3685241575047135084702338 676 3865981108392269225840678 677 4055445649483023559086092 678 4254049785920358371042550 679 4462227497119348818102348 680 4680433047177952615560714 681 4909141918215828202998422 682 5148851785990311677470873 683 5400083539673558369543396 684 5663382347760117845966687 685 5939318772158002405036601 686 6228489932608997786714852 687 6531520723675253769715269 688 6849065086629947029562286 689 7181807338689251199830578 690 7530463562132364565841325 691 7895783055964654204941994 692 8278549852898005589156373 693 8679584304540413995724739 694 9099744737816216945296780 695 9539929185766792534512379 696 10001077196022131364581503 697 10484171720373504785368904 698 10990241089030217584855643 699 11520361073295626328660141 700 12075657040563596641820028 701 12657306205702216887350444 702 13266539983071936782537774 703 13904646443605559039478905 704 14572972881573450312523994 705 15272928495853475785268336 706 16005987190738018764979294 707 16773690501523833628506619 708 17577650650361700233034916 709 18419553738074970323391165 710 19301163077907244585185183 711 20224322677411889056698957 712 21190960874968873352017346 713 22203094137688979448247993 714 23262831027761668917833864 715 24372376344601455167254152 716 25534035450469326074616148 717 26750218787570369333142153 718 28023446594978072812108593 719 29356353834088656463600382 720 30751695331688075830190482 721 32212351150097915164230528 722 33741332194278173650485474 723 35341786066181839123042420 724 37017003177103181588987568 725 38770423129214741722648704 726 40605641377973259760695961 727 42526416187567061770412776 728 44536675892104151371808140 729 46640526475775089177694765 730 48842259485796431468367716 731 51146360292521509085315052 732 53557516711725762985404061 733 56080628004704951668521748 734 58720814272497830335133545 735 61483426261230329728370674 736 64374055596308839904910890 737 67398545463934554701590494 738 70563001759203514270038074 739 73873804720865230842504230 740 77337621073672779134748299 741 80961416700134765542437925 742 84752469864412542420649867 743 88718385012058686089858344 744 92867107170304772419426201 745 97206936974640573599902349 746 101746546348524489442222153 747 106494994864187393916128673 748 111461746813682598331298028 749 116656689020552683099966652 750 122090149423775047259048049 751 127772916466969775194755056 752 133716259327253476757821491 753 139931949019556884023916856 754 146432280413742075902314805 755 153230095203411097266268147 756 160338805866943674484545692 757 167772420662989556824562989 758 175545569704425416742853092 759 183673532156616999952702876 760 192172264607761578866681029 761 201058430661071351721385332 762 210349431800655182150443325 763 220063439585109368987110050 764 230219429225100724904170639 765 240837214603560172669514574 766 251937484799568037094819722 767 263541842179543843702484159 768 275672842122022514600663154 769 288354034445043485443358195 770 301610006608071468074701936 771 315466428763342843671320509 772 329950100734665388123740100 773 345089001004923980816929928 774 360912337796940070653792820 775 377450602335827924917593563 776 394735624384668719461601877 777 412800630149111370705972009 778 431680302650493201142309601 779 451410844671178059604377927 780 472030044380124998023389755 781 493577343751147874447959202 782 516093909891000186454284110 783 539622709399237605945594578 784 564208585886872434655858683 785 589898340786053703949867981 786 616740817588487934958103492 787 644786989655969314661625378 788 674090051752323169641744374 789 704705515452190146748047740 790 736691308588504521494017705 791 770107878907151789687545351 792 805018302104247627952177377 793 841488394428661763477027642 794 879586830039941393761768606 795 919385263319564823351246311 796 960958456341607979943537291 797 1004384411717325525658708657 798 1049744511036971641855891617 799 1097123659141299990829968972 800 1146610434464731604454447950 801 1198297245702045786566407357 802 1252280495060783127174247043 803 1308660748372229043441816537 804 1367542912345028626062905676 805 1429036419257041819716350036 806 1493255419393147349436366354 807 1560318981549212210378824438 808 1630351301935534086683473605 809 1703481921826599533751505250 810 1779845954318162526108312577 811 1859584320567293543410022390 812 1942843995906368783317074687 813 2029778266237814413574811618 814 2120546995132991142413992279 815 2215316902075746247239808912 816 2314261852309082233323889698 817 2417563158761934167195543100 818 2525409896552430134075771311 819 2637999230584065921371829547 820 2755536756772185133827774676 821 2878236857459848088269144176 822 3006323071604837255574410539 823 3140028480343005999800985833 824 3279596108557682735001307211 825 3425279343110210185124226704 826 3577342368413193186679380090 827 3736060620055457567686757239 828 3901721257216363845860580004 829 4074623654636775133791134951 830 4255079914944938920621281989 831 4443415402167602632142834491 832 4639969297290147362521307681 833 4845095176764181055068664013 834 5059161614897200817136546000 835 5282552811096394770085762452 836 5515669242977741567373457931 837 5758928346392053728888317377 838 6012765223461850321352750217 839 6277633379766700847503506152 840 6554005491860323789555119553 841 6842374206350007830271155925 842 7143252971818237747824725191 843 7457176904917500100550742620 844 7784703692022521523195941950 845 8126414527879396360493478368 846 8482915092748615930409405430 847 8854836569598652277389862753 848 9242836702968921376144950401 849 9647600901185379316454738908 850 10069843383679158739759511397 851 10510308375228248129304402064 852 10969771349014745509497809172 853 11449040320465388490386618408 854 11948957193921390991401472186 855 12470399164264802493918841760 856 13014280175713190755776417384 857 13581552440082123898023402492 858 14173208016906262326106276012 859 14790280457904546578587597643 860 15433846518373582267554450264 861 16105027938195550440711181563 862 16804993295253439532498925776 863 17534959934156767382459106286 864 18296195973295898996420708184 865 19090022393362222786700058193 866 19917815210595518915738800740 867 20781007738148484289797774214 868 21681092939092299038902988639 869 22619625874725966501951180996 870 23598226251996699434205422803 871 24618581073988488344311691536 872 25682447397591979494227004028 873 26791655202630530753533051816 874 27948110376885650612425032557 875 29153797821639571656809857753 876 30410784682534355874552848911 877 31721223710735279832839840534 878 33087356759582240395252612336 879 34511518422116153203339087145 880 35996139815078772717802900926 881 37543752515203633986519301173 882 39156992653843940011902093161 883 40838605176219777692439213437 884 42591448271813131662942798591 885 44418497982694355824155281701 886 46322852996829206154762302557 887 48307739633690806823696731585 888 50376517029787224487357647570 889 52532682532012229373714034243 890 54779877307035600169059768733 891 57121892175269545163573165715 892 59562673678280806090105316505 893 62106330388863342765314659487 894 64757139473345579046236108207 895 67519553516078580763383178026 896 70398207616438722831306186985 897 73397926769079941690336156213 898 76523733538588129210778959442 899 79780856040123161510655960181 900 83174736238084123987652495279 901 86711038575300050304501195218 902 90395658945733680755910425794 903 94234734024188925789384330611 904 98234650967035730793713733110 905 102402057498508445142073394599 906 106743872397697539428728769285 907 111267296401939163515610903636 908 115979823542914638031106115141 909 120889252932402106283122503589 910 126003701015277398105671615125 911 131331614308040266612442241762 912 136881782641847828075717187205 913 142663352929768873227746739825 914 148685843478733126086288069041 915 154959158867438130294048157723 916 161493605412295777322788758133 917 168299907244350202621392321942 918 175389223020981540737857954422 919 182773163297125519592014507438 920 190463808581689913213518606256 921 198473728105835160317958987389 922 206815999330810977828372228379 923 215504228224103284990820608218 924 224552570333749358386907808250 925 233975752691823628894581709674 926 243789096579285240552496175821 927 254008541185611228247063728138 928 264650668197919457847608581850 929 275732727355613166230097233626 930 287272663007957762414627896758 931 299289141713430415671588962379 932 311801580921167798269552661064 933 324830178776377140509962214057 934 338395945093174656751603391679 935 352520733539973451494796418317 936 367227275084264617738341346788 937 382539212745420509027849382980 938 398481137706002760738001742350 939 415078626833979752000633301140 940 432358281670253767376964952766 941 450347768937967426456961717301 942 469075862632207218188460564987 943 488572487750949597240350705320 944 508868765730407596241559796923 945 529997061650333786278520426755 946 551991033277324527883515831310 947 574885682016751427268416072439 948 598717405846624942588224492530 949 623524054309472942088677736336 950 649344985641200262186546669353 951 676221126118884870378452181497 952 704195031712569057864378484675 953 733310952129321258406265318780 954 763614897341182980787668558536 955 795154706692077223989855210057 956 827980120682347425799762749179 957 862142855533320949436380673411 958 897696680638156617300618868201 959 934697499009243548235287984316 960 973203430836577322427292657004 961 1013274900275851218617810989851 962 1054974725589474250513391689917 963 1098368212768366167898266079038 964 1143523252767192357051770468532 965 1190510422490691155656712413328 966 1239403089673922965025680196621 967 1290277521804637490302990335941 968 1343212999241523583036250635984 969 1398291932687878633324208729994 970 1455599985186223057746167261873 971 1515226198805593657774479583419 972 1577263126199690003865827206166 973 1641806967220724438852298286965 974 1708957710780752085440481942885 975 1778819282159436730142202474742 976 1851499695964655757055432940032 977 1927111214960067238535656849404 978 2005770514981769849046609303238 979 2087598856174486788377706595095 980 2172722260786314306924392610188 981 2261271697769999613775771812243 982 2353383274447968837611050682196 983 2449198435507919802922998871666 984 2548864169605744658158516668569 985 2652533223862861008024817397637 986 2760364326555726265658476288526 987 2872522418306396324344427081913 988 2989178892094486661069307699259 989 3110511842422810269790504204181 990 3236706323981323969741662431691 991 3367954620166822122830967884823 992 3504456521829097578071579827346 993 3646419616628054122742383130598 994 3794059589400527268394779420565 995 3947600533950362194276112460249 996 4107275276690635070915208747802 997 4273325712582799207462787094176 998 4446003153834018120929057671301 999 4625568691831027269075937217947 1000 4812293572806574197158839545293