0 1 1 1 2 2 3 6 4 21 5 73 6 237 7 702 8 1881 9 4577 10 10216 11 21158 12 41097 13 75561 14 132523 15 223134 16 362589 17 571137 18 875246 19 1308934 20 1915277 21 2748105 22 3873897 23 5373886 24 7346385 25 9909345 26 13203156 27 17393702 28 22675681 29 29276201 30 37458663 31 47526942 32 59829877 33 74766081 34 92789082 35 114412806 36 140217413 37 170855497 38 207058661 39 249644478 40 299523849 41 357708769 42 425320512 43 503598246 44 593908089 45 697752617 46 816780835 47 952798622 48 1107779661 49 1283876865 50 1483434310 51 1708999686 52 1963337277 53 2249441481 54 2570550881 55 2930162878 56 3332048897 57 3780270177 58 4279194156 59 4833511462 60 5448253521 61 6128810793 62 6880951647 63 7710841886 64 8625064933 65 9630642689 66 10735057074 67 11946272262 68 13272757621 69 14723511369 70 16308084957 71 18036608190 72 19919815097 73 21969070561 74 24196397720 75 26614506150 76 29236820841 77 32077511977 78 35151525531 79 38474614686 80 42063372093 81 45935262977 82 50108659102 83 54602873606 84 59438196717 85 64635932361 86 70218435673 87 76209151422 88 82632653361 89 89514684513 90 96882198404 91 104763401254 92 113187795137 93 122186222121 94 131790909399 95 142035515422 96 152955177045 97 164586557697 98 176967896586 99 190139058950 100 204141587365 101 219018754121 102 234815614677 103 251579062206 104 269357883241 105 288202814433 106 308166600432 107 329304052902 108 351672110681 109 375329901097 110 400338802451 111 426762507678 112 454667089197 113 484121064961 114 515195465718 115 547963903494 116 582502641309 117 618890664137 118 657209751121 119 697544549054 120 739982647137 121 784614653025 122 831534270172 123 880838376486 124 932627104305 125 987003921705 126 1044075715151 127 1103952873502 128 1166749373381 129 1232582865921 130 1301574764898 131 1373850336262 132 1449538789077 133 1528773367881 134 1611691446477 135 1698434623166 136 1789148817433 137 1883984368097 138 1983096132936 139 2086643589798 140 2194790939209 141 2307707208489 142 2425566357387 143 2548547385246 144 2676834439709 145 2810616926977 146 2950089623630 147 3095452790022 148 3246912285261 149 3404679683785 150 3568972393545 151 3740013775806 152 3918033266577 153 4103266499681 154 4295955431476 155 4496348467238 156 4704700589217 157 4921273486377 158 5146335685831 159 5380162685982 160 5623037091381 161 5875248749313 162 6137094888122 163 6408880257286 164 6690917269253 165 6983526143049 166 7287035049669 167 7601780259262 168 7928106290121 169 8266366059489 170 8616921036192 171 8980141395110 172 9356406173497 173 9746103429161 174 10149630400515 175 10567393668510 176 10999809320461 177 11447303115777 178 11910310653606 179 12389277542406 180 12884659571453 181 13396922884297 182 13926544154177 183 14474010761406 184 15039820972737 185 15624484122721 186 16228520797068 187 16852463018022 188 17496854431761 189 18162250497833 190 18849218680639 191 19558338642974 192 20290202441637 193 21045414725121 194 21824592933394 195 22628367499782 196 23457382054965 197 24312293633097 198 25193772880061 199 26102504263870 200 27039186287225 201 28004531702241 202 28999267727352 203 30024136266406 204 31079894129961 205 32167313258793 206 33287180949627 207 34440300083102 208 35627489353981 209 36849583503617 210 38107433554686 211 39401907048198 212 40733888282797 213 42104278556361 214 43513996409913 215 44963977873854 216 46455176716529 217 47988564695137 218 49565131808996 219 51185886555174 220 52851856186497 221 54564086971945 222 56323644459447 223 58131613741086 224 59989099720725 225 61897227384065 226 63857142071146 227 65870009751302 228 67937017300581 229 70059372781641 230 72238305726133 231 74475067419582 232 76770931188777 233 79127192691681 234 81545170209872 235 84026204943526 236 86571661308953 237 89182927238697 238 91861414484211 239 94608558921118 240 97425820857069 241 100314685342209 242 103276662482262 243 106313287754246 244 109426122324829 245 112616753371337 246 115886794405425 247 119237885599422 248 122671694115361 249 126189914436705 250 129794268702780 251 133486507045926 252 137268407931377 253 141141778499881 254 145108454913071 255 149170302701598 256 153329217116037 257 157587123480577 258 161945977549506 259 166407765866502 260 170974506126741 261 175648247541833 262 180431071207597 263 185325090474686 264 190332451322073 265 195455332733409 266 200695947076264 267 206056540484262 268 211539393242121 269 217146820173609 270 222881171032427 271 228744830896030 272 234740220562397 273 240869796949761 274 247136053499310 275 253541520580870 276 260088765901581 277 266780394917577 278 273619051248681 279 280607417096126 280 287748213663313 281 295044201579617 282 302498181327252 283 310112993671206 284 317891520092257 285 325836683223081 286 333951447287463 287 342238818542622 288 350701845724661 289 359343620497153 290 368167277902874 291 377175996818694 292 386373000413637 293 395761556610121 294 405344978548389 295 415126625054142 296 425109901109385 297 435298258326497 298 445695195425536 299 456304258714790 300 467129042574585 301 478173189944361 302 489440392813027 303 500934392712606 304 512658981215181 305 524618000433153 306 536815343522822 307 549254955191302 308 561940832206781 309 574877023912137 310 588067632741921 311 601516814742718 312 615228780096897 313 629207793649761 314 643458175440108 315 657984301234214 316 672790603063249 317 687881569764137 318 703261747523871 319 718935740427294 320 734908211008357 321 751183880804865 322 767767530916722 323 784664002567686 324 801878197670645 325 819415079396425 326 837279672746141 327 855477065127102 328 874012406932281 329 892890912123361 330 912117858817368 331 931698589876902 332 951638513503977 333 971943103837481 334 992617901554267 335 1013668514473886 336 1035100618166973 337 1056919956567297 338 1079132342587486 339 1101743658738438 340 1124759857752429 341 1148186963209929 342 1172031070170137 343 1196298345805246 344 1220995030038449 345 1246127436185697 346 1271701951601220 347 1297725038326822 348 1324203233744961 349 1351143151235625 350 1378551480837015 351 1406434989910046 352 1434800523806677 353 1463655006542081 354 1493005441470666 355 1522858911965958 356 1553222582104357 357 1584103697352777 358 1615509585260181 359 1647447656153022 360 1679925403834601 361 1712950406288353 362 1746530326385072 363 1780672912594086 364 1815385999698393 365 1850677509513769 366 1886555451611859 367 1923027924047262 368 1960103114088621 369 1997789298953729 370 2036094846548662 371 2075028216210950 372 2114597959456797 373 2154812720732361 374 2195681238169105 375 2237212344343230 376 2279414967039201 377 2322298130017377 378 2365870953785756 379 2410142656375846 380 2455122554122673 381 2500820062448937 382 2547244696653327 383 2594406072703006 384 2642313908030277 385 2690978022333441 386 2740408338381858 387 2790614882825222 388 2841607787007061 389 2893397287782473 390 2945993728340109 391 2999407559028414 392 3053649338186137 393 3108729732977121 394 3164659520229384 395 3221449587278502 396 3279110932815305 397 3337654667737897 398 3397092016008011 399 3457434315511710 400 3518693018924445 401 3580879694580481 402 3644006027346702 403 3708083819500806 404 3773124991613901 405 3839141583437513 406 3906145754795017 407 3974149786477502 408 4043166081144081 409 4113207164226657 410 4184285684839156 411 4256414416691238 412 4329606259006497 413 4403874237445161 414 4479231505031303 415 4555691343084574 416 4633267162156469 417 4711972502971137 418 4791821037370746 419 4872826569265414 420 4955003035587717 421 5038364507251785 422 5122925190116997 423 5208699425956286 424 5295701693429065 425 5383946609058785 426 5473448928215136 427 5564223546100902 428 5656285498743481 429 5749649963991081 430 5844332262513603 431 5940347858808222 432 6037712362209677 433 6136441527905281 434 6236551257954662 435 6338057602314246 436 6440976759866493 437 6545325079453897 438 6651119060917761 439 6758375356141758 440 6867110770100289 441 6977342261911649 442 7089086945896012 443 7202362092638246 444 7317185130055569 445 7433573644470057 446 7551545381686015 447 7671118248072222 448 7792310311649061 449 7915139803180545 450 8039625117271250 451 8165784813468166 452 8293637617367477 453 8423202421726281 454 8554498287579261 455 8687544445360318 456 8822360296029177 457 8958965412202977 458 9097379539292856 459 9237622596645542 460 9379714678689961 461 9523676056088873 462 9669527176895547 463 9817288667715486 464 9966981334873213 465 10118626165584129 466 10272244329131454 467 10427857178048262 468 10585486249304621 469 10745153265499849 470 10906880136059897 471 11070688958439870 472 11236602019331697 473 11404641795876961 474 11574830956884900 475 11747192364055590 476 11921749073208321 477 12098524335515177 478 12277541598739831 479 12458824508481566 480 12642396909424533 481 12828282846592257 482 13016506566607402 483 13207092518956806 484 13400065357261797 485 13595449940553801 486 13793271334555253 487 13993554812965822 488 14196325858753961 489 14401610165453793 490 14609433638467344 491 14819822396372134 492 15032802772234137 493 15248401314926121 494 15466644790451379 495 15687560183272862 496 15911174697647725 497 16137515758967297 498 16366611015102486 499 16598488337754630 500 16833175823811805 501 17070701796710601 502 17311094807803377 503 17554383637731006 504 17800597297801121 505 18049765031371873 506 18301916315241212 507 18557080861041702 508 18815288616640881 509 19076569767547177 510 19340954738321391 511 19608474193993758 512 19879159041486597 513 20153040431042561 514 20430149757658498 515 20710518662524934 516 20994179034471189 517 21281163011416137 518 21571502981824621 519 21865231586169534 520 22162381718399577 521 22462986527412705 522 22767079418535272 523 23074694055006886 524 23385864359470985 525 23700624515471145 526 24019008968953131 527 24341052429772702 528 24666789873209181 529 24996256541484801 530 25329487945289838 531 25666519865313542 532 26007388353780877 533 26352129735995081 534 26700780611886057 535 27053377857564606 536 27409958626882513 537 27770560352998497 538 28135220749950036 539 28503977814231078 540 28876869826375649 541 29253935352547369 542 29635213246134887 543 30020742649353246 544 30410562994851189 545 30804714007324417 546 31203235705134810 547 31606168401935622 548 32013552708302661 549 32425429533371465 550 32841840086480485 551 33262825878820286 552 33688428725088777 553 34118690745152481 554 34553654365713856 555 34993362321984678 556 35437857659365497 557 35887183735131177 558 36341384220122531 559 36800503100444062 560 37264584679167821 561 37733673578043393 562 38207814739214022 563 38687053426938886 564 39171435229321533 565 39661006060044489 566 40155812160110049 567 40655900099587262 568 41161316779365121 569 41672109432911969 570 42188325628041132 571 42710013268682790 572 43237220596662097 573 43769996193483561 574 44308388982121695 575 44852448228817950 576 45402223544883941 577 45957764888510977 578 46519122566585906 579 47086347236513286 580 47659489908043893 581 48238601945109577 582 48823735067664477 583 49414941353532606 584 50012273240261817 585 50615783526984161 586 51225525376282648 587 51841552316064422 588 52463918241440361 589 53092677416611113 590 53727884476759579 591 54369594429949854 592 55017862659032637 593 55672744923557121 594 56334297361689374 595 57002576492137222 596 57677639216081645 597 58359542819114697 598 59048344973183961 599 59744103738543550 600 60446877565711665 601 61156725297434721 602 61873706170658052 603 62597879818503206 604 63329306272251841 605 64068045963336233 606 64814159725336407 607 65567708795983902 608 66328754819172181 609 67097359846973697 610 67873586341663626 611 68657497177750278 612 69449155644012197 613 70248625445541961 614 71055970705796693 615 71871255968655294 616 72694546200482409 617 73525906792199137 618 74365403561360496 619 75213102754239654 620 76069071047918937 621 76933375552387625 622 77806083812646547 623 78687263810819486 624 79576983968271405 625 80475313147733505 626 81382320655435126 627 82298076243242502 628 83222650110804381 629 84156112907704521 630 85098535735621073 631 86049990150492862 632 87010548164692577 633 87980282249206881 634 88959265335823452 635 89947570819324966 636 90945272559690033 637 91952444884301097 638 92969162590159311 639 93995500946106398 640 95031535695053509 641 96077343056217089 642 97132999727361762 643 98198582887050246 644 99274170196900309 645 100359839803848777 646 101455670342422605 647 102561740937017022 648 103678131204180761 649 104804921254908385 650 105942191696939720 651 107090023637066406 652 108248498683445577 653 109417698947920681 654 110597707048349451 655 111788606110939038 656 112990479772588317 657 114203412183237377 658 115427488008224206 659 116662792430648582 660 117909411153743181 661 119167430403251913 662 120436936929815497 663 121718018011364286 664 123010761455518353 665 124315255601994849 666 125631589325022644 667 126959852035764262 668 128300133684745121 669 129652524764290089 670 131017116310967367 671 132393999908039710 672 133783267687922997 673 135185012334652161 674 136599327086354490 675 138026305737730310 676 139466042642541061 677 140918632716104777 678 142384171437798981 679 143862754853571006 680 145354479578455753 681 146859442799100897 682 148377742276299552 683 149909476347530406 684 151454743929505337 685 153013644520724521 686 154586278204039043 687 156172745649221022 688 157773148115541261 689 159387587454354433 690 161016166111691814 691 162658987130861574 692 164316154155056637 693 165987771429970121 694 167673943806418369 695 169374776742971582 696 171090376308592065 697 172820849185280097 698 174566302670727436 699 176326844680978470 700 178102583753099025 701 179893629047852841 702 181700090352385727 703 183522078082917406 704 185359703287441061 705 187213077648430593 706 189082313485555602 707 190967523758404102 708 192868822069212981 709 194786322665606217 710 196720140443340861 711 198670390949060798 712 200637190383058297 713 202620655602043361 714 204620904121920888 715 206638054120575654 716 208672224440665129 717 210723534592420137 718 212792104756453371 719 214878055786575774 720 216981509212620797 721 219102587243276545 722 221241412768925822 723 223398109364494086 724 225572801292305325 725 227765613504945865 726 229976671648136121 727 232206102063610302 728 234454031792004081 729 236720588575750241 730 239005900861982308 731 241310097805446182 732 243633309271419777 733 245975665838640681 734 248337298802241847 735 250718340176695326 736 253118922698764053 737 255539179830461697 738 257979245762020586 739 260439255414867718 740 262919344444608869 741 265419649244020809 742 267940306946051637 743 270481455426829246 744 273043233308677929 745 275625779963143137 746 278229235514024400 747 280853740840416422 748 283499437579758361 749 286166468130891305 750 288854975657123955 751 291565104089306526 752 294296998128912877 753 297050803251130881 754 299826665707961046 755 302624732531323398 756 305445151536172637 757 308288071323621577 758 311153641284072881 759 314042011600359102 760 316953333250891041 761 319887758012814433 762 322845438465174972 763 325826527992091686 764 328831180785938673 765 331859551850535209 766 334911797004344239 767 337988072883679262 768 341088536945919621 769 344213347472734209 770 347362663573313602 771 350536645187610630 772 353735453089589397 773 356959248890482761 774 360208195042058285 775 363482454839892670 776 366782192426654681 777 370107572795396577 778 373458761792854056 779 376835926122754726 780 380239233349135113 781 383668851899666217 782 387124951068987627 783 390607701022050206 784 394117272797467357 785 397653838310874881 786 401217570358299438 787 404808642619535622 788 408427229661531661 789 412073506941783753 790 415747650811739049 791 419449838520207294 792 423180248216781137 793 426939058955265121 794 430726450697113364 795 434542604314875942 796 438387701595653985 797 442261925244563497 798 446165458888207911 799 450098487078159390 800 454061195294448885 801 458053769949064961 802 462076398389461402 803 466129268902073606 804 470212570715843781 805 474326494005754953 806 478471229896373797 807 482646970465402302 808 486853908747238281 809 491092238736544737 810 495362155391828096 811 499663854639025318 812 503997533375099897 813 508363389471646761 814 512761621778506083 815 517192430127386014 816 521656015335494349 817 526152579209179137 818 530682324547578246 819 535245455146277894 820 539842175800980157 821 544472692311179465 822 549137211483848097 823 553835941137130686 824 558569090104047745 825 563336868236208225 826 568139486407531116 827 572977156517976102 828 577850091497283281 829 582758505308721961 830 587702612952848543 831 592682630471273502 832 597698774950437477 833 602751264525396481 834 607840318383616242 835 612966156768775686 836 618129000984579573 837 623329073398580297 838 628566597446008861 839 633841797633615038 840 639154899543516729 841 644506129837058529 842 649895716258679512 843 655323887639790246 844 660790873902659049 845 666296906064307497 846 671842216240415195 847 677427037649233822 848 683051604615510461 849 688716152574420225 850 694420918075508190 851 700166138786640646 852 705952053497965677 853 711778902125883081 854 717646925717023641 855 723556366452237758 856 729507467650593457 857 735500473773383777 858 741535630428143556 859 747613184372675622 860 753733383519086401 861 759896476937830953 862 766102714861767447 863 772352348690221086 864 778645630993057493 865 784982815514765569 866 791364157178549834 867 797789912090432262 868 804260337543363621 869 810775692021344329 870 817336235203554837 871 823942227968495550 872 830593932398136297 873 837291611782075361 874 844035530621708080 875 850825954634405030 876 857663150757699801 877 864547387153486377 878 871478933212226131 879 878458059557164446 880 885485038048556973 881 892560141787905537 882 899683645122203702 883 906855823648192006 884 914076954216622877 885 921347314936535241 886 928667185179538833 887 936036845584108222 888 943456578059886561 889 950926665791999073 890 958447393245376284 891 966019046169087014 892 973641911600681137 893 981316277870542121 894 989042434606249359 895 996820672736950302 896 1004651284497742405 897 1012534563434064897 898 1020470804406100386 899 1028460303593186310 900 1036503358498236245 901 1044600267952171081 902 1052751332118360077 903 1060956852497071806 904 1069217131929935001 905 1077532474604409313 906 1085903186058265992 907 1094329573184078502 908 1102811944233723081 909 1111350608822889257 910 1119945877935600331 911 1128598063928743838 912 1137307480536611997 913 1146074442875452161 914 1154899267448027278 915 1163782272148186374 916 1172723776265445069 917 1181724100489576137 918 1190783566915210121 919 1199902499046446014 920 1209081221801472017 921 1218320061517196385 922 1227619345953888372 923 1236979404299829286 924 1246400567175973665 925 1255883166640620585 926 1265427536194095111 927 1275034010783439902 928 1284702926807116981 929 1294434622119719681 930 1304229436036694778 931 1314087709339074822 932 1324009784278220677 933 1333996004580574281 934 1344046715452421637 935 1354162263584666046 936 1364342997157611593 937 1374589265845756897 938 1384901420822599136 939 1395279814765448358 940 1405724801860252089 941 1416236737806430249 942 1426815979821720387 943 1437462886647033246 944 1448177818551318669 945 1458961137336441857 946 1469813206342069990 947 1480734390450569222 948 1491725056091912061 949 1502785571248595145 950 1513916305460567425 951 1525117629830168766 952 1536389917027078977 953 1547733541293277281 954 1559148878448012236 955 1570636305892782118 956 1582196202616325777 957 1593828949199623977 958 1605534927820911231 959 1617314522260698142 960 1629168117906804261 961 1641096101759401473 962 1653098862436067922 963 1665176790176852486 964 1677330276849349813 965 1689559715953785929 966 1701865502628114429 967 1714248033653123262 968 1726707707457552121 969 1739244924123220449 970 1751860085390166072 971 1764553594661794470 972 1777325857010038697 973 1790177279180529961 974 1803108269597778875 975 1816119238370367390 976 1829210597296151421 977 1842382759867474177 978 1855636141276390206 979 1868971158419900166 980 1882388229905196333 981 1895887776054918857 982 1909470218912422777 983 1923135982247055806 984 1936885491559446897 985 1950719174086805601 986 1964637458808232228 987 1978640776450038822 988 1992729559491080961 989 2006904242168100393 990 2021165260481078519 991 2035513052198600734 992 2049948056863231637 993 2064470715796901121 994 2079081472106301354 995 2093780770688294662 996 2108569058235332325 997 2123446783240884297 998 2138414396004879861 999 2153472348639159230 1000 2168621095072936105