0 1 1 1 2 2 3 3 4 5 5 7 6 11 7 14 8 22 9 29 10 41 11 54 12 75 13 97 14 130 15 168 16 222 17 283 18 368 19 465 20 597 21 750 22 949 23 1183 24 1488 25 1841 26 2292 27 2822 28 3487 29 4267 30 5239 31 6376 32 7782 33 9429 34 11439 35 13798 36 16661 37 20007 38 24043 39 28763 40 34420 41 41021 42 48894 43 58066 44 68956 45 81627 46 96592 47 113981 48 134458 49 158190 50 186030 51 218263 52 255936 53 299478 54 350221 55 408759 56 476796 57 555157 58 645963 59 750392 60 871127 61 1009718 62 1169567 63 1352800 64 1563658 65 1804976 66 2082103 67 2398772 68 2761723 69 3175862 70 3649590 71 4189371 72 4805756 73 5507042 74 6306469 75 7214828 76 8248575 77 9421603 78 10754493 79 12264976 80 13978765 81 15918457 82 18115968 83 20600134 84 23410648 85 26583884 86 30169190 87 34212569 88 38775103 89 43914682 90 49706998 91 56224635 92 63561242 93 71807680 94 81079440 95 91490101 96 103182162 97 116296799 98 131009625 99 147496215 100 165972326 101 186655675 102 209811350 103 235708569 104 264672627 105 297035884 106 333196594 107 373564571 108 418627122 109 468887915 110 524942540 111 587409574 112 657015518 113 734518525 114 820804148 115 916799837 116 1023583666 117 1142288558 118 1274224832 119 1420774564 120 1583529005 121 1764170556 122 1964629360 123 2186951542 124 2433474695 125 2706683338 126 3009406090 127 3344655097 128 3715849311 129 4126635927 130 4581141782 131 5083777857 132 5639520688 133 6253696527 134 6932300164 135 7681756452 136 8509277793 137 9422604175 138 10430404828 139 11541992365 140 12767776096 141 14118948211 142 15607993139 143 17248347416 144 19054970317 145 21043972295 146 23233260226 147 25642131904 148 28291999509 149 31205953190 150 34409573448 151 37930457981 152 41799137793 153 46048564951 154 50715142427 155 55838177160 156 61461034767 157 67630552716 158 74398344010 159 81820168460 160 89957396708 161 98876346283 162 108649927535 163 119356939800 164 131083926810 165 143924434124 166 157981096427 167 173364866531 168 190197360848 169 208610056983 170 228746942742 171 250763686833 172 274830618294 173 301131888732 174 329868826471 175 361259091833 176 395540462782 177 432969994396 178 473828286024 179 518418673183 180 567072032715 181 620146018917 182 678030494397 183 741146833389 184 809954044484 185 884948186508 186 966669277083 187 1055700847435 188 1152677750829 189 1258285900871 190 1373271089985 191 1498438982808 192 1634665071563 193 1782894977070 194 1944155717269 195 2119556392542 196 2310300918457 197 2517689211120 198 2743131584058 199 2988150527299 200 3254397008634 201 3543652975124 202 3857849801707 203 4199071695169 204 4569576566742 205 4971800503523 206 5408381427714 207 5882164844605 208 6396230633878 209 6953900353717 210 7558767593813 211 8214707105890 212 8925909222399 213 9696891153538 214 10532536004784 215 11438106671730 216 12419290067856 217 13482214052911 218 14633497629910 219 15880271439483 220 17230234691696 221 18691679893431 222 20273557439529 223 21985505261633 224 23837922156066 225 25842003184032 226 28009822902224 227 30354377527502 228 32889679398470 229 35630806983111 230 38594012172602 231 41796779407194 232 45257947491122 233 48997779373428 234 53038100474064 235 57402380777345 236 62115891963524 237 67205803766978 238 72701362440696 239 78634003690540 240 85037555352642 241 91948369431898 242 99405552383696 243 107451119206196 244 116130254991473 245 125491494545276 246 135587019471423 247 146472867136260 248 158209268177305 249 170860889243979 250 184497216365060 251 199192836637833 252 215027873626048 253 232088313736654 254 250466500819731 255 270261513845936 256 291579728595624 257 314535254311727 258 339250571553012 259 365857036367218 260 394495604657615 261 425317413706042 262 458484604627153 263 494170992571483 264 532563000398537 265 573860430225960 266 618277523420912 267 666043848000656 268 717405501696406 269 772626131879285 270 831988300849394 271 895794656948588 272 964369483847007 273 1038060044165857 274 1117238337178250 275 1202302639350115 276 1293679498092486 277 1391825496609860 278 1497229515270453 279 1610414751949139 280 1731941286249653 281 1862408390950507 282 2002457439141407 283 2152774546754280 284 2314093868002165 285 2487200614459896 286 2672934789794046 287 2872194637128448 288 3085940870684479 289 3315200609574090 290 3561072171810523 291 3824729560495742 292 4107427893462122 293 4410508516797346 294 4735405153115617 295 5083649726626544 296 5456879323846294 297 5856842825602566 298 6285408785583371 299 6744572977404426 300 7236467309860473 301 7763368410606932 302 8327707712647173 303 8932081212064219 304 9579260876525044 305 10272205732598649 306 11014074766564899 307 11808239516098695 308 12658298655387583 309 13568092288582528 310 14541718434880262 311 15583549246727303 312 16698249637673685 313 17890795675868338 314 19166495628632671 315 20531010813797803 316 21990379368082483 317 23551039875054679 318 25219858203265402 319 27004154268782479 320 28911732332379394 321 30950911299883595 322 33130558915296821 323 35460126053259331 324 37949685299113698 325 40609969743438876 326 43452416501666733 327 46489210584422186 328 49733333975924619 329 53198615225781307 330 56899784782224320 331 60852531029634532 332 65073562658374210 333 69580671962148142 334 74392805120838770 335 79530133672706236 336 85014133693654770 337 90867666470147607 338 97115067679247245 339 103782238414108780 340 110896745601259171 341 118487924672042105 342 126586992604319430 343 135227163688929370 344 144443776751138076 345 154274425637646404 346 164759102359295063 347 175940344121919852 348 187863394341321734 349 200576368259558948 350 214130434018872531 351 228579999151393215 352 243982914157880398 353 260400682434840091 354 277898689097177706 355 296546437211658227 356 316417804929511694 357 337591311238733300 358 360150404835342948 359 384183762991132936 360 409785615998942816 361 437056083177607899 362 466101537182337014 363 497034981646287946 364 529976460150149514 365 565053480533589720 366 602401473884187257 367 642164271142921565 368 684494618103131819 369 729554710597199649 370 777516772195993864 371 828563655003798117 372 882889487531124395 373 940700348944856359 374 1002214995461813922 375 1067665616818905541 376 1137298650502076971 377 1211375630225032939 378 1290174098391925468 379 1373988557507735411 380 1463131492479014139 381 1557934437147572667 382 1658749119372179789 383 1765948656290407315 384 1879928836617391382 385 2001109459807528061 386 2129935771671352406 387 2266879964357880539 388 2412442783233947359 389 2567155206555518795 390 2731580243612573518 391 2906314815116399961 392 3091991764901589255 393 3289281964463736136 394 3498896563049188839 395 3721589342455469205 396 3958159233166160427 397 4209452948495030434 398 4476367797569343591 399 4759854631204908272 400 5060920986024924024 401 5380634378128853593 402 5720125816514792707 403 6080593484678562257 404 6463306665816676208 405 6869609857024883907 406 7300927153536986664 407 7758766845226844000 408 8244726312448618968 409 8760497160125441562 410 9307870683656425714 411 9888743602076922536 412 10505124159029852164 413 11159138523367148063 414 11853037597444528640 415 12589204161159472425 416 13370160467882273301 417 14198576216396038916 418 15077277023700041207 419 16009253318712986743 420 16997669791086383836 421 18045875310937022213 422 19157413463792581479 423 20336033612165338138 424 21585702638908357444 425 22910617279243075859 426 24315217208293449168 427 25804198786348854176 428 27382529641287161208 429 29055463985566669476 430 30828558860791653466 431 32707691202334165152 432 34699075931626707237 433 36809284963575906315 434 39045267352474535768 435 41414370458711605970 436 43924362376654355174 437 46583455500791031908 438 49400331488815804522 439 52384167493476492914 440 55544663941630366793 441 58892073727010767631 442 62437233116474257716 443 66191594230925510492 444 70167259423677656192 445 74377017412180136989 446 78834381510702273261 447 83553629814686765006 448 88549847711171404486 449 93838972560919966646 450 99437840955585065489 451 105364238390646803170 452 111636951788713285278 453 118275824709246080082 454 125301815713074791878 455 132737059713411595767 456 140604932818202290217 457 148930120491572682810 458 157738689578653544807 459 167058164018041351277 460 176917604828829403873 461 187347694193585048875 462 198380824270297054266 463 210051190552497095148 464 222394890460461245953 465 235450026981338871228 466 249256818095087283822 467 263857711803722397951 468 279297507559135237639 469 295623483907825856707 470 312885533211019521315 471 331136303260674227809 472 350431346718293535271 473 370829278200824129651 474 392391940014638111047 475 415184576367467554329 476 439276017139579126996 477 464738871051696405343 478 491649729397952630255 479 520089380191442126585 480 550143033984886348778 481 581900561226785762500 482 615456742517760592183 483 650911531643305919937 484 688370332858465208151 485 727944292320076893815 486 769750605262205049396 487 813912838833833475759 488 860561272324762514313 489 909833254726681567601 490 961873581496763526401 491 1016834890503780036195 492 1074878079177477627908 493 1136172742879995566604 494 1200897636686611182708 495 1269241160639758225239 496 1341401870844422100708 497 1417589016521325827280 498 1498023105582286610882 499 1582936498904747735098 500 1672574036083094567980 501 1767193692903386295703 502 1867067273550747808432 503 1972481137875898754655 504 2083736966981661060732 505 2201152567547150713507 506 2325062718423967789536 507 2455820060025911086037 508 2593796030343777080562 509 2739381848224801563099 510 2892989548071347764388 511 3055053066732176260097 512 3226029387092208751124 513 3406399739285342869282 514 3596670864418268643002 515 3797376341900605177721 516 4009077985684725913588 517 4232367310703022060684 518 4467867075257936752206 519 4716232900868866544156 520 4978154975822990225131 521 5254359844177216586258 522 5545612286993253628020 523 5852717297825636734676 524 6176522159826962174390 525 6517918626795454734922 526 6877845216162839820655 527 7257289616589264020698 528 7657291218852947887567 529 8078943773083075238073 530 8523398181774571255189 531 8991865432059258468275 532 9485619677489708970901 533 10006001473285423470577 534 10554421176187886913178 535 11132362513403451588327 536 11741386332750200198424 537 12383134539076766432136 538 13059334230125311788086 539 13771802037561787633802 540 14522448687495820648090 541 15313283786941392213027 542 16146420851793663140697 543 17024082583581315622313 544 17948606411934854045960 545 18922450310927134112805 546 19948198907713678318260 547 21028569892623513717199 548 22166420750748587711031 549 23364755825284277516722 550 24626733734434874611666 551 25955675153356769281535 552 27355070984877321595789 553 28828590931812616132608 554 30380092496719139212394 555 32013630423396090047128 556 33733466608258888747095 557 35544080497551848718947 558 37450180001011393152243 559 39456712939772267815596 560 41568879061843213419323 561 43792142644959238854385 562 46132245723096448205004 563 48595221958680590152573 564 51187411200001036141746 565 53915474748315227344751 566 56786411377671825914752 567 59807574134643530206922 568 62986687964831233512791 569 66331868196313620185773 570 69851639931082594436756 571 73554958377925758180758 572 77451230182352014570421 573 81550335790641928714457 574 85862652908585435770789 575 90399081095974959063697 576 95171067562830666483833 577 100190634212813606145463 578 105470406005706154547028 579 111023640689242670486901 580 116864259978604947498210 581 123006882239174847139157 582 129466856757873977126971 583 136260299664520515950164 584 143404131596181339782745 585 150916117172365667447732 586 158814906382376490640491 587 167120077959716164760182 588 175852184853952085507557 589 185032801882683134809875 590 194684575683922324174913 591 204831277060040049905636 592 215497855844386234224016 593 226710498391071530575173 594 238496687830801901237557 595 250885267203492646812175 596 263906505623393591680751 597 277592167598692821658181 598 291975585675324417125191 599 307091736539278426986202 600 322977320762391857780076 601 339670846339441158372966 602 357212716218141624920080 603 375645319984698514813996 604 395013129924637970496165 605 415362801637811323578031 606 436743279447052920525579 607 459205906797190349155174 608 482804541905415274676634 609 507595678879219636793137 610 533638574586367860430503 611 560995381514474631354335 612 589731286930227830009867 613 619914658599221505475914 614 651617197404302867224265 615 684914097149010548122677 616 719884211914372193111084 617 756610231283673361413519 618 795178863836551504374446 619 835681029257706082236603 620 878212059497629262155699 621 922871909364213578029732 622 969765377021919804632333 623 1019002334814078136694150 624 1070697970927798875263057 625 1124973042357221348330207 626 1181954139731197471098852 627 1241773964505045745745670 628 1304571619133258432778767 629 1370492910770799052692968 630 1439690669175193574739927 631 1512325079409519223306849 632 1588564030078751875664110 633 1668583477756912259288236 634 1752567828403102458182637 635 1840710336486520616076232 636 1933213522690022442992261 637 2030289610980755877418860 638 2132160985995278592549190 639 2239060671602434846562881 640 2351232831676166852477697 641 2468933294023168928762892 642 2592430098589858213814419 643 2722004070982701010274907 644 2857949422526864728357359 645 3000574377994536090146039 646 3150201832337289076146946 647 3307170037660048830151922 648 3471833321890147605664627 649 3644562840494923934849216 650 3825747362831025320597576 651 4015794094605334087741529 652 4215129538171816260651102 653 4424200392282188441325247 654 4643474493168320486872520 655 4873441798724773588100165 656 5114615417836580958428830 657 5367532686784816179715520 658 5632756294957001732098168 659 5910875461973900291289886 660 6202507168657728496648594 661 6508297444148499482911944 662 6828922711808963261004065 663 7165091196437607977512371 664 7517544395664580306717192 665 7887058618281892889453129 666 8274446592637773196631704 667 8680559148099260385574707 668 9106286972990300305773595 669 9552562452284848920554021 670 10020361588763972381198631 671 10510706011216515722856303 672 11024665073720517050338831 673 11563358049911820543887736 674 12127956426633997341826820 675 12719686301232074777974940 676 13339830887272343677942132 677 13989733133338510498174800 678 14670798460108549057931177 679 15384497620784771581237461 680 16132369690540414052634163 681 16916025190514999758570078 682 17737149352520747184171753 683 18597505530492787734497216 684 19498938765387906325641628 685 20443379510109370967349339 686 21432847521752229771544856 687 22469455928339583178969128 688 23555415477985149174802023 689 24693038978297888256898365 690 25884745934660617024130220 691 27133067395900479065539020 692 28440651016740261082731185 693 29810266346312278060663867 694 31244810352946496797042956 695 32747313195345562523536061 696 34320944251252311725373028 697 35969018414626242636827532 698 37695002673405762589681292 699 39502522979855623366393311 700 41395371426631518942137432 701 43377513741630134746778932 702 45453097115902847581982563 703 47626458378863554164469630 704 49902132536313880643664391 705 52284861686779744963215453 706 54779604333034809439636507 707 57391545105678268585091538 708 60126104917111132898985075 709 62988951564271304272922370 710 65986010800066442659690156 711 69123477893487332598138118 712 72407829700072499949685573 713 75845837264469812256672062 714 79444578978646063605349625 715 83211454319405880414207441 716 87154198190812263727487312 717 91280895897251253214494204 718 95599998774949010674888453 719 100120340509944562339980893 720 104851154172731881823886588 721 109802090000030138683858922 722 114983233956506549867527561 723 120405127109577568518690218 724 126078785852946261465664956 725 132015723014897721074422196 726 138227969890085154884251963 727 144728099233973165138312368 728 151529249262007313893757984 729 158645148696090668255539919 730 166090142904056484842749945 731 173879221178424136017805741 732 182028045204054875565525592 733 190552978765017762627271812 734 199471118744542894065070187 735 208800327472738901439600610 736 218559266480573380620963912 737 228767431719532096073558424 738 239445190310468254860071960 739 250613818886200020418219045 740 262295543596803936012275691 741 274513581847741963392684320 742 287292185845665239066353887 743 300656688028085554605174988 744 314633548458150360662817325 745 329250404267278922093005984 746 344536121233826741714507640 747 360520847587658620296195724 748 377236070136312140182752904 749 394714672810357128681573846 750 412990997731779299699859041 751 432100908911371376477714873 752 452081858687790407939042712 753 472972957023349097760710999 754 494815043778771098423217213 755 517650764091828033581429453 756 541524646992461404845107679 757 566483187389985954917335372 758 592574931576219056717639735 759 619850566391708978130186944 760 648363012211087836584927270 761 678167519907270056034005790 762 709321771963720655987724632 763 741885987908114069377296706 764 775923034250907353628042540 765 811498539116887054595806831 766 848681011768704665252171548 767 887541967226430999206557948 768 928156056198924895695339568 769 970601200548351546119480908 770 1014958734521821526332135649 771 1061313551990234323479587391 772 1109754259947982631389737122 773 1160373338533911745543260143 774 1213267307848508600916026577 775 1268536901849715438177582014 776 1326287249625427538801699778 777 1386628064348899187308023305 778 1449673840240113113941096949 779 1515544057865144854391787074 780 1584363398123639904590432775 781 1656261965284382107879806269 782 1731375519448369045724685448 783 1809845718829634201668214920 784 1891820372264946793592550869 785 1977453702375393380480892749 786 2066906619825301047691654592 787 2160347009136977405127389334 788 2257950026543882231081538155 789 2359898410379104041557848889 790 2466382804521966872022895408 791 2577602095441203294415601544 792 2693763763401032471935668644 793 2815084248413563494825107024 794 2941789331550946823760770258 795 3074114532249377069375634148 796 3212305522269313225604147075 797 3356618556996700794273358023 798 3507320924804676242905944630 799 3664691415217540965343712275 800 3829020806656107168003879441 801 4000612374567876153424727575 802 4179782420785644424713758784 803 4366860824984718800380385352 804 4562191619152092208241025923 805 4766133586009936247073473556 806 4979060882382205062957098949 807 5201363688524774750784194783 808 5433448884489499258717071743 809 5675740754627042250637052392 810 5928681721387088982277183708 811 6192733109612111407362763700 812 6468375942578682438211199706 813 6756111771081256708770482542 814 7056463536915548580444441745 815 7369976472163194747064674313 816 7697219035746329413462826892 817 8038783888769197777074120688 818 8395288910235963803469774059 819 8767378254786637903848546909 820 9155723454170560275113612512 821 9561024564234274695375843920 822 9984011359284037750627853536 823 10425444575745623373619187523 824 10886117207133845204759023383 825 11366855852412067648538072115 826 11868522119918578685572453896 827 12392014089110430573611710164 828 12938267832479320715703795147 829 13508259000074190286379198036 830 14103004469177112935451146990 831 14723564061766050019534327386 832 15371042332518480010149428470 833 16046590430204381473902114311 834 16751408035446671050877789035 835 17486745377929751489359003500 836 18253905336276342153805152015 837 19054245623924063164399080514 838 19889181064483415404154017489 839 20760185960179558583645413396 840 21668796557141930665104867112 841 22616613611436746175517320032 842 23605305059911400835293022639 843 24636608800061872787510268319 844 25712335583321495284818524386 845 26834372026323507726981994673 846 28004683744891389215115677693 847 29225318615677951810035995833 848 30498410170591176431698040310 849 31826181129325736849443975464 850 33210947075552750789171215510 851 34655120282516380450638023049 852 36161213694037355302255766520 853 37731845067135914405844216948 854 39369741282757339015294541313 855 41077742831313327922021083512 856 42858808480043834365618226907 857 44716020129453142033344065572 858 46652587866387598567045182965 859 48671855221592191596585491373 860 50777304639920769826143678455 861 52972563171666736851856868414 862 55261408393844470939906955235 863 57647774570567787430832235569 864 60135759062062964481700476486 865 62729628992195873220887151032 866 65433828184813856033301200972 867 68252984379573042031940043934 868 71191916738375070970821809004 869 74255643653937496233975956907 870 77449390872510053062904737591 871 80778599943181933892389373298 872 84248937006750401298783533272 873 87866301937589269693701322892 874 91636837852521088291430518084 875 95566941001203092698253629013 876 99663271053145461036622313163 877 103932761797027684666443569527 878 108382632268633784750204586470 879 113020398324318656632580846662 880 117853884677622731541214093536 881 122891237417291459604824144963 882 128140937025714812500951270527 883 133611811917492838270599657726 884 139313052518649869249074763330 885 145254225907766382972952304656 886 151445291041176353958337395609 887 157896614585184253836590805817 888 164618987379201691601312504588 889 171623641554574616434126177097 890 178922268334889918694180206554 891 186527036544490856417602946526 892 194450611853026191722614277815 893 202706176784873611087924986818 894 211307451523456880287296337243 895 220268715541572824727432442541 896 229604830090112839964329149227 897 239331261578747527014177120115 898 249464105883508190078075244524 899 260020113617476854217456095345 900 271016716402265433643401879948 901 282472054179343928143364084996 902 294405003601858177036812565624 903 306835207549066125862265467656 904 319783105807222328208998114744 905 333269966962346458883798005011 906 347317921552141565078159931147 907 361949996526060554437436835767 908 377190151064488299013519554560 909 393063313809876004438425800120 910 409595421564782778135513737342 911 426813459513795619397672676661 912 444745503028577999936959259425 913 463420761117471827667848032000 914 482869621583529290648505339837 915 503123697957196208809698415206 916 524215878272505982829150982755 917 546180375758171957021270855920 918 569052781517803199908317010136 919 592870119276195107625741822286 920 617670902271698154765224278627 921 643495192377607329762418017833 922 670384661538797568087847849389 923 698382655612998795846813275142 924 727534260709635151628132893197 925 757886372122567839399586419893 926 789487765956878808735311768429 927 822389173553512741045194096120 928 856643358819679342527461356954 929 892305198576883846701218732476 930 929431766042846402431685141425 931 968082417567844281948928044689 932 1008318882750734931136912627618 933 1050205358064521861836595015937 934 1093808604126405559712790948400 935 1139198046752221385894126176060 936 1186445881940629314009678691628 937 1235627184937762958567746765776 938 1286820023538919473922544476262 939 1340105575789626321036393392855 940 1395568252254736962923130497329 941 1453295823030404924977720604019 942 1513379549680576604788627309165 943 1575914322286317020309206193472 944 1640998801803583892245639590961 945 1708735567932251648734223704440 946 1779231272707036386137159511256 947 1852596800028710028878591633398 948 1928947431362430391682669216965 949 2008403017838343567489966484454 950 2091088158998686315007069356119 951 2177132388444582918366036861060 952 2266670366645482025318118562166 953 2359842081183830714124673385408 954 2456793054718064300211873297550 955 2557674560957378488250287864536 956 2662643848953016108602473710467 957 2771864376021980324563134601573 958 2885506049631194317681814882508 959 3003745478582157934121559657057 960 3126766233849164755589970866708 961 3254759119437088006648823360728 962 3387922453638728488315116218790 963 3526462361085645479063185780956 964 3670593076001419953369691743864 965 3820537257081283379047231769002 966 3976526314438194476713289931922 967 4138800749071565143388204549918 968 4307610505332189288008806016127 969 4483215336874266581007864727931 970 4665885186604057834289553401338 971 4855900581153357145669817116943 972 5053553040425998037554770370952 973 5259145502785666775689351356118 974 5472992766474817679152717281308 975 5695421947876053228746027917774 976 5926772957250452517655421804444 977 6167398992610523767436788725584 978 6417667052410294029571505139033 979 6677958467759985890518988330210 980 6948669454899411145470071861712 981 7230211688691021738847512494264 982 7523012897922216409531928053811 983 7827517483235323977389426177445 984 8144187158534465391505322018127 985 8473501616749479945668928547492 986 8815959220870160857891420165166 987 9172077721197348917179007317037 988 9542394999792938127343328312771 989 9927469843146642030975757068467 990 10327882744115498955726812953502 991 10744236734230563871976686037456 992 11177158247506180272414889492440 993 11627298016928566381130024838197 994 12095332004844417569293414567335 995 12581962368514650221373810935307 996 13087918462145622242398710520554 997 13613957876757897535195620556097 998 14160867519303310531758540418550 999 14729464732492370447238000059786 1000 15320598456848465955070226411130