1000
0 884800 46562 641487 864612 131694 969666 306519 214437 668787 225983 319089 205756 426693 569610 816917 12426 718544 623833 134561 208285 944528 679215 58565 255276 663463 615520 863361 678578 128837 698230 170113 538543 435326 869035 256278 295749 788765 870754 886176 421440 811865 509511 294374 858164 261922 8167 322146 519410 639673 517608 218650 743255 558478 184309 260222 225724 370570 240892 448434 970129 220243 303962 652881 717858 788626 241864 559537 489300 752647 568595 686576 577975 191882 785628 501842 466716 598551 811065 759624 496524 617016 895007 968244 953893 772455 926031 968443 702169 948847 937148 64112 807156 448961 762964 379210 214576 707998 684625 229721 809730 751526 507210 559872 899090 519361 864176 572901 317679 828725 470381 357476 822724 409243 33631 219002 656924 471374 467319 787016 920225 946523 814997 10471 637246 729698 768510 691028 880118 108837 318296 583326 849964 48355 850848 279964 825389 681681 589225 181932 77115 124600 926743 938149 348714 26729 183868 280272 456416 648320 193224 500197 607198 159746 278857 656039 948891 187087 559659 432759 133616 407371 679415 223338 962292 729191 472397 346320 452638 912854 530063 47516 651773 167305 816891 639896 497180 35581 862377 587247 700629 329214 673791 633281 175278 868069 16269 918391 675055 563808 130392 482695 501845 922765 521171 998828 217812 772962 518959 359773 307527 728109 852085 27968 278466 812041 926861 526908 570096 879430 866272 194818 821975 650462 552036 81819 797426 429155 951819 805106 531574 798242 610961 665761 579319 988977 248758 821408 459622 127149 816869 452740 377306 340283 668615 40087 847591 470364 957240 737582 65925 748467 428894 883516 682405 697414 301327 929963 61628 975280 770418 891529 506398 217513 992956 104970 845140 530754 749262 989788 163321 6486 593489 575978 968234 941385 836084 824812 776147 170144 283840 937258 125373 523962 666625 505423 204955 390715 925186 77250 713295 102680 134496 103408 236567 963726 456649 357725 714479 151049 398234 944194 835657 213143 911713 620378 412820 695904 545425 53906 677270 831933 545185 297378 991125 36594 389927 168503 664185 837534 999315 527956 368140 500272 717382 464791 78852 444248 41234 284289 482043 939132 355567 174721 564666 791755 445024 428094 257107 783234 7256 333913 718470 387748 198687 111744 627580 314112 952291 260554 105748 479259 40622 869697 579344 569027 548205 633036 847769 17948 145910 813388 688643 33605 553799 381735 586861 923863 10707 25361 785863 693047 131252 293440 387349 84067 22609 142307 661308 79947 968481 579658 776617 532317 583858 727109 216051 947318 877551 59178 339415 821284 947236 251640 532493 579994 184252 172024 551758 834922 247895 540478 378915 644576 490518 780769 831699 530459 40398 862378 262656 586896 38255 641767 802085 895542 135966 759689 226586 784612 398247 440326 930535 958920 2429 585447 425611 626259 583406 698937 905985 765367 174670 716653 333497 864381 328997 796069 960630 33169 931312 737594 951852 92626 255940 529078 287602 444753 460843 70278 420646 96892 784874 505789 369147 260653 957568 718436 143902 537095 164779 707138 735826 558144 904450 409505 36158 704235 217790 566478 232251 975437 422665 107014 195044 343171 736542 923124 677486 730788 147343 334488 566188 623463 58767 72872 525711 252962 895817 261478 537183 666508 621370 498632 667188 370816 337471 483966 708656 822601 655312 935984 191229 993314 99558 129468 820071 35706 468202 368631 826273 724229 388827 833534 285549 304419 369420 617540 385162 855605 103735 817903 905608 697822 517563 724844 133249 345919 336491 476524 733867 750646 788790 110495 871662 955005 133887 643332 359153 448538 472700 208267 608180 892003 175899 520104 492390 584693 728080 58227 645099 685766 357145 745290 528580 978262 715605 267060 965220 796498 359572 667067 216996 639613 803921 386342 110039 528074 326088 281672 112986 216893 130875 717876 773079 394312 477213 969806 993298 625599 431075 704934 483876 712611 229535 331527 46307 828111 682491 891563 650435 640199 563406 678704 881420 784902 715196 404321 374787 709643 512678 954289 169295 399485 537186 365768 419635 838309 175689 453263 969917 838134 677460 455699 219895 620453 518160 628869 659782 575691 404924 891412 162159 412272 115148 985388 264785 617745 697805 764905 155072 893381 913823 36631 980110 273384 103297 394373 252522 961989 616956 335408 59683 86883 243215 62352 662758 433235 846356 42784 831663 188766 448453 766105 115188 603867 54113 806917 319196 650916 788667 399831 261899 865038 224056 95970 146442 800507 199796 298727 654744 957055 116467 239048 127198 790732 455910 747199 969851 349 588287 941880 662002 115077 16392 815121 634485 847656 440654 222682 210819 353194 559208 207647 529745 265683 198578 228525 649089 120205 229582 534370 681728 422967 85432 239296 983135 498114 272017 612759 835538 245788 807526 243478 839561 813510 63515 998300 677482 148909 635819 496851 246829 986493 202099 704293 385853 496918 81323 326236 523057 731525 778663 693283 498733 441882 958678 804367 941325 988591 40935 447019 888982 648374 408960 419613 886444 666173 29740 165943 79431 947757 185209 761271 875229 150439 555562 316749 63395 995215 78841 111093 868779 640357 593037 948956 565735 163781 983419 801705 635856 647715 128364 802899 185999 386440 650896 220105 240906 153963 755733 498928 579645 658969 94748 735086 187448 939237 548174 412197 615030 36741 473653 512246 591256 184443 656169 344094 934230 783339 364182 329540 154496 227287 697676 489066 559683 808101 512914 931373 212512 850797 898273 327047 679818 708475 65103 827086 511749 595441 831032 523258 202455 811849 401699 881418 913208 350289 613485 211712 889400 267878 248129 103572 982242 499477 813970 230047 763681 630542 136797 423870 434185 569577 302545 979639 72088 29504 946207 25866 763216 456798 580849 25004 89783 405794 578324 870628 905914 145002 368165 606344 1556 195926 877671 764499 18259 587697 504646 495164 450814 683012 550860 754288 95007 817042 399295 280268 179506 965891 980800 764849 681193 776034 865923 396390 926287 670765 216568 638388 815079 156846 886029 534040 190349 894605 388377 403487 861346 225070 30801 17897 959971 839189 826805 815066 420153 707116 627801 877897 686061 425074 147564 561544 729762 89663 469911 552503 128548 995417 559870 578338 702464 283560 620888 505898 431447 579700 638454 52638 148451 852294 42136 768564 945174 711577 291292 593561 28288 536148 289735 372573 584966 492295 955792 382721 533873 261699 789604 626666 501085 716243 782068 800365 964196 277165 242741 99446 96719 430935 268175 726191 638133 729369 9583 754453 601718 211390 473630 54525 684745 967556 285295 961070 179493 29118 221145 375825 118057 107977 988839 352340 453269 111357 776322 935394 300827 72865 128380 106976 154077 233915 624864 148917 634292 802245 404477 305242 157857 72163 216547 183124 307384 873288 85004 631209 28863 765493 349259 0