1000 1000 0 1 2 1
132625 572871 770124 563851 578941 933006 37851 712167 787787 21841 604359 544543 291697 614202 217317 279151 895815 907188 928 230088 615013 807840 735459 4978 235862 255796 73447 976978 608845 143807 47494 86708 266274 569504 236993 720635 568066 977048 562580 835334 263018 198469 319339 920134 130806 725275 115485 435250 211565 156159 801918 444289 354245 909101 770224 401684 523563 287652 281489 808390 85089 847306 719055 19606 44203 70341 444727 799706 256062 598661 735682 121716 236113 158306 960102 617252 455887 784041 899057 721071 344767 405267 131911 112760 671609 368635 254546 81084 541152 485852 488790 862017 503918 327348 336896 23371 645572 68132 671351 924330 12014 710566 445303 194355 814454 278185 90452 755819 856266 21767 457065 851719 235619 324249 387529 155470 507744 736258 618256 817582 872159 254642 800840 409139 157286 707315 649395 737989 161937 318442 665683 588924 796853 240420 695726 719766 24949 887234 551276 116030 742490 717428 754785 622773 809381 429708 728204 189664 558978 123757 404425 239570 954105 235461 501902 159068 931890 228058 291686 855381 641385 106038 479269 335615 848586 327428 342330 481933 197232 74501 712663 493024 671117 102290 258159 198070 718462 515328 393839 200845 280220 664983 236596 413469 111268 799790 825644 675104 762129 596992 979383 982764 693974 861699 470607 239963 518467 639997 809593 764175 617461 201882 382731 379210 793446 553631 290017 307653 304088 389731 831654 254990 627047 471721 431361 95849 521921 173097 570596 823270 534701 244453 672403 391863 655574 643711 242508 650379 11738 642115 824715 831978 907286 839926 158052 988583 990821 171645 896108 699395 349741 138617 923999 757799 280848 900076 937049 932937 736825 142831 554462 750902 249541 104336 86358 818076 909764 174869 478257 609655 354866 2190 681102 870356 834367 803491 620262 941732 575484 366379 461900 617607 423127 829860 830307 873553 36255 774045 712696 973318 259034 292016 218221 291257 987062 256548 823617 857911 796645 480693 35684 239721 77879 826660 171491 210332 506084 534947 884432 679132 910283 303562 357928 971108 15710 738642 629536 748701 249874 741749 31417 958629 861564 342561 185859 299653 779966 952648 216590 279533 148527 510459 791788 908156 207242 108715 362808 588188 690100 42868 13698 368409 438530 327705 808717 69743 180930 224853 798779 255506 202066 655725 658535 874816 467664 618243 643339 966900 449415 78825 381917 128186 79031 95973 798111 897833 240217 728311 533520 750910 975294 444840 863883 1306 877731 637307 53728 563084 632501 49409 416994 91686 22954 584287 703327 138728 915885 132987 404129 790761 28113 697158 586472 723302 906198 894495 511457 798583 9556 164371 491302 434780 713361 782203 535121 453433 510256 284859 609504 954691 814182 86467 610847 355987 992902 964010 255898 897258 162243 112266 11744 546083 304453 142567 432625 752568 225147 256327 728351 703796 946983 745584 222603 678803 394881 530094 846237 683762 794359 760878 295312 733185 859884 356193 101741 33910 501281 52687 199045 665558 979755 960329 246887 212130 603157 509899 668753 407239 970725 287463 387095 9589 111731 983641 119135 733528 885817 113052 350326 341421 498142 117855 80656 920629 888582 407958 757092 352382 375491 578914 141374 590521 97956 318610 328287 465444 486135 295022 28296 87219 314962 889476 57733 678284 1062 725727 616081 415709 34299 557484 964519 838350 561358 105559 460018 615324 613990 327465 331071 654457 392332 59735 187930 413782 549109 591361 847163 675611 439057 172584 387810 140474 64525 941873 390782 912279 674210 932269 364399 359093 834472 28676 723412 921976 978593 257979 209190 419133 381564 923335 209594 199826 893472 866188 173802 763733 62752 744802 536511 194387 862887 448974 772752 357231 650696 21443 470554 965914 401953 775238 58524 413203 875215 487499 256347 452972 820671 485830 600402 240877 456287 248500 887584 714746 305282 387141 463286 382009 703916 52109 469053 585073 210524 149266 573945 505652 8318 591731 721083 976054 177989 955810 765379 795820 216205 748812 338672 438018 951105 454174 890947 324866 632348 144352 426167 816459 546341 479364 891470 707521 844584 545043 414783 363263 109416 612617 751312 630981 473264 937505 745180 229804 726061 547651 569719 805198 738344 897432 438783 705017 440721 781707 61034 386206 174728 112555 904304 651416 141323 466189 628934 963404 907340 303064 862388 734706 753215 254423 987695 52648 882072 522311 868577 896801 652438 835974 472933 367102 176522 40235 200956 519899 284103 878473 886460 669206 428884 545768 864623 91878 235289 751423 412464 4530 231401 810895 355380 408708 94150 23520 275782 264632 278598 630918 533138 939361 648095 635196 559774 331054 638122 455753 385604 516853 421005 650955 445737 341936 816513 945656 386082 868334 542398 917646 704660 864556 947334 855980 641696 689323 774607 627322 71934 845612 889703 726872 64594 45619 837803 744797 798864 882068 372302 89916 476059 669791 327511 410893 897857 487761 975089 412858 529810 787508 310243 595147 340609 204639 751907 502846 556865 26608 232548 788182 497020 775295 179436 62171 65757 757701 361267 724175 274956 91915 811231 221256 393678 98633 78679 422323 580582 756250 104057 708291 49979 61387 701716 815242 425357 992899 871097 218382 914360 951099 435142 115211 364950 920150 304893 133132 701412 924685 602508 15256 87743 696879 463317 664632 654561 518043 566558 931450 685672 942982 836662 932593 814006 15197 705161 825019 501975 857725 614247 807867 575355 653601 977069 429065 245327 778382 346926 224522 282352 88694 507519 822782 190909 443946 370408 380912 920816 821460 314936 461559 777373 405507 372348 652966 868079 667212 1969 590259 518794 832772 499350 610012 2890 956668 84746 890124 984833 891675 721881 799888 524630 164345 362015 74407 716913 328647 365698 341672 967793 242044 59148 65141 853728 712923 283055 645264 14076 503602 321236 839553 467617 546432 445427 591038 576643 18339 385620 702239 87528 531753 120286 143995 998289 726530 404007 135818 294651 871488 38070 734264 424830 673237 63735 973465 738235 547566 88783 513689 298190 316159 311583 863465 588792 999591 295258 89659 916368 109900 398128 799308 951366 758799 89561 720393 543328 266773 243996 514477 706156 35231 673682 789511 581548 56179 31261 432734 779365 186516 102220 321880 555067 656590 59659 518765 647641 820639 227112 747312 500043 232675 943430 130165 886694 811769 60987 846616 54576 717523 568726 510533 255538 183668 828649 209032 877804 57831 226269 480502 158168 538592 588349 316485 571647 543168 597285 935071 786209 10462 273253 552279 659639 365931 535730 175744 674658 330648 710157 147155 696819 862321 696681 923466 400045 950545 368933 1402 19177 911354 124840 881475 774385 172889 341358 371662 376290 235583 270357 742671 29066 970973 228754 853981 354635 959728 773939 917647 436126 40126 858675 486586 748081 82345 92352 86191 834109 218150