1 1 2 4 3 14 4 40 5 97 6 206 7 394 8 694 9 1145 10 1792 11 2686 12 3884 13 5449 14 7450 15 9962 16 13066 17 16849 18 21404 19 26830 20 33232 21 40721 22 49414 23 59434 24 70910 25 83977 26 98776 27 115454 28 134164 29 155065 30 178322 31 204106 32 232594 33 263969 34 298420 35 336142 36 377336 37 422209 38 470974 39 523850 40 581062 41 642841 42 709424 43 781054 44 857980 45 940457 46 1028746 47 1123114 48 1223834 49 1331185 50 1445452 51 1566926 52 1695904 53 1832689 54 1977590 55 2130922 56 2293006 57 2464169 58 2644744 59 2835070 60 3035492 61 3246361 62 3468034 63 3700874 64 3945250 65 4201537 66 4470116 67 4751374 68 5045704 69 5353505 70 5675182 71 6011146 72 6361814 73 6727609 74 7108960 75 7506302 76 7920076 77 8350729 78 8798714 79 9264490 80 9748522 81 10251281 82 10773244 83 11314894 84 11876720 85 12459217 86 13062886 87 13688234 88 14335774 89 15006025 90 15699512 91 16416766 92 17158324 93 17924729 94 18716530 95 19534282 96 20378546 97 21249889 98 22148884 99 23076110 100 24032152 101 25017601 102 26033054 103 27079114 104 28156390 105 29265497 106 30407056 107 31581694 108 32790044 109 34032745 110 35310442 111 36623786 112 37973434 113 39360049 114 40784300 115 42246862 116 43748416 117 45289649 118 46871254 119 48493930 120 50158382 121 51865321 122 53615464 123 55409534 124 57248260 125 59132377 126 61062626 127 63039754 128 65064514 129 67137665 130 69259972 131 71432206 132 73655144 133 75929569 134 78256270 135 80636042 136 83069686 137 85558009 138 88101824 139 90701950 140 93359212 141 96074441 142 98848474 143 101682154 144 104576330 145 107531857 146 110549596 147 113630414 148 116775184 149 119984785 150 123260102 151 126602026 152 130011454 153 133489289 154 137036440 155 140653822 156 144342356 157 148102969 158 151936594 159 155844170 160 159826642 161 163884961 162 168020084 163 172232974 164 176524600 165 180895937 166 185347966 167 189881674 168 194498054 169 199198105 170 203982832 171 208853246 172 213810364 173 218855209 174 223988810 175 229212202 176 234526426 177 239932529 178 245431564 179 251024590 180 256712672 181 262496881 182 268378294 183 274357994 184 280437070 185 286616617 186 292897736 187 299281534 188 305769124 189 312361625 190 319060162 191 325865866 192 332779874 193 339803329 194 346937380 195 354183182 196 361541896 197 369014689 198 376602734 199 384307210 200 392129302 201 400070201 202 408131104 203 416313214 204 424617740 205 433045897 206 441598906 207 450277994 208 459084394 209 468019345 210 477084092 211 486279886 212 495607984 213 505069649 214 514666150 215 524398762 216 534268766 217 544277449 218 554426104 219 564716030 220 575148532 221 585724921 222 596446514 223 607314634 224 618330610 225 629495777 226 640811476 227 652279054 228 663899864 229 675675265 230 687606622 231 699695306 232 711942694 233 724350169 234 736919120 235 749650942 236 762547036 237 775608809 238 788837674 239 802235050 240 815802362 241 829541041 242 843452524 243 857538254 244 871799680 245 886238257 246 900855446 247 915652714 248 930631534 249 945793385 250 961139752 251 976672126 252 992392004 253 1008300889 254 1024400290 255 1040691722 256 1057176706 257 1073856769 258 1090733444 259 1107808270 260 1125082792 261 1142558561 262 1160237134 263 1178120074 264 1196208950 265 1214505337 266 1233010816 267 1251726974 268 1270655404 269 1289797705 270 1309155482 271 1328730346 272 1348523914 273 1368537809 274 1388773660 275 1409233102 276 1429917776 277 1450829329 278 1471969414 279 1493339690 280 1514941822 281 1536777481 282 1558848344 283 1581156094 284 1603702420 285 1626489017 286 1649517586 287 1672789834 288 1696307474 289 1720072225 290 1744085812 291 1768349966 292 1792866424 293 1817636929 294 1842663230 295 1867947082 296 1893490246 297 1919294489 298 1945361584 299 1971693310 300 1998291452 301 2025157801 302 2052294154 303 2079702314 304 2107384090 305 2135341297 306 2163575756 307 2192089294 308 2220883744 309 2249960945 310 2279322742 311 2308970986 312 2338907534 313 2369134249 314 2399653000 315 2430465662 316 2461574116 317 2492980249 318 2524685954 319 2556693130 320 2589003682 321 2621619521 322 2654542564 323 2687774734 324 2721317960 325 2755174177 326 2789345326 327 2823833354 328 2858640214 329 2893767865 330 2929218272 331 2964993406 332 3001095244 333 3037525769 334 3074286970 335 3111380842 336 3148809386 337 3186574609 338 3224678524 339 3263123150 340 3301910512 341 3341042641 342 3380521574 343 3420349354 344 3460528030 345 3501059657 346 3541946296 347 3583190014 348 3624792884 349 3666756985 350 3709084402 351 3751777226 352 3794837554 353 3838267489 354 3882069140 355 3926244622 356 3970796056 357 4015725569 358 4061035294 359 4106727370 360 4152803942 361 4199267161 362 4246119184 363 4293362174 364 4340998300 365 4389029737 366 4437458666 367 4486287274 368 4535517754 369 4585152305 370 4635193132 371 4685642446 372 4736502464 373 4787775409 374 4839463510 375 4891569002 376 4944094126 377 4997041129 378 5050412264 379 5104209790 380 5158435972 381 5213093081 382 5268183394 383 5323709194 384 5379672770 385 5436076417 386 5492922436 387 5550213134 388 5607950824 389 5666137825 390 5724776462 391 5783869066 392 5843417974 393 5903425529 394 5963894080 395 6024825982 396 6086223596 397 6148089289 398 6210425434 399 6273234410 400 6336518602 401 6400280401 402 6464522204 403 6529246414 404 6594455440 405 6660151697 406 6726337606 407 6793015594 408 6860188094 409 6927857545 410 6996026392 411 7064697086 412 7133872084 413 7203553849 414 7273744850 415 7344447562 416 7415664466 417 7487398049 418 7559650804 419 7632425230 420 7705723832 421 7779549121 422 7853903614 423 7928789834 424 8004210310 425 8080167577 426 8156664176 427 8233702654 428 8311285564 429 8389415465 430 8468094922 431 8547326506 432 8627112794 433 8707456369 434 8788359820 435 8869825742 436 8951856736 437 9034455409 438 9117624374 439 9201366250 440 9285683662 441 9370579241 442 9456055624 443 9542115454 444 9628761380 445 9715996057 446 9803822146 447 9892242314 448 9981259234 449 10070875585 450 10161094052 451 10251917326 452 10343348104 453 10435389089 454 10528042990 455 10621312522 456 10715200406 457 10809709369 458 10904842144 459 11000601470 460 11096990092 461 11194010761 462 11291666234 463 11389959274 464 11488892650 465 11588469137 466 11688691516 467 11789562574 468 11891085104 469 11993261905 470 12096095782 471 12199589546 472 12303746014 473 12408568009 474 12514058360 475 12620219902 476 12727055476 477 12834567929 478 12942760114 479 13051634890 480 13161195122 481 13271443681 482 13382383444 483 13494017294 484 13606348120 485 13719378817 486 13833112286 487 13947551434 488 14062699174 489 14178558425 490 14295132112 491 14412423166 492 14530434524 493 14649169129 494 14768629930 495 14888819882 496 15009741946 497 15131399089 498 15253794284 499 15376930510 500 15500810752 501 15625438001 502 15750815254 503 15876945514 504 16003831790 505 16131477097 506 16259884456 507 16389056894 508 16518997444 509 16649709145 510 16781195042 511 16913458186 512 17046501634 513 17180328449 514 17314941700 515 17450344462 516 17586539816 517 17723530849 518 17861320654 519 17999912330 520 18139308982 521 18279513721 522 18420529664 523 18562359934 524 18705007660 525 18848475977 526 18992768026 527 19137886954 528 19283835914 529 19430618065 530 19578236572 531 19726694606 532 19875995344 533 20026141969 534 20177137670 535 20328985642 536 20481689086 537 20635251209 538 20789675224 539 20944964350 540 21101121812 541 21258150841 542 21416054674 543 21574836554 544 21734499730 545 21895047457 546 22056482996 547 22218809614 548 22382030584 549 22546149185 550 22711168702 551 22877092426 552 23043923654 553 23211665689 554 23380321840 555 23549895422 556 23720389756 557 23891808169 558 24064153994 559 24237430570 560 24411641242 561 24586789361 562 24762878284 563 24939911374 564 25117892000 565 25296823537 566 25476709366 567 25657552874 568 25839357454 569 26022126505 570 26205863432 571 26390571646 572 26576254564 573 26762915609 574 26950558210 575 27139185802 576 27328801826 577 27519409729 578 27711012964 579 27903614990 580 28097219272 581 28291829281 582 28487448494 583 28684080394 584 28881728470 585 29080396217 586 29280087136 587 29480804734 588 29682552524 589 29885334025 590 30089152762 591 30294012266 592 30499916074 593 30706867729 594 30914870780 595 31123928782 596 31334045296 597 31545223889 598 31757468134 599 31970781610 600 32185167902 601 32400630601 602 32617173304 603 32834799614 604 33053513140 605 33273317497 606 33494216306 607 33716213194 608 33939311794 609 34163515745 610 34388828692 611 34615254286 612 34842796184 613 35071458049 614 35301243550 615 35532156362 616 35764200166 617 35997378649 618 36231695504 619 36467154430 620 36703759132 621 36941513321 622 37180420714 623 37420485034 624 37661710010 625 37904099377 626 38147656876 627 38392386254 628 38638291264 629 38885375665 630 39133643222 631 39383097706 632 39633742894 633 39885582569 634 40138620520 635 40392860542 636 40648306436 637 40904962009 638 41162831074 639 41421917450 640 41682224962 641 41943757441 642 42206518724 643 42470512654 644 42735743080 645 43002213857 646 43269928846 647 43538891914 648 43809106934 649 44080577785 650 44353308352 651 44627302526 652 44902564204 653 45179097289 654 45456905690 655 45735993322 656 46016364106 657 46298021969 658 46580970844 659 46865214670 660 47150757392 661 47437602961 662 47725755334 663 48015218474 664 48305996350 665 48598092937 666 48891512216 667 49186258174 668 49482334804 669 49779746105 670 50078496082 671 50378588746 672 50680028114 673 50982818209 674 51286963060 675 51592466702 676 51899333176 677 52207566529 678 52517170814 679 52828150090 680 53140508422 681 53454249881 682 53769378544 683 54085898494 684 54403813820 685 54723128617 686 55043846986 687 55365973034 688 55689510874 689 56014464625 690 56340838412 691 56668636366 692 56997862624 693 57328521329 694 57660616630 695 57994152682 696 58329133646 697 58665563689 698 59003446984 699 59342787710 700 59683590052 701 60025858201 702 60369596354 703 60714808714 704 61061499490 705 61409672897 706 61759333156 707 62110484494 708 62463131144 709 62817277345 710 63172927342 711 63530085386 712 63888755734 713 64248942649 714 64610650400 715 64973883262 716 65338645516 717 65704941449 718 66072775354 719 66442151530 720 66813074282 721 67185547921 722 67559576764 723 67935165134 724 68312317360 725 68691037777 726 69071330726 727 69453200554 728 69836651614 729 70221688265 730 70608314872 731 70996535806 732 71386355444 733 71777778169 734 72170808370 735 72565450442 736 72961708786 737 73359587809 738 73759091924 739 74160225550 740 74562993112 741 74967399041 742 75373447774 743 75781143754 744 76190491430 745 76601495257 746 77014159696 747 77428489214 748 77844488284 749 78262161385 750 78681513002 751 79102547626 752 79525269754 753 79949683889 754 80375794540 755 80803606222 756 81233123456 757 81664350769 758 82097292694 759 82531953770 760 82968338542 761 83406451561 762 83846297384 763 84287880574 764 84731205700 765 85176277337 766 85623100066 767 86071678474 768 86522017154 769 86974120705 770 87427993732 771 87883640846 772 88341066664 773 88800275809 774 89261272910 775 89724062602 776 90188649526 777 90655038329 778 91123233664 779 91593240190 780 92065062572 781 92538705481 782 93014173594 783 93491471594 784 93970604170 785 94451576017 786 94934391836 787 95419056334 788 95905574224 789 96393950225 790 96884189062 791 97376295466 792 97870274174 793 98366129929 794 98863867480 795 99363491582 796 99865006996 797 100368418489 798 100873730834 799 101380948810 800 101890077202 801 102401120801 802 102914084404 803 103428972814 804 103945790840 805 104464543297 806 104985235006 807 105507870794 808 106032455494 809 106558993945 810 107087490992 811 107617951486 812 108150380284 813 108684782249 814 109221162250 815 109759525162 816 110299875866 817 110842219249 818 111386560204 819 111932903630 820 112481254432 821 113031617521 822 113583997814 823 114138400234 824 114694829710 825 115253291177 826 115813789576 827 116376329854 828 116940916964 829 117507555865 830 118076251522 831 118647008906 832 119219832994 833 119794728769 834 120371701220 835 120950755342 836 121531896136 837 122115128609 838 122700457774 839 123287888650 840 123877426262 841 124469075641 842 125062841824 843 125658729854 844 126256744780 845 126856891657 846 127459175546 847 128063601514 848 128670174634 849 129278899985 850 129889782652 851 130502827726 852 131118040304 853 131735425489 854 132354988390 855 132976734122 856 133600667806 857 134226794569 858 134855119544 859 135485647870 860 136118384692 861 136753335161 862 137390504434 863 138029897674 864 138671520050 865 139315376737 866 139961472916 867 140609813774 868 141260404504 869 141913250305 870 142568356382 871 143225727946 872 143885370214 873 144547288409 874 145211487760 875 145877973502 876 146546750876 877 147217825129 878 147891201514 879 148566885290 880 149244881722 881 149925196081 882 150607833644 883 151292799694 884 151980099520 885 152669738417 886 153361721686 887 154056054634 888 154752742574 889 155451790825 890 156153204712 891 156856989566 892 157563150724 893 158271693529 894 158982623330 895 159695945482 896 160411665346 897 161129788289 898 161850319684 899 162573264910 900 163298629352 901 164026418401 902 164756637454 903 165489291914 904 166224387190 905 166961928697 906 167701921856 907 168444372094 908 169189284844 909 169936665545 910 170686519642 911 171438852586 912 172193669834 913 172950976849 914 173710779100 915 174473082062 916 175237891216 917 176005212049 918 176775050054 919 177547410730 920 178322299582 921 179099722121 922 179879683864 923 180662190334 924 181447247060 925 182234859577 926 183025033426 927 183817774154 928 184613087314 929 185410978465 930 186211453172 931 187014517006 932 187820175544 933 188628434369 934 189439299070 935 190252775242 936 191068868486 937 191887584409 938 192708928624 939 193532906750 940 194359524412 941 195188787241 942 196020700874 943 196855270954 944 197692503130 945 198532403057 946 199374976396 947 200220228814 948 201068165984 949 201918793585 950 202772117302 951 203628142826 952 204486875854 953 205348322089 954 206212487240 955 207079377022 956 207948997156 957 208821353369 958 209696451394 959 210574296970 960 211454895842 961 212338253761 962 213224376484 963 214113269774 964 215004939400 965 215899391137 966 216796630766 967 217696664074 968 218599496854 969 219505134905 970 220413584032 971 221324850046 972 222238938764 973 223155856009 974 224075607610 975 224998199402 976 225923637226 977 226851926929 978 227783074364 979 228717085390 980 229653965872 981 230593721681 982 231536358694 983 232481882794 984 233430299870 985 234381615817 986 235335836536 987 236292967934 988 237253015924 989 238215986425 990 239181885362 991 240150718666 992 241122492274 993 242097212129 994 243074884180 995 244055514382 996 245039108696 997 246025673089 998 247015213534 999 248007736010 1000 249003246502