0 1 1 96 2 944 3 4057 4 11811 5 27446 6 55066 7 99639 8 166997 9 263836 10 397716 11 577061 12 811159 13 1110162 14 1485086 15 1947811 16 2511081 17 3188504 18 3994552 19 4944561 20 6054731 21 7342126 22 8824674 23 10521167 24 12451261 25 14635476 26 17095196 27 19852669 28 22931007 29 26354186 30 30147046 31 34335291 32 38945489 33 44005072 34 49542336 35 55586441 36 62167411 37 69316134 38 77064362 39 85444711 40 94490661 41 104236556 42 114717604 43 125969877 44 138030311 45 150936706 46 164727726 47 179442899 48 195122617 49 211808136 50 229541576 51 248365921 52 268325019 53 289463582 54 311827186 55 335462271 56 360416141 57 386736964 58 414473772 59 443676461 60 474395791 61 506683386 62 540591734 63 576174187 64 613484961 65 652579136 66 693512656 67 736342329 68 781125827 69 827921686 70 876789306 71 927788951 72 980981749 73 1036429692 74 1094195636 75 1154343301 76 1216937271 77 1282042994 78 1349726782 79 1420055811 80 1493098121 81 1568922616 82 1647599064 83 1729198097 84 1813791211 85 1901450766 86 1992249986 87 2086262959 88 2183564637 89 2284230836 90 2388338236 91 2495964381 92 2607187679 93 2722087402 94 2840743686 95 2963237531 96 3089650801 97 3220066224 98 3354567392 99 3493238761 100 3636165651 101 3783434246 102 3935131594 103 4091345607 104 4252165061 105 4417679596 106 4587979716 107 4763156789 108 4943303047 109 5128511586 110 5318876366 111 5514492211 112 5715454809 113 5921860712 114 6133807336 115 6351392961 116 6574716731 117 6803878654 118 7038979602 119 7280121311 120 7527406381 121 7780938276 122 8040821324 123 8307160717 124 8580062511 125 8859633626 126 9145981846 127 9439215819 128 9739445057 129 10046779936 130 10361331696 131 10683212441 132 11012535139 133 11349413622 134 11693962586 135 12046297591 136 12406535061 137 12774792284 138 13151187412 139 13535839461 140 13928868311 141 14330394706 142 14740540254 143 15159427427 144 15587179561 145 16023920856 146 16469776376 147 16924872049 148 17389334667 149 17863291886 150 18346872226 151 18840205071 152 19343420669 153 19856650132 154 20380025436 155 20913679421 156 21457745791 157 22012359114 158 22577654822 159 23153769211 160 23740839441 161 24339003536 162 24948400384 163 25569169737 164 26201452211 165 26845389286 166 27501123306 167 28168797479 168 28848555877 169 29540543436 170 30244905956 171 30961790101 172 31691343399 173 32433714242 174 33189051886 175 33957506451 176 34739228921 177 35534371144 178 36343085832 179 37165526561 180 38001847771 181 38852204766 182 39716753714 183 40595651647 184 41489056461 185 42397126916 186 43320022636 187 44257904109 188 45210932687 189 46179270586 190 47163080886 191 48162527531 192 49177775329 193 50208989952 194 51256337936 195 52319986681 196 53400104451 197 54496860374 198 55610424442 199 56740967511 200 57888661301 201 59053678396 202 60236192244 203 61436377157 204 62654408311 205 63890461746 206 65144714366 207 66417343939 208 67708529097 209 69018449336 210 70347285016 211 71695217361 212 73062428459 213 74449101262 214 75855419586 215 77281568111 216 78727732381 217 80194098804 218 81680854652 219 83188188061 220 84716288031 221 86265344426 222 87835547974 223 89427090267 224 91040163761 225 92674961776 226 94331678496 227 96010508969 228 97711649107 229 99435295686 230 101181646346 231 102950899591 232 104743254789 233 106558912172 234 108398072836 235 110260938741 236 112147712711 237 114058598434 238 115993800462 239 117953524211 240 119937975961 241 121947362856 242 123981892904 243 126041774977 244 128127218811 245 130238435006 246 132375635026 247 134539031199 248 136728836717 249 138945265636 250 141188532876 251 143458854221 252 145756446319 253 148081526682 254 150434313686 255 152815026571 256 155223885441 257 157661111264 258 160126925872 259 162621551961 260 165145213091 261 167698133686 262 170280539034 263 172892655287 264 175534709461 265 178206929436 266 180909543956 267 183642782629 268 186406875927 269 189202055186 270 192028552606 271 194886601251 272 197776435049 273 200698288792 274 203652398136 275 206638999601 276 209658330571 277 212710629294 278 215796134882 279 218915087311 280 222067727421 281 225254296916 282 228475038364 283 231730195197 284 235020011711 285 238344733066 286 241704605286 287 245099875259 288 248530790737 289 251997600336 290 255500553536 291 259039900681 292 262615892979 293 266228782502 294 269878822186 295 273566265831 296 277291368101 297 281054384524 298 284855571492 299 288695186261 300 292573486951 301 296490732546 302 300447182894 303 304443098707 304 308478741561 305 312554373896 306 316670259016 307 320826661089 308 325023845147 309 329262077086 310 333541623666 311 337862752511 312 342225732109 313 346630831812 314 351078321836 315 355568473261 316 360101558031 317 364677848954 318 369297619702 319 373961144811 320 378668699681 321 383420560576 322 388217004624 323 393058309817 324 397944755011 325 402876619926 326 407854185146 327 412877732119 328 417947543157 329 423063901436 330 428227090996 331 433437396741 332 438695104439 333 444000500722 334 449353873086 335 454755509891 336 460205700361 337 465704734584 338 471252903512 339 476850498961 340 482497813611 341 488195141006 342 493942775554 343 499741012527 344 505590148061 345 511490479156 346 517442303676 347 523445920349 348 529501628767 349 535609729386 350 541770523526 351 547984313371 352 554251401969 353 560572093232 354 566946691936 355 573375503721 356 579858835091 357 586396993414 358 592990286922 359 599639024711 360 606343516741 361 613104073836 362 619921007684 363 626794630837 364 633725256711 365 640713199586 366 647758774606 367 654862297779 368 662024085977 369 669244456936 370 676523729256 371 683862222401 372 691260256699 373 698718153342 374 706236234386 375 713814822751 376 721454242221 377 729154817444 378 736916873932 379 744740738061 380 752626737071 381 760575199066 382 768586453014 383 776660828747 384 784798656961 385 793000269216 386 801265997936 387 809596176409 388 817991138787 389 826451220086 390 834976756186 391 843568083831 392 852225540629 393 860949465052 394 869740196436 395 878598074981 396 887523441751 397 896516638674 398 905578008542 399 914707895011 400 923906642601 401 933174596696 402 942512103544 403 951919510257 404 961397164811 405 970945416046 406 980564613666 407 990255108239 408 1000017251197 409 1009851394836 410 1019757892316 411 1029737097661 412 1039789365759 413 1049915052362 414 1060114514086 415 1070388108411 416 1080736193681 417 1091159129104 418 1101657274752 419 1112230991561 420 1122880641331 421 1133606586726 422 1144409191274 423 1155288819367 424 1166245836261 425 1177280608076 426 1188393501796 427 1199584885269 428 1210855127207 429 1222204597186 430 1233633665646 431 1245142703891 432 1256732084089 433 1268402179272 434 1280153363336 435 1291986011041 436 1303900498011 437 1315897200734 438 1327976496562 439 1340138763711 440 1352384381261 441 1364713729156 442 1377127188204 443 1389625140077 444 1402207967311 445 1414876053306 446 1427629782326 447 1440469539499 448 1453395710817 449 1466408683136 450 1479508844176 451 1492696582521 452 1505972287619 453 1519336349782 454 1532789160186 455 1546331110871 456 1559962594741 457 1573684005564 458 1587495737972 459 1601398187461 460 1615391750391 461 1629476823986 462 1643653806334 463 1657923096387 464 1672285093961 465 1686740199736 466 1701288815256 467 1715931342929 468 1730668186027 469 1745499748686 470 1760426435906 471 1775448653551 472 1790566808349 473 1805781307892 474 1821092560636 475 1836500975901 476 1852006963871 477 1867610935594 478 1883313302982 479 1899114478811 480 1915014876721 481 1931014911216 482 1947114997664 483 1963315552297 484 1979616992211 485 1996019735366 486 2012524200586 487 2029130807559 488 2045839976837 489 2062652129836 490 2079567688836 491 2096587076981 492 2113710718279 493 2130939037602 494 2148272460686 495 2165711414131 496 2183256325401 497 2200907622824 498 2218665735592 499 2236531093761 500 2254504128251 501 2272585270846 502 2290774954194 503 2309073611807 504 2327481678061 505 2345999588196 506 2364627778316 507 2383366685389 508 2402216747247 509 2421178402586 510 2440252090966 511 2459438252811 512 2478737329409 513 2498149762912 514 2517675996336 515 2537316473561 516 2557071639331 517 2576941939254 518 2596927819802 519 2617029728311 520 2637248112981 521 2657583422876 522 2678036107924 523 2698606618917 524 2719295407511 525 2740102926226 526 2761029628446 527 2782075968419 528 2803242401257 529 2824529382936 530 2845937370296 531 2867466821041 532 2889118193739 533 2910891947822 534 2932788543586 535 2954808442191 536 2976952105661 537 2999219996884 538 3021612579612 539 3044130318461 540 3066773678911 541 3089543127306 542 3112439130854 543 3135462157627 544 3158612676561 545 3181891157456 546 3205298070976 547 3228833888649 548 3252499082867 549 3276294126886 550 3300219494826 551 3324275661671 552 3348463103269 553 3372782296332 554 3397233718436 555 3421817848021 556 3446535164391 557 3471386147714 558 3496371279022 559 3521491040211 560 3546745914041 561 3572136384136 562 3597662934984 563 3623326051937 564 3649126221211 565 3675063929886 566 3701139665906 567 3727353918079 568 3753707176077 569 3780199930436 570 3806832672556 571 3833605894701 572 3860520089999 573 3887575752442 574 3914773376886 575 3942113459051 576 3969596495521 577 3997222983744 578 4024993422032 579 4052908309561 580 4080968146371 581 4109173433366 582 4137524672314 583 4166022365847 584 4194667017461 585 4223459131516 586 4252399213236 587 4281487768709 588 4310725304887 589 4340112329586 590 4369649351486 591 4399336880131 592 4429175425929 593 4459165500152 594 4489307614936 595 4519602283281 596 4550050019051 597 4580651336974 598 4611406752642 599 4642316782511 600 4673381943901 601 4704602754996 602 4735979734844 603 4767513403357 604 4799204281311 605 4831052890346 606 4863059752966 607 4895225392539 608 4927550333297 609 4960035100336 610 4992680219616 611 5025486217961 612 5058453623059 613 5091582963462 614 5124874768586 615 5158329568711 616 5191947894981 617 5225730279404 618 5259677254852 619 5293789355061 620 5328067114631 621 5362511069026 622 5397121754574 623 5431899708467 624 5466845468761 625 5501959574376 626 5537242565096 627 5572694981569 628 5608317365307 629 5644110258686 630 5680074204946 631 5716209748191 632 5752517433389 633 5788997806372 634 5825651413836 635 5862478803341 636 5899480523311 637 5936657123034 638 5974009152662 639 6011537163211 640 6049241706561 641 6087123335456 642 6125182603504 643 6163420065177 644 6201836275811 645 6240431791606 646 6279207169626 647 6318162967799 648 6357299744917 649 6396618060636 650 6436118475476 651 6475801550821 652 6515667848919 653 6555717932882 654 6595952366686 655 6636371715171 656 6676976544041 657 6717767419864 658 6758744910072 659 6799909582961 660 6841262007691 661 6882802754286 662 6924532393634 663 6966451497487 664 7008560638461 665 7050860390036 666 7093351326556 667 7136034023229 668 7178909056127 669 7221977002186 670 7265238439206 671 7308693945851 672 7352344101649 673 7396189486992 674 7440230683136 675 7484468272201 676 7528902837171 677 7573534961894 678 7618365231082 679 7663394230311 680 7708622546021 681 7754050765516 682 7799679476964 683 7845509269397 684 7891540732711 685 7937774457666 686 7984211035886 687 8030851059859 688 8077695122937 689 8124743819336 690 8171997744136 691 8219457493281 692 8267123663579 693 8314996852702 694 8363077659186 695 8411366682431 696 8459864522701 697 8508571781124 698 8557489059692 699 8606616961261 700 8655956089551 701 8705507049146 702 8755270445494 703 8805246884907 704 8855436974561 705 8905841322496 706 8956460537616 707 9007295229689 708 9058346009347 709 9109613488086 710 9161098278266 711 9212800993111 712 9264722246709 713 9316862654012 714 9369222830836 715 9421803393861 716 9474604960631 717 9527628149554 718 9580873579902 719 9634341871811 720 9688033646281 721 9741949525176 722 9796090131224 723 9850456088017 724 9905048020011 725 9959866552526 726 10014912311746 727 10070185924719 728 10125688019357 729 10181419224436 730 10237380169596 731 10293571485341 732 10349993803039 733 10406647754922 734 10463533974086 735 10520653094491 736 10578005750961 737 10635592579184 738 10693414215712 739 10751471297961 740 10809764464211 741 10868294353606 742 10927061606154 743 10986066862727 744 11045310765061 745 11104793955756 746 11164517078276 747 11224480776949 748 11284685696967 749 11345132484386 750 11405821786126 751 11466754249971 752 11527930524569 753 11589351259432 754 11651017104936 755 11712928712321 756 11775086733691 757 11837491822014 758 11900144631122 759 11963045815711 760 12026196031341 761 12089595934436 762 12153246182284 763 12217147433037 764 12281300345711 765 12345705580186 766 12410363797206 767 12475275658379 768 12540441826177 769 12605862963936 770 12671539735856 771 12737472807001 772 12803662843299 773 12870110511542 774 12936816479386 775 13003781415351 776 13071005988821 777 13138490870044 778 13206236730132 779 13274244241061 780 13342514075671 781 13411046907666 782 13479843411614 783 13548904262947 784 13618230137961 785 13687821713816 786 13757679668536 787 13827804681009 788 13898197430987 789 13968858599086 790 14039788866786 791 14110988916431 792 14182459431229 793 14254201095252 794 14326214593436 795 14398500611581 796 14471059836351 797 14543892955274 798 14617000656742 799 14690383630011 800 14764042565201 801 14837978153296 802 14912191086144 803 14986682056457 804 15061451757811 805 15136500884646 806 15211830132266 807 15287440196839 808 15363331775397 809 15439505565836 810 15515962266916 811 15592702578261 812 15669727200359 813 15747036834562 814 15824632183086 815 15902513949011 816 15980682836281 817 16059139549704 818 16137884794952 819 16216919278561 820 16296243707931 821 16375858791326 822 16455765237874 823 16535963757567 824 16616455061261 825 16697239860676 826 16778318868396 827 16859692797869 828 16941362363407 829 17023328280186 830 17105591264246 831 17188152032491 832 17271011302689 833 17354169793472 834 17437628224336 835 17521387315641 836 17605447788611 837 17689810365334 838 17774475768762 839 17859444722711 840 17944717951861 841 18030296181756 842 18116180138804 843 18202370550277 844 18288868144311 845 18375673649906 846 18462787796926 847 18550211316099 848 18637944939017 849 18725989398136 850 18814345426776 851 18903013759121 852 18991995130219 853 19081290275982 854 19170899933186 855 19260824839471 856 19351065733341 857 19441623354164 858 19532498442172 859 19623691738461 860 19715203984991 861 19807035924586 862 19899188300934 863 19991661858587 864 20084457342961 865 20177575500336 866 20271017077856 867 20364782823529 868 20458873486227 869 20553289815686 870 20648032562506 871 20743102478151 872 20838500314949 873 20934226826092 874 21030282765636 875 21126668888501 876 21223385950471 877 21320434708194 878 21417815919182 879 21515530341811 880 21613578735321 881 21711961859816 882 21810680476264 883 21909735346497 884 22009127233211 885 22108856899966 886 22208925111186 887 22309332632159 888 22410080229037 889 22511168668836 890 22612598719436 891 22714371149581 892 22816486728879 893 22918946227802 894 23021750417686 895 23124900070731 896 23228395960001 897 23332238859424 898 23436429543792 899 23540968788761 900 23645857370851 901 23751096067446 902 23856685656794 903 23962626918007 904 24068920631061 905 24175567576796 906 24282568536916 907 24389924293989 908 24497635631447 909 24605703333586 910 24714128185566 911 24822910973411 912 24932052484009 913 25041553505112 914 25151414825336 915 25261637234161 916 25372221521931 917 25483168479854 918 25594478900002 919 25706153575311 920 25818193299581 921 25930598867476 922 26043371074524 923 26156510717117 924 26270018592511 925 26383895498826 926 26498142235046 927 26612759601019 928 26727748397457 929 26843109425936 930 26958843488896 931 27074951389641 932 27191433932339 933 27308291922022 934 27425526164586 935 27543137466791 936 27661126636261 937 27779494481484 938 27898241811812 939 28017369437461 940 28136878169511 941 28256768819906 942 28377042201454 943 28497699127827 944 28618740413561 945 28740166874056 946 28861979325576 947 28984178585249 948 29106765471067 949 29229740801886 950 29353105397426 951 29476860078271 952 29601005665869 953 29725542982532 954 29850472851436 955 29975796096621 956 30101513542991 957 30227626016314 958 30354134343222 959 30481039351211 960 30608341868641 961 30736042724736 962 30864142749584 963 30992642774137 964 31121543630211 965 31250846150486 966 31380551168506 967 31510659518679 968 31641172036277 969 31772089557436 970 31903412919156 971 32035142959301 972 32167280516599 973 32299826430642 974 32432781541886 975 32566146691651 976 32699922722121 977 32834110476344 978 32968710798232 979 33103724532561 980 33239152524971 981 33374995621966 982 33511254670914 983 33647930520047 984 33785024018461 985 33922536016116 986 34060467363836 987 34198818913309 988 34337591517087 989 34476786028586 990 34616403302086 991 34756444192731 992 34896909556529 993 35037800250352 994 35179117131936 995 35320861059881 996 35463032893651 997 35605633493574 998 35748663720842 999 35892124437511 1000 36036016506501