0 1 1 8 2 36 3 120 4 330 5 792 6 1716 7 3432 8 6434 9 11432 10 19412 11 31704 12 50058 13 76728 14 114564 15 167112 16 238722 17 334664 18 461252 19 625976 20 837642 21 1106520 22 1444500 23 1865256 24 2384418 25 3019752 26 3791348 27 4721816 28 5836490 29 7163640 30 8734692 31 10584456 32 12751362 33 15277704 34 18209892 35 21598712 36 25499594 37 29972888 38 35084148 39 40904424 40 47510562 41 54985512 42 63418644 43 72906072 44 83550986 45 95463992 46 108763460 47 123575880 48 140036226 49 158288328 50 178485252 51 200789688 52 225374346 53 252422360 54 282127700 55 314695592 56 350342946 57 389298792 58 431804724 59 478115352 60 528498762 61 583236984 62 642626468 63 706978568 64 776620034 65 851893512 66 933158052 67 1020789624 68 1115181642 69 1216745496 70 1325911092 71 1443127400 72 1568863010 73 1703606696 74 1847867988 75 2002177752 76 2167088778 77 2343176376 78 2531038980 79 2731298760 80 2944602242 81 3171620936 82 3413051972 83 3669618744 84 3942071562 85 4231188312 86 4537775124 87 4862667048 88 5206728738 89 5570855144 90 5955972212 91 6363037592 92 6793041354 93 7247006712 94 7725990756 95 8231085192 96 8763417090 97 9324149640 98 9914482916 99 10535654648 100 11188941002 101 11875657368 102 12597159156 103 13354842600 104 14150145570 105 14984548392 106 15859574676 107 16776792152 108 17737813514 109 18744297272 110 19797948612 111 20900520264 112 22053813378 113 23259678408 114 24520016004 115 25836777912 116 27211967882 117 28647642584 118 30145912532 119 31708943016 120 33338955042 121 35038226280 122 36809092020 123 38653946136 124 40575242058 125 42575493752 126 44657276708 127 46823228936 128 49076051970 129 51418511880 130 53853440292 131 56383735416 132 59012363082 133 61742357784 134 64576823732 135 67518935912 136 70571941154 137 73739159208 138 77023983828 139 80429883864 140 83960404362 141 87619167672 142 91409874564 143 95336305352 144 99402321026 145 103611864392 146 107968961220 147 112477721400 148 117142340106 149 121967098968 150 126956367252 151 132114603048 152 137446354466 153 142956260840 154 148649053940 155 154529559192 156 160602696906 157 166873483512 158 173347032804 159 180028557192 160 186923368962 161 194036881544 162 201374610788 163 208942176248 164 216745302474 165 224789820312 166 233081668212 167 241626893544 168 250431653922 169 259502218536 170 268844969492 171 278466403160 172 288373131530 173 298571883576 174 309069506628 175 319872967752 176 330989355138 177 342425879496 178 354189875460 179 366288803000 180 378730248842 181 391521927896 182 404671684692 183 418187494824 184 432077466402 185 446349841512 186 461012997684 187 476075449368 188 491545849418 189 507432990584 190 523745807012 191 540493375752 192 557684918274 193 575329801992 194 593437541796 195 612017801592 196 631080395850 197 650635291160 198 670692607796 199 691262621288 200 712355764002 201 733982626728 202 756153960276 203 778880677080 204 802173852810 205 826044727992 206 850504709636 207 875565372872 208 901238462594 209 927535895112 210 954469759812 211 982052320824 212 1010296018698 213 1039213472088 214 1068817479444 215 1099121020712 216 1130137259042 217 1161879542504 218 1194361405812 219 1227596572056 220 1261598954442 221 1296382658040 222 1331961981540 223 1368351419016 224 1405565661698 225 1443619599752 226 1482528324068 227 1522307128056 228 1562971509450 229 1604537172120 230 1647020027892 231 1690436198376 232 1734802016802 233 1780134029864 234 1826448999572 235 1873763905112 236 1922095944714 237 1971462537528 238 2021881325508 239 2073370175304 240 2125947180162 241 2179630661832 242 2234439172484 243 2290391496632 244 2347506653066 245 2405803896792 246 2465302720980 247 2526022858920 248 2587984285986 249 2651207221608 250 2715712131252 251 2781519728408 252 2848650976586 253 2917127091320 254 2986969542180 255 3058200054792 256 3130840612866 257 3204913460232 258 3280441102884 259 3357446311032 260 3435952121162 261 3515981838104 262 3597559037108 263 3680707565928 264 3765451546914 265 3851815379112 266 3939823740372 267 4029501589464 268 4120874168202 269 4213967003576 270 4308805909892 271 4405416990920 272 4503826642050 273 4604061552456 274 4706148707268 275 4810115389752 276 4915989183498 277 5023797974616 278 5133569953940 279 5245333619240 280 5359117777442 281 5474951546856 282 5592864359412 283 5712885962904 284 5835046423242 285 5959376126712 286 6085905782244 287 6214666423688 288 6345689412098 289 6479006438024 290 6614649523812 291 6752651025912 292 6893043637194 293 7035860389272 294 7181134654836 295 7328900149992 296 7479190936610 297 7632041424680 298 7787486374676 299 7945560899928 300 8106300469002 301 8269740908088 302 8435918403396 303 8604869503560 304 8776631122050 305 8951240539592 306 9128735406596 307 9309153745592 308 9492533953674 309 9678914804952 310 9868335453012 311 10060835433384 312 10256454666018 313 10455233457768 314 10657212504884 315 10862432895512 316 11070936112202 317 11282764034424 318 11497958941092 319 11716563513096 320 11938620835842 321 12164174401800 322 12393268113060 323 12625946283896 324 12862253643338 325 13102235337752 326 13345936933428 327 13593404419176 328 13844684208930 329 14099823144360 330 14358868497492 331 14621867973336 332 14888869712522 333 15159922293944 334 15435074737412 335 15714376506312 336 15997877510274 337 16285628107848 338 16577679109188 339 16874081778744 340 17174887837962 341 17480149467992 342 17789919312404 343 18104250479912 344 18423196547106 345 18746811561192 346 19075150042740 347 19408266988440 348 19746217873866 349 20089058656248 350 20436845777252 351 20789636165768 352 21147487240706 353 21510456913800 354 21878603592420 355 22251986182392 356 22630664090826 357 23014697228952 358 23404146014964 359 23799071376872 360 24199534755362 361 24605598106664 362 25017323905428 363 25434775147608 364 25858015353354 365 26287108569912 366 26722119374532 367 27163112877384 368 27610154724482 369 28063311100616 370 28522648732292 371 28988234890680 372 29460137394570 373 29938424613336 374 30423165469908 375 30914429443752 376 31412286573858 377 31916807461736 378 32428063274420 379 32946125747480 380 33471067188042 381 34002960477816 382 34541879076132 383 35087897022984 384 35641088942082 385 36201530043912 386 36769296128804 387 37344463590008 388 37927109416778 389 38517311197464 390 39115147122612 391 39720695988072 392 40334037198114 393 40955250768552 394 41584417329876 395 42221618130392 396 42866935039370 397 43520450550200 398 44182247783556 399 44852410490568 400 45531023056002 401 46218170501448 402 46913938488516 403 47618413322040 404 48331681953290 405 49053831983192 406 49784951665556 407 50525129910312 408 51274456286754 409 52033021026792 410 52800915028212 411 53578229857944 412 54365057755338 413 55161491635448 414 55967625092324 415 56783552402312 416 57609368527362 417 58445169118344 418 59291050518372 419 60147109766136 420 61013444599242 421 61890153457560 422 62777335486580 423 63675090540776 424 64583519186978 425 65502722707752 426 66432803104788 427 67373863102296 428 68326006150410 429 69289336428600 430 70263958849092 431 71249979060296 432 72247503450242 433 73256639150024 434 74277494037252 435 75310176739512 436 76354796637834 437 77411463870168 438 78480289334868 439 79561384694184 440 80654862377762 441 81760835586152 442 82879418294324 443 84010725255192 444 85154872003146 445 86311974857592 446 87482150926500 447 88665518109960 448 89862195103746 449 91072301402888 450 92295957305252 451 93533283915128 452 94784403146826 453 96049437728280 454 97328511204660 455 98621747941992 456 99929273130786 457 101251212789672 458 102587693769044 459 103938843754712 460 105304791271562 461 106685665687224 462 108081597215748 463 109492716921288 464 110919156721794 465 112361049392712 466 113818528570692 467 115291728757304 468 116780785322762 469 118285834509656 470 119807013436692 471 121344460102440 472 122898313389090 473 124468713066216 474 126055799794548 475 127659715129752 476 129280601526218 477 130918602340856 478 132573861836900 479 134246525187720 480 135936738480642 481 137644648720776 482 139370403834852 483 141114152675064 484 142876045022922 485 144656231593112 486 146454864037364 487 148272094948328 488 150108077863458 489 151962967268904 490 153836918603412 491 155730088262232 492 157642633601034 493 159574712939832 494 161526485566916 495 163498111742792 496 165489752704130 497 167501570667720 498 169533728834436 499 171586391393208 500 173659723525002 501 175753891406808 502 177869062215636 503 180005404132520 504 182163086346530 505 184342279058792 506 186543153486516 507 188765881867032 508 191010637461834 509 193277594560632 510 195566928485412 511 197878815594504 512 200213433286658 513 202570960005128 514 204951575241764 515 207355459541112 516 209782794504522 517 212233762794264 518 214708548137652 519 217207335331176 520 219730310244642 521 222277659825320 522 224849572102100 523 227446236189656 524 230067842292618 525 232714581709752 526 235386646838148 527 238084231177416 528 240807529333890 529 243556737024840 530 246332051082692 531 249133669459256 532 251961791229962 533 254816616598104 534 257698346899092 535 260607184604712 536 263543333327394 537 266506997824488 538 269498384002548 539 272517698921624 540 275565150799562 541 278640949016312 542 281745304118244 543 284878427822472 544 288040533021186 545 291231833785992 546 294452545372260 547 297702884223480 548 300983067975626 549 304293315461528 550 307633846715252 551 311004882976488 552 314406646694946 553 317839361534760 554 321303252378900 555 324798545333592 556 328325467732746 557 331884248142392 558 335475116365124 559 339098303444552 560 342754041669762 561 346442564579784 562 350164106968068 563 353918904886968 564 357707195652234 565 361529217847512 566 365385211328852 567 369275417229224 568 373200077963042 569 377159437230696 570 381153740023092 571 385183232626200 572 389248162625610 573 393348778911096 574 397485331681188 575 401658072447752 576 405867254040578 577 410113130611976 578 414395957641380 579 418715991939960 580 423073491655242 581 427468716275736 582 431901926635572 583 436373384919144 584 440883354665762 585 445432100774312 586 450019889507924 587 454646988498648 588 459313666752138 589 464020194652344 590 468766843966212 591 473553887848392 592 478381600845954 593 483250258903112 594 488160139365956 595 493111520987192 596 498104683930890 597 503139909777240 598 508217481527316 599 513337683607848 600 518500801876002 601 523707123624168 602 528956937584756 603 534250533935000 604 539588204301770 605 544970241766392 606 550396940869476 607 555868597615752 608 561385509478914 609 566947975406472 610 572556295824612 611 578210772643064 612 583911709259978 613 589659410566808 614 595454182953204 615 601296334311912 616 607186174043682 617 613124013062184 618 619110163798932 619 625144940208216 620 631228657772042 621 637361633505080 622 643544185959620 623 649776635230536 624 656059302960258 625 662392512343752 626 668776588133508 627 675211856644536 628 681698645759370 629 688237284933080 630 694828105198292 631 701471439170216 632 708167621051682 633 714916986638184 634 721719873322932 635 728576620101912 636 735487567578954 637 742453057970808 638 749473435112228 639 756549044461064 640 763680233103362 641 770867349758472 642 778110744784164 643 785410770181752 644 792767779601226 645 800182128346392 646 807654173380020 647 815184273329000 648 822772788489506 649 830420080832168 650 838126514007252 651 845892453349848 652 853718265885066 653 861604320333240 654 869550987115140 655 877558638357192 656 885627647896706 657 893758391287112 658 901951245803204 659 910206590446392 660 918524805949962 661 926906274784344 662 935351381162388 663 943860511044648 664 952434052144674 665 961072393934312 666 969775927649012 667 978545046293144 668 987380144645322 669 996281619263736 670 1005249868491492 671 1014285292461960 672 1023388293104130 673 1032559274147976 674 1041798641129828 675 1051106801397752 676 1060484164116938 677 1069931140275096 678 1079448142687860 679 1089035586004200 680 1098693886711842 681 1108423463142696 682 1118224735478292 683 1128098125755224 684 1138044057870602 685 1148062957587512 686 1158155252540484 687 1168321372240968 688 1178561748082818 689 1188876813347784 690 1199267003211012 691 1209732754746552 692 1220274506932874 693 1230892700658392 694 1241587778726996 695 1252360185863592 696 1263210368719650 697 1274138775878760 698 1285145857862196 699 1296232067134488 700 1307397858109002 701 1318643687153528 702 1329970012595876 703 1341377294729480 704 1352865995819010 705 1364436580105992 706 1376089513814436 707 1387825265156472 708 1399644304337994 709 1411547103564312 710 1423534137045812 711 1435605881003624 712 1447762813675298 713 1460005415320488 714 1472334168226644 715 1484749556714712 716 1497252067144842 717 1509842187922104 718 1522520409502212 719 1535287224397256 720 1548143127181442 721 1561088614496840 722 1574124185059140 723 1587250339663416 724 1600467581189898 725 1613776414609752 726 1627177346990868 727 1640670887503656 728 1654257547426850 729 1667937840153320 730 1681712281195892 731 1695581388193176 732 1709545680915402 733 1723605681270264 734 1737761913308772 735 1752014903231112 736 1766365179392514 737 1780813272309128 738 1795359714663908 739 1810005041312504 740 1824749789289162 741 1839594497812632 742 1854539708292084 743 1869585964333032 744 1884733811743266 745 1899983798538792 746 1915336474949780 747 1930792393426520 748 1946352108645386 749 1962016177514808 750 1977785159181252 751 1993659615035208 752 2009640108717186 753 2025727206123720 754 2041921475413380 755 2058223487012792 756 2074633813622666 757 2091153030223832 758 2107781714083284 759 2124520444760232 760 2141369804112162 761 2158330376300904 762 2175402747798708 763 2192587507394328 764 2209885246199114 765 2227296557653112 766 2244822037531172 767 2262462283949064 768 2280217897369602 769 2298089480608776 770 2316077638841892 771 2334182979609720 772 2352406112824650 773 2370747650776856 774 2389208208140468 775 2407788401979752 776 2426488851755298 777 2445310179330216 778 2464253008976340 779 2483317967380440 780 2502505683650442 781 2521816789321656 782 2541251918363012 783 2560811707183304 784 2580496794637442 785 2600307822032712 786 2620245433135044 787 2640310274175288 788 2660502993855498 789 2680824243355224 790 2701274676337812 791 2721854948956712 792 2742565719861794 793 2763407650205672 794 2784381403650036 795 2805487646371992 796 2826727047070410 797 2848100276972280 798 2869608009839076 799 2891250921973128 800 2913029692224002 801 2934945001994888 802 2956997535248996 803 2979187978515960 804 3001517020898250 805 3023985354077592 806 3046593672321396 807 3069342672489192 808 3092233054039074 809 3115265519034152 810 3138440772149012 811 3161759520676184 812 3185222474532618 813 3208830346266168 814 3232583851062084 815 3256483706749512 816 3280530633808002 817 3304725355374024 818 3329068597247492 819 3353561087898296 820 3378203558472842 821 3402996742800600 822 3427941377400660 823 3453038201488296 824 3478287956981538 825 3503691388507752 826 3529249243410228 827 3554962271754776 828 3580831226336330 829 3606856862685560 830 3633039939075492 831 3659381216528136 832 3685881458821122 833 3712541432494344 834 3739361906856612 835 3766343653992312 836 3793487448768074 837 3820794068839448 838 3848264294657588 839 3875898909475944 840 3903698699356962 841 3931664453178792 842 3959796962642004 843 3988097022276312 844 4016565429447306 845 4045202984363192 846 4074010490081540 847 4102988752516040 848 4132138580443266 849 4161460785509448 850 4190956182237252 851 4220625588032568 852 4250469823191306 853 4280489710906200 854 4310686077273620 855 4341059751300392 856 4371611564910626 857 4402342352952552 858 4433252953205364 859 4464344206386072 860 4495616956156362 861 4527072049129464 862 4558710334877028 863 4590532665936008 864 4622539897815554 865 4654732889003912 866 4687112500975332 867 4719679598196984 868 4752435048135882 869 4785379721265816 870 4818514491074292 871 4851840234069480 872 4885357829787170 873 4919068160797736 874 4952972112713108 875 4987070574193752 876 5021364436955658 877 5055854595777336 878 5090541948506820 879 5125427396068680 880 5160511842471042 881 5195796194812616 882 5231281363289732 883 5266968261203384 884 5302857804966282 885 5338950914109912 886 5375248511291604 887 5411751522301608 888 5448460876070178 889 5485377504674664 890 5522502343346612 891 5559836330478872 892 5597380407632714 893 5635135519544952 894 5673102614135076 895 5711282642512392 896 5749676558983170 897 5788285321057800 898 5827109889457956 899 5866151228123768 900 5905410304221002 901 5944888088148248 902 5984585553544116 903 6024503677294440 904 6064643439539490 905 6105005823681192 906 6145591816390356 907 6186402407613912 908 6227438590582154 909 6268701361815992 910 6310191721134212 911 6351910671660744 912 6393859219831938 913 6436038375403848 914 6478449151459524 915 6521092564416312 916 6563969634033162 917 6607081383417944 918 6650428839034772 919 6694013030711336 920 6737834991646242 921 6781895758416360 922 6826196370984180 923 6870737872705176 924 6915521310335178 925 6960547734037752 926 7005818197391588 927 7051333757397896 928 7097095474487810 929 7143104412529800 930 7189361638837092 931 7235868224175096 932 7282625242768842 933 7329633772310424 934 7376894893966452 935 7424409692385512 936 7472179255705634 937 7520204675561768 938 7568487047093268 939 7617027468951384 940 7665827043306762 941 7714886875856952 942 7764208075833924 943 7813791756011592 944 7863639032713346 945 7913751025819592 946 7964128858775300 947 8014773658597560 948 8065686555883146 949 8116868684816088 950 8168321183175252 951 8220045192341928 952 8272041857307426 953 8324312326680680 954 8376857752695860 955 8429679291219992 956 8482778101760586 957 8536155347473272 958 8589812195169444 959 8643749815323912 960 8697969382082562 961 8752472073270024 962 8807259070397348 963 8862331558669688 964 8917690726993994 965 8973337767986712 966 9029273877981492 967 9085500257036904 968 9142018108944162 969 9198828641234856 970 9255933065188692 971 9313332595841240 972 9371028451991690 973 9429021856210616 974 9487314034847748 975 9545906218039752 976 9604799639718018 977 9663995537616456 978 9723495153279300 979 9783299732068920 980 9843410523173642 981 9903828779615576 982 9964555758258452 983 10025592719815464 984 10086940928857122 985 10148601653819112 986 10210576167010164 987 10272865744619928 988 10335471666726858 989 10398395217306104 990 10461637684237412 991 10525200359313032 992 10589084538245634 993 10653291520676232 994 10717822610182116 995 10782679114284792 996 10847862344457930 997 10913373616135320 998 10979214248718836 999 11045385565586408 1000 11111888894100002