0 1 1 16 2 90 3 328 4 886 5 2016 6 3986 7 7208 8 12050 9 19096 10 28802 11 41936 12 59030 13 81048 14 108586 15 142816 16 184386 17 234688 18 294410 19 365176 20 447702 21 543856 22 654370 23 781368 24 925586 25 1089416 26 1273586 27 1480768 28 1711670 29 1969256 30 2254202 31 2569776 32 2916610 33 3298288 34 3715386 35 4171816 36 4668086 37 5208448 38 5793330 39 6427336 40 7110802 41 7848696 42 8641250 43 9493808 44 10406486 45 11385016 46 12429386 47 13545728 48 14733890 49 16000416 50 17345002 51 18774616 52 20288790 53 21894928 54 23592386 55 25389016 56 27283986 57 29285608 58 31392850 59 33614496 60 35949302 61 38406536 62 40984730 63 43693648 64 46531586 65 49508816 66 52623386 67 55886088 68 59294710 69 62860576 70 66581202 71 70468456 72 74519570 73 78746968 74 83147586 75 87734416 76 92504086 77 97470168 78 102628970 79 107994656 80 113563202 81 119349376 82 125348810 83 131576888 84 138028886 85 144720816 86 151647586 87 158825848 88 166250130 89 173937736 90 181882802 91 190103296 92 198592950 93 207370408 94 216428986 95 225788016 96 235440386 97 245406128 98 255677690 99 266275816 100 277192502 101 288449216 102 300037490 103 311979528 104 324266386 105 336921016 106 349933986 107 363329008 108 377096150 109 391259896 110 405809802 111 420771136 112 436132930 113 451921248 114 468124586 115 484769816 116 501844886 117 519377488 118 537355010 119 555805976 120 574717202 121 594118056 122 613994770 123 634377568 124 655252086 125 676649416 126 698554586 127 720999568 128 743968770 129 767495056 130 791562202 131 816203976 132 841403510 133 867195488 134 893562386 135 920539816 136 948109586 137 976308248 138 1005116930 139 1034573136 140 1064657302 141 1095407896 142 1126804650 143 1158887008 144 1191633986 145 1225086016 146 1259221386 147 1294081528 148 1329643990 149 1365951216 150 1402980002 151 1440773816 152 1479308690 153 1518629128 154 1558710386 155 1599598016 156 1641266486 157 1683762408 158 1727059450 159 1771205296 160 1816172802 161 1862010736 162 1908691130 163 1956263848 164 2004700086 165 2054050816 166 2104286386 167 2155458888 168 2207537810 169 2260576376 170 2314543202 171 2369492656 172 2425392470 173 2482298168 174 2540176586 175 2599084416 176 2658987586 177 2719943968 178 2781918570 179 2844970456 180 2909063702 181 2974258576 182 3040518210 183 3107904088 184 3176378386 185 3246003816 186 3316741586 187 3388655648 188 3461706230 189 3535958536 190 3611371802 191 3688012496 192 3765838850 193 3844918608 194 3925208986 195 4006779016 196 4089584886 197 4173696928 198 4259070290 199 4345776616 200 4433770002 201 4523123416 202 4613789890 203 4705843728 204 4799236886 205 4894045016 206 4990218986 207 5087835808 208 5186845250 209 5287325696 210 5389225802 211 5492625336 212 5597471830 213 5703846448 214 5811695586 215 5921101816 216 6032010386 217 6144505288 218 6258530610 219 6374171776 220 6491371702 221 6610217256 222 6730650170 223 6852758768 224 6976483586 225 7101914416 226 7228990586 227 7357803368 228 7488290870 229 7620545856 230 7754505202 231 7890263176 232 8027755410 233 8167077688 234 8308164386 235 8451112816 236 8595856086 237 8742493048 238 8890955530 239 9041343936 240 9193588802 241 9347792096 242 9503883050 243 9661965208 244 9821966486 245 9983992016 246 10147968386 247 10314002328 248 10482019090 249 10652127016 250 10824250002 251 10998498016 252 11174793590 253 11353248328 254 11533783386 255 11716512016 256 11901353986 257 12088424208 258 12277641050 259 12469121096 260 12662781302 261 12858739936 262 13056912530 263 13257419048 264 13460173586 265 13665297816 266 13872704386 267 14082516688 268 14294645910 269 14509217176 270 14726140202 271 14945541856 272 15167330370 273 15391634368 274 15618360586 275 15847639416 276 16079376086 277 16313702768 278 16550523170 279 16789971256 280 17031949202 281 17276592776 282 17523802610 283 17773716288 284 18026232886 285 18281491816 286 18539390586 287 18800070448 288 19063427330 289 19329604336 290 19598495802 291 19870246696 292 20144749750 293 20422151808 294 20702343986 295 20985475016 296 21271434386 297 21560372728 298 21852177890 299 22147002416 300 22444732502 301 22745522616 302 23049257290 303 23356092928 304 23665912386 305 23978874016 306 24294858986 307 24614027608 308 24936259350 309 25261716496 310 25590276802 311 25922104536 312 26257075730 313 26595356648 314 26936821586 315 27281638816 316 27629680886 317 27981118088 318 28335821210 319 28693962576 320 29055411202 321 29420341456 322 29788620570 323 30160424968 324 30535620086 325 30914384416 326 31296581586 327 31682392168 328 32071677970 329 32464621656 330 32861083202 331 33261247376 332 33664972310 333 34072444888 334 34483521386 335 34898390816 336 35316907586 337 35739262848 338 36165309130 339 36595239736 340 37028905302 341 37466501296 342 37907876450 343 38353228408 344 38802403986 345 39255603016 346 39712670386 347 40173808128 348 40638859190 349 41108027816 350 41581155002 351 42058447216 352 42539743490 353 43025252528 354 43514811386 355 44008631016 356 44506546486 357 45008771008 358 45515137650 359 46025861896 360 46540774802 361 47060094136 362 47583648930 363 48111659248 364 48643952086 365 49180749816 366 49721877386 367 50267559488 368 50817619010 369 51372282976 370 51931372202 371 52495116056 372 53063333270 373 53636255568 374 54213699586 375 54795899416 376 55382669586 377 55974246568 378 56570442770 379 57171497056 380 57777219702 381 58387851976 382 59003202010 383 59623513488 384 60248592386 385 60878684816 386 61513594586 387 62153570248 388 62798413430 389 63448375136 390 64103254802 391 64763305896 392 65428325650 393 66098570008 394 66773833986 395 67454376016 396 68139988886 397 68830933528 398 69527000490 399 70228453216 400 70935080002 401 71647146816 402 72364439690 403 73087227128 404 73815292886 405 74548908016 406 75287853986 407 76032404408 408 76782338450 409 77537932296 410 78298962802 411 79065708736 412 79837944630 413 80615951848 414 81399502586 415 82188880816 416 82983856386 417 83784715888 418 84591226810 419 85403678376 420 86221835702 421 87045990656 422 87875905970 423 88711876168 424 89553661586 425 90401559416 426 91255327586 427 92115265968 428 92981130070 429 93853222456 430 94731296202 431 95615656576 432 96506054210 433 97402797088 434 98305633386 435 99214873816 436 100130264086 437 101052117648 438 101980177730 439 102914760536 440 103855606802 441 104803035496 442 105756784850 443 106717176608 444 107683946486 445 108657419016 446 109637327386 447 110623998928 448 111617164290 449 112617153616 450 113623695002 451 114637121416 452 115657158390 453 116684141728 454 117717794386 455 118758455016 456 119805843986 457 120860302808 458 121921549250 459 122989927696 460 124065153302 461 125147573336 462 126236900330 463 127333484448 464 128437035586 465 129547906816 466 130665805386 467 131791087288 468 132923457110 469 134063273776 470 135210239202 471 136364715256 472 137526401170 473 138695661768 474 139872193586 475 141056364416 476 142247868086 477 143447075368 478 144653677370 479 145868047856 480 147089875202 481 148319536176 482 149556716410 483 150801795688 484 152054456886 485 153315082816 486 154583353586 487 155859655048 488 157143664530 489 158435770936 490 159735648802 491 161043690096 492 162359566550 493 163683673208 494 165015678986 495 166355982016 496 167704248386 497 169060879328 498 170425538090 499 171798629016 500 173179812502 501 174569496016 502 175967337090 503 177373746328 504 178788378386 505 180211647016 506 181643203986 507 183083466208 508 184532082550 509 185989473096 510 187455283802 511 188929937936 512 190413078530 513 191905132048 514 193405738586 515 194915327816 516 196433536886 517 197960798688 518 199496747410 519 201041819176 520 202595645202 521 204158664856 522 205730506370 523 207311612368 524 208901608086 525 210500939416 526 212109228586 527 213726924768 528 215353647170 529 216989848256 530 218635144202 531 220289990776 532 221954001110 533 223627634288 534 225310500386 535 227003061816 536 228704925586 537 230416557448 538 232137561330 539 233868406336 540 235608693302 541 237358894696 542 239118608250 543 240888309808 544 242667593986 545 244456940016 546 246255939386 547 248065074728 548 249883934390 549 251713004416 550 253551870002 551 255401020616 552 257260038290 553 259129415928 554 261008732386 555 262898484016 556 264798246486 557 266708519608 558 268628875850 559 270559818496 560 272500916802 561 274452677536 562 276414666730 563 278387394648 564 280370424086 565 282364268816 566 284368488386 567 286383600088 568 288409160210 569 290445689576 570 292492741202 571 294550839456 572 296619534070 573 298699352968 574 300789842586 575 302891534416 576 305003971586 577 307127689168 578 309262226970 579 311408123656 580 313564915702 581 315733145376 582 317912345810 583 320103062888 584 322304826386 585 324518185816 586 326742667586 587 328978824848 588 331226180630 589 333485291736 590 335755677802 591 338037899296 592 340331472450 593 342636961408 594 344953878986 595 347282793016 596 349623212886 597 351975710128 598 354339790690 599 356716029816 600 359103930002 601 361504070216 602 363915949490 603 366340150528 604 368776168886 605 371224591016 606 373684908986 607 376157713008 608 378642491650 609 381139838896 610 383649239802 611 386171292136 612 388705477430 613 391252397248 614 393811529586 615 396383479816 616 398967722386 617 401564866488 618 404174383010 619 406796884976 620 409431839702 621 412079864056 622 414740421770 623 417414133568 624 420100459586 625 422800024416 626 425512284586 627 428237868568 628 430976229270 629 433727999056 630 436492627202 631 439270749976 632 442061813010 633 444866456488 634 447684122386 635 450515454816 636 453359892086 637 456218082248 638 459089459930 639 461974677136 640 464873164802 641 467785578896 642 470711346650 643 473651128008 644 476604346486 645 479571666016 646 482552506386 647 485547535528 648 488556169490 649 491579080216 650 494615680002 651 497666644816 652 500731383190 653 503810575128 654 506903625386 655 510011218016 656 513132753986 657 516268921408 658 519419117450 659 522584034296 660 525763065302 661 528956906736 662 532164948130 663 535387889848 664 538625117586 665 541877335816 666 545143926386 667 548425597888 668 551721728310 669 555033030376 670 558358878202 671 561699988656 672 565055731970 673 568426829168 674 571812646586 675 575213909416 676 578629980086 677 582061587968 678 585508091570 679 588970224456 680 592447341202 681 595940179576 682 599448090210 683 602971815088 684 606510700886 685 610065493816 686 613635536586 687 617221579648 688 620822961730 689 624440437536 690 628073341802 691 631722433496 692 635387043350 693 639067934608 694 642764433986 695 646477309016 696 650205882386 697 653950925928 698 657711758290 699 661489155616 700 665282432502 701 669092369416 702 672918276890 703 676760939728 704 680619664386 705 684495240016 706 688386968986 707 692295644808 708 696220565750 709 700162529696 710 704120830802 711 708096271336 712 712088141330 713 716097247448 714 720122875586 715 724165836816 716 728225412886 717 732302419288 718 736396133610 719 740507375776 720 744635419202 721 748781088256 722 752943652170 723 757123939768 724 761321216086 725 765536314416 726 769768495586 727 774018597368 728 778285876370 729 782571174856 730 786873745202 731 791194434176 732 795532489910 733 799888763688 734 804262499386 735 808654552816 736 813064163586 737 817492192048 738 821937873530 739 826402072936 740 830884021302 741 835384588096 742 839903000050 743 844440131208 744 848995203986 745 853569097016 746 858161028386 747 862771881328 748 867400869590 749 872048881016 750 876715125002 751 881400494016 752 886104193090 753 890827119328 754 895568473386 755 900329157016 756 905108366486 757 909907008208 758 914724274050 759 919561075096 760 924416598802 761 929291760936 762 934185744530 763 939099470048 764 944032116086 765 948984607816 766 953956119386 767 958947580688 768 963958161410 769 968988796176 770 974038650202 771 979108662856 772 984197994870 773 989307590368 774 994436605586 775 999585989416 776 1004754893586 777 1009944271768 778 1015153271170 779 1020382850256 780 1025632151702 781 1030902138776 782 1036191949610 783 1041502552288 784 1046833080386 785 1052184506816 786 1057555960586 787 1062948419448 788 1068361007830 789 1073794708336 790 1079248640802 791 1084723792696 792 1090219279250 793 1095736092808 794 1101273343986 795 1106832030016 796 1112411256886 797 1118012026728 798 1123633440890 799 1129276506416 800 1134940320002 801 1140625893616 802 1146332319290 803 1152060613928 804 1157809864886 805 1163581094016 806 1169373383986 807 1175187761608 808 1181023304850 809 1186881045496 810 1192760056802 811 1198661375536 812 1204584070230 813 1210529182648 814 1216495776586 815 1222484898816 816 1228495608386 817 1234528957088 818 1240583999210 819 1246661791576 820 1252761383702 821 1258883837456 822 1265028197570 823 1271195530968 824 1277384877586 825 1283597309416 826 1289831861586 827 1296089611168 828 1302369588470 829 1308672875656 830 1314998498202 831 1321347543376 832 1327719031810 833 1334114055888 834 1340531631386 835 1346972855816 836 1353436740086 837 1359924386848 838 1366434802130 839 1372969093736 840 1379526262802 841 1386107422296 842 1392711568450 843 1399339819408 844 1405991166486 845 1412666733016 846 1419365505386 847 1426088612128 848 1432835034690 849 1439605906816 850 1446400205002 851 1453219068216 852 1460061467990 853 1466928548528 854 1473819276386 855 1480734801016 856 1487674083986 857 1494638280008 858 1501626345650 859 1508639440896 860 1515676517302 861 1522738740136 862 1529825055930 863 1536936635248 864 1544072419586 865 1551233584816 866 1558419067386 867 1565630048488 868 1572865459510 869 1580126486976 870 1587412057202 871 1594723362056 872 1602059322770 873 1609421136568 874 1616807719586 875 1624220274416 876 1631657712086 877 1639121240568 878 1646609765770 879 1654124501056 880 1661664347202 881 1669230522976 882 1676821924010 883 1684439774488 884 1692082964886 885 1699752724816 886 1707447939586 887 1715169844248 888 1722917318930 889 1730691604136 890 1738491574802 891 1746318476896 892 1754171180150 893 1762050936008 894 1769956608986 895 1777889456016 896 1785848336386 897 1793834512528 898 1801846838490 899 1809886582216 900 1817952592502 901 1826046142816 902 1834166076690 903 1842313673128 904 1850487770386 905 1858689653016 906 1866918153986 907 1875174563408 908 1883457708950 909 1891768886296 910 1900106917802 911 1908473104736 912 1916866264130 913 1925287702848 914 1933736232586 915 1942213165816 916 1950717308886 917 1959249979888 918 1967809979810 919 1976398632376 920 1985014733202 921 1993659611656 922 2002332057970 923 2011033407168 924 2019762444086 925 2028520509416 926 2037306382586 927 2046121409968 928 2054964365570 929 2063836601456 930 2072736886202 931 2081666577576 932 2090624438710 933 2099611833088 934 2108627518386 935 2117672863816 936 2126746621586 937 2135850166648 938 2144982245730 939 2154144239536 940 2163334889302 941 2172555581496 942 2181805051850 943 2191084692608 944 2200393233986 945 2209732074016 946 2219099937386 947 2228498227928 948 2237925664790 949 2247383657616 950 2256870920002 951 2266388867416 952 2275936207890 953 2285514362728 954 2295122034386 955 2304760650016 956 2314428906486 957 2324128236808 958 2333857332250 959 2343617631696 960 2353407820802 961 2363229344336 962 2373080882330 963 2382963885448 964 2392877028086 965 2402821766816 966 2412796770386 967 2422803501288 968 2432840622610 969 2442909602776 970 2453009099202 971 2463140586256 972 2473302715670 973 2483496967768 974 2493721988586 975 2503979264416 976 2514267435586 977 2524587994368 978 2534939575370 979 2545323676856 980 2555738927702 981 2566186832176 982 2576666013410 983 2587177981688 984 2597721354386 985 2608297647816 986 2618905473586 987 2629546354048 988 2640218895030 989 2650924624936 990 2661662143802 991 2672432986096 992 2683235746050 993 2694071964208 994 2704940228986 995 2715842087016 996 2726776120886 997 2737743883328 998 2748743951090 999 2759777883016 1000 2770844250002