-1 0 0 0 1 6 2 42 3 156 4 420 5 930 6 1806 7 3192 8 5256 9 8190 10 12210 11 17556 12 24492 13 33306 14 44310 15 57840 16 74256 17 93942 18 117306 19 144780 20 176820 21 213906 22 256542 23 305256 24 360600 25 423150 26 493506 27 572292 28 660156 29 757770 30 865830 31 985056 32 1116192 33 1260006 34 1417290 35 1588860 36 1775556 37 1978242 38 2197806 39 2435160 40 2691240 41 2967006 42 3263442 43 3581556 44 3922380 45 4286970 46 4676406 47 5091792 48 5534256 49 6004950 50 6505050 51 7035756 52 7598292 53 8193906 54 8823870 55 9489480 56 10192056 57 10932942 58 11713506 59 12535140 60 13399260 61 14307306 62 15260742 63 16261056 64 17309760 65 18408390 66 19558506 67 20761692 68 22019556 69 23333730 70 24705870 71 26137656 72 27630792 73 29187006 74 30808050 75 32495700 76 34251756 77 36078042 78 37976406 79 39948720 80 41996880 81 44122806 82 46328442 83 48615756 84 50986740 85 53443410 86 55987806 87 58621992 88 61348056 89 64168110 90 67084290 91 70098756 92 73213692 93 76431306 94 79753830 95 83183520 96 86722656 97 90373542 98 94138506 99 98019900 100 102020100 101 106141506 102 110386542 103 114757656 104 119257320 105 123888030 106 128652306 107 133552692 108 138591756 109 143772090 110 149096310 111 154567056 112 160186992 113 165958806 114 171885210 115 177968940 116 184212756 117 190619442 118 197191806 119 203932680 120 210844920 121 217931406 122 225195042 123 232638756 124 240265500 125 248078250 126 256080006 127 264273792 128 272662656 129 281249670 130 290037930 131 299030556 132 308230692 133 317641506 134 327266190 135 337107960 136 347170056 137 357455742 138 367968306 139 378711060 140 389687340 141 400900506 142 412353942 143 424051056 144 435995280 145 448190070 146 460638906 147 473345292 148 486312756 149 499544850 150 513045150 151 526817256 152 540864792 153 555191406 154 569800770 155 584696580 156 599882556 157 615362442 158 631140006 159 647219040 160 663603360 161 680296806 162 697303242 163 714626556 164 732270660 165 750239490 166 768537006 167 787167192 168 806134056 169 825441630 170 845093970 171 865095156 172 885449292 173 906160506 174 927232950 175 948670800 176 970478256 177 992659542 178 1015218906 179 1038160620 180 1061488980 181 1085208306 182 1109322942 183 1133837256 184 1158755640 185 1184082510 186 1209822306 187 1235979492 188 1262558556 189 1289564010 190 1317000390 191 1344872256 192 1373184192 193 1401940806 194 1431146730 195 1460806620 196 1490925156 197 1521507042 198 1552557006 199 1584079800 200 1616080200 201 1648563006 202 1681533042 203 1714995156 204 1748954220 205 1783415130 206 1818382806 207 1853862192 208 1889858256 209 1926375990 210 1963420410 211 2000996556 212 2039109492 213 2077764306 214 2116966110 215 2156720040 216 2197031256 217 2237904942 218 2279346306 219 2321360580 220 2363953020 221 2407128906 222 2450893542 223 2495252256 224 2540210400 225 2585773350 226 2631946506 227 2678735292 228 2726145156 229 2774181570 230 2822850030 231 2872156056 232 2922105192 233 2972703006 234 3023955090 235 3075867060 236 3128444556 237 3181693242 238 3235618806 239 3290226960 240 3345523440 241 3401514006 242 3458204442 243 3515600556 244 3573708180 245 3632533170 246 3692081406 247 3752358792 248 3813371256 249 3875124750 250 3937625250 251 4000878756 252 4064891292 253 4129668906 254 4195217670 255 4261543680 256 4328653056 257 4396551942 258 4465246506 259 4534742940 260 4605047460 261 4676166306 262 4748105742 263 4820872056 264 4894471560 265 4968910590 266 5044195506 267 5120332692 268 5197328556 269 5275189530 270 5353922070 271 5433532656 272 5514027792 273 5595414006 274 5677697850 275 5760885900 276 5844984756 277 5930001042 278 6015941406 279 6102812520 280 6190621080 281 6279373806 282 6369077442 283 6459738756 284 6551364540 285 6643961610 286 6737536806 287 6832096992 288 6927649056 289 7024199910 290 7121756490 291 7220325756 292 7319914692 293 7420530306 294 7522179630 295 7624869720 296 7728607656 297 7833400542 298 7939255506 299 8046179700 300 8154180300 301 8263264506 302 8373439542 303 8484712656 304 8597091120 305 8710582230 306 8825193306 307 8940931692 308 9057804756 309 9175819890 310 9294984510 311 9415306056 312 9536791992 313 9659449806 314 9783287010 315 9908311140 316 10034529756 317 10161950442 318 10290580806 319 10420428480 320 10551501120 321 10683806406 322 10817352042 323 10952145756 324 11088195300 325 11225508450 326 11364093006 327 11503956792 328 11645107656 329 11787553470 330 11931302130 331 12076361556 332 12222739692 333 12370444506 334 12519483990 335 12669866160 336 12821599056 337 12974690742 338 13129149306 339 13284982860 340 13442199540 341 13600807506 342 13760814942 343 13922230056 344 14085061080 345 14249316270 346 14415003906 347 14582132292 348 14750709756 349 14920744650 350 15092245350 351 15265220256 352 15439677792 353 15615626406 354 15793074570 355 15972030780 356 16152503556 357 16334501442 358 16518033006 359 16703106840 360 16889731560 361 17077915806 362 17267668242 363 17458997556 364 17651912460 365 17846421690 366 18042534006 367 18240258192 368 18439603056 369 18640577430 370 18843190170 371 19047450156 372 19253366292 373 19460947506 374 19670202750 375 19881141000 376 20093771256 377 20308102542 378 20524143906 379 20741904420 380 20961393180 381 21182619306 382 21405591942 383 21630320256 384 21856813440 385 22085080710 386 22315131306 387 22546974492 388 22780619556 389 23016075810 390 23253352590 391 23492459256 392 23733405192 393 23976199806 394 24220852530 395 24467372820 396 24715770156 397 24966054042 398 25218234006 399 25472319600 400 25728320400 401 25986246006 402 26246106042 403 26507910156 404 26771668020 405 27037389330 406 27305083806 407 27574761192 408 27846431256 409 28120103790 410 28395788610 411 28673495556 412 28953234492 413 29235015306 414 29518847910 415 29804742240 416 30092708256 417 30382755942 418 30674895306 419 30969136380 420 31265489220 421 31563963906 422 31864570542 423 32167319256 424 32472220200 425 32779283550 426 33088519506 427 33399938292 428 33713550156 429 34029365370 430 34347394230 431 34667647056 432 34990134192 433 35314866006 434 35641852890 435 35971105260 436 36302633556 437 36636448242 438 36972559806 439 37310978760 440 37651715640 441 37994781006 442 38340185442 443 38687939556 444 39038053980 445 39390539370 446 39745406406 447 40102665792 448 40462328256 449 40824404550 450 41188905450 451 41555841756 452 41925224292 453 42297063906 454 42671371470 455 43048157880 456 43427434056 457 43809210942 458 44193499506 459 44580310740 460 44969655660 461 45361545306 462 45755990742 463 46153003056 464 46552593360 465 46954772790 466 47359552506 467 47766943692 468 48176957556 469 48589605330 470 49004898270 471 49422847656 472 49843464792 473 50266761006 474 50692747650 475 51121436100 476 51552837756 477 51986964042 478 52423826406 479 52863436320 480 53305805280 481 53750944806 482 54198866442 483 54649581756 484 55103102340 485 55559439810 486 56018605806 487 56480611992 488 56945470056 489 57413191710 490 57883788690 491 58357272756 492 58833655692 493 59312949306 494 59795165430 495 60280315920 496 60768412656 497 61259467542 498 61753492506 499 62250499500 500 62750500500 501 63253507506 502 63759532542 503 64268587656 504 64780684920 505 65295836430 506 65814054306 507 66335350692 508 66859737756 509 67387227690 510 67917832710 511 68451565056 512 68988436992 513 69528460806 514 70071648810 515 70618013340 516 71167566756 517 71720321442 518 72276289806 519 72835484280 520 73397917320 521 73963601406 522 74532549042 523 75104772756 524 75680285100 525 76259098650 526 76841226006 527 77426679792 528 78015472656 529 78607617270 530 79203126330 531 79802012556 532 80404288692 533 81009967506 534 81619061790 535 82231584360 536 82847548056 537 83466965742 538 84089850306 539 84716214660 540 85346071740 541 85979434506 542 86616315942 543 87256729056 544 87900686880 545 88548202470 546 89199288906 547 89853959292 548 90512226756 549 91174104450 550 91839605550 551 92508743256 552 93181530792 553 93857981406 554 94538108370 555 95221924980 556 95909444556 557 96600680442 558 97295646006 559 97994354640 560 98696819760 561 99403054806 562 100113073242 563 100826888556 564 101544514260 565 102265963890 566 102991251006 567 103720389192 568 104453392056 569 105190273230 570 105931046370 571 106675725156 572 107424323292 573 108176854506 574 108933332550 575 109693771200 576 110458184256 577 111226585542 578 111998988906 579 112775408220 580 113555857380 581 114340350306 582 115128900942 583 115921523256 584 116718231240 585 117519038910 586 118323960306 587 119133009492 588 119946200556 589 120763547610 590 121585064790 591 122410766256 592 123240666192 593 124074778806 594 124913118330 595 125755699020 596 126602535156 597 127453641042 598 128309031006 599 129168719400 600 130032720600 601 130901049006 602 131773719042 603 132650745156 604 133532141820 605 134417923530 606 135308104806 607 136202700192 608 137101724256 609 138005191590 610 138913116810 611 139825514556 612 140742399492 613 141663786306 614 142589689710 615 143520124440 616 144455105256 617 145394646942 618 146338764306 619 147287472180 620 148240785420 621 149198718906 622 150161287542 623 151128506256 624 152100390000 625 153076953750 626 154058212506 627 155044181292 628 156034875156 629 157030309170 630 158030498430 631 159035458056 632 160045203192 633 161059749006 634 162079110690 635 163103303460 636 164132342556 637 165166243242 638 166205020806 639 167248690560 640 168297267840 641 169350768006 642 170409206442 643 171472598556 644 172540959780 645 173614305570 646 174692651406 647 175776012792 648 176864405256 649 177957844350 650 179056345650 651 180159924756 652 181268597292 653 182382378906 654 183501285270 655 184625332080 656 185754535056 657 186888909942 658 188028472506 659 189173238540 660 190323223860 661 191478444306 662 192638915742 663 193804654056 664 194975675160 665 196151994990 666 197333629506 667 198520594692 668 199712906556 669 200910581130 670 202113634470 671 203322082656 672 204535941792 673 205755228006 674 206979957450 675 208210146300 676 209445810756 677 210686967042 678 211933631406 679 213185820120 680 214443549480 681 215706835806 682 216975695442 683 218250144756 684 219530200140 685 220815878010 686 222107194806 687 223404166992 688 224706811056 689 226015143510 690 227329180890 691 228648939756 692 229974436692 693 231305688306 694 232642711230 695 233985522120 696 235334137656 697 236688574542 698 238048849506 699 239414979300 700 240786980700 701 242164870506 702 243548665542 703 244938382656 704 246334038720 705 247735650630 706 249143235306 707 250556809692 708 251976390756 709 253401995490 710 254833640910 711 256271344056 712 257715121992 713 259164991806 714 260620970610 715 262083075540 716 263551323756 717 265025732442 718 266506318806 719 267993100080 720 269486093520 721 270985316406 722 272490786042 723 274002519756 724 275520534900 725 277044848850 726 278575479006 727 280112442792 728 281655757656 729 283205441070 730 284761510530 731 286323983556 732 287892877692 733 289468210506 734 291049999590 735 292638262560 736 294233017056 737 295834280742 738 297442071306 739 299056406460 740 300677303940 741 302304781506 742 303938856942 743 305579548056 744 307226872680 745 308880848670 746 310541493906 747 312208826292 748 313882863756 749 315563624250 750 317251125750 751 318945386256 752 320646423792 753 322354256406 754 324068902170 755 325790379180 756 327518705556 757 329253899442 758 330995979006 759 332744962440 760 334500867960 761 336263713806 762 338033518242 763 339810299556 764 341594076060 765 343384866090 766 345182688006 767 346987560192 768 348799501056 769 350618529030 770 352444662570 771 354277920156 772 356118320292 773 357965881506 774 359820622350 775 361682561400 776 363551717256 777 365428108542 778 367311753906 779 369202672020 780 371100881580 781 373006401306 782 374919249942 783 376839446256 784 378767009040 785 380701957110 786 382644309306 787 384594084492 788 386551301556 789 388515979410 790 390488136990 791 392467793256 792 394454967192 793 396449677806 794 398451944130 795 400461785220 796 402479220156 797 404504268042 798 406536948006 799 408577279200 800 410625280800 801 412680972006 802 414744372042 803 416815500156 804 418894375620 805 420981017730 806 423075445806 807 425177679192 808 427287737256 809 429405639390 810 431531405010 811 433665053556 812 435806604492 813 437956077306 814 440113491510 815 442278866640 816 444452222256 817 446633577942 818 448822953306 819 451020367980 820 453225841620 821 455439393906 822 457661044542 823 459890813256 824 462128719800 825 464374783950 826 466629025506 827 468891464292 828 471162120156 829 473441012970 830 475728162630 831 478023589056 832 480327312192 833 482639352006 834 484959728490 835 487288461660 836 489625571556 837 491971078242 838 494325001806 839 496687362360 840 499058180040 841 501437475006 842 503825267442 843 506221577556 844 508626425580 845 511039831770 846 513461816406 847 515892399792 848 518331602256 849 520779444150 850 523235945850 851 525701127756 852 528175010292 853 530657613906 854 533148959070 855 535649066280 856 538157956056 857 540675648942 858 543202165506 859 545737526340 860 548281752060 861 550834863306 862 553396880742 863 555967825056 864 558547716960 865 561136577190 866 563734426506 867 566341285692 868 568957175556 869 571582116930 870 574216130670 871 576859237656 872 579511458792 873 582172815006 874 584843327250 875 587523016500 876 590211903756 877 592910010042 878 595617356406 879 598333963920 880 601059853680 881 603795046806 882 606539564442 883 609293427756 884 612056657940 885 614829276210 886 617611303806 887 620402761992 888 623203672056 889 626014055310 890 628833933090 891 631663326756 892 634502257692 893 637350747306 894 640208817030 895 643076488320 896 645953782656 897 648840721542 898 651737326506 899 654643619100 900 657559620900 901 660485353506 902 663420838542 903 666366097656 904 669321152520 905 672286024830 906 675260736306 907 678245308692 908 681239763756 909 684244123290 910 687258409110 911 690282643056 912 693316846992 913 696361042806 914 699415252410 915 702479497740 916 705553800756 917 708638183442 918 711732667806 919 714837275880 920 717952029720 921 721076951406 922 724212063042 923 727357386756 924 730512944700 925 733678759050 926 736854852006 927 740041245792 928 743237962656 929 746445024870 930 749662454730 931 752890274556 932 756128506692 933 759377173506 934 762636297390 935 765905900760 936 769186006056 937 772476635742 938 775777812306 939 779089558260 940 782411896140 941 785744848506 942 789088437942 943 792442687056 944 795807618480 945 799183254870 946 802569618906 947 805966733292 948 809374620756 949 812793304050 950 816222805950 951 819663149256 952 823114356792 953 826576451406 954 830049455970 955 833533393380 956 837028286556 957 840534158442 958 844051032006 959 847578930240 960 851117876160 961 854667892806 962 858229003242 963 861801230556 964 865384597860 965 868979128290 966 872584845006 967 876201771192 968 879829930056 969 883469344830 970 887120038770 971 890782035156 972 894455357292 973 898140028506 974 901836072150 975 905543511600 976 909262370256 977 912992671542 978 916734438906 979 920487695820 980 924252465780 981 928028772306 982 931816638942 983 935616089256 984 939427146840 985 943249835310 986 947084178306 987 950930199492 988 954787922556 989 958657371210 990 962538569190 991 966431540256 992 970336308192 993 974252896806 994 978181329930 995 982121631420 996 986073825156 997 990037935042 998 994013985006 999 998001999000 1000 1002002001000