0 2 1 0 2 8 3 50 4 132 5 414 6 171 7 659 8 96 9 361 10 12311 11 7224 12 5896 13 2954 14 5804 15 72387 16 12756 17 1292 18 4332 19 3715 20 2704 21 1887 22 5780 23 9837 24 11721 25 1094 26 70067 27 32610 28 57658 29 26146 30 167389 31 94957 32 36588 33 19663 34 35588 35 9627 36 108296 37 51653 38 38147 39 54788 40 81871 41 15502 42 142576 43 60392 44 191260 45 140588 46 12006 47 57876 48 22309 49 161849 50 213717 51 69486 52 88482 53 102904 54 409811 55 9155 56 79042 57 210341 58 141585 59 441444 60 45047 61 122709 62 56600 63 132904 64 806 65 26006 66 614066 67 216441 68 33639 69 888513 70 151853 71 179878 72 85239 73 255590 74 48394 75 20611 76 187404 77 184695 78 91671 79 443105 80 257494 81 816242 82 163117 83 133392 84 138425 85 176049 86 253434 87 107777 88 583263 89 424124 90 49919 91 762047 92 73055 93 87519 94 848820 95 1321593 96 505166 97 64173 98 164101 99 701998 100 1072 101 911208 102 151416 103 662495 104 52709 105 1628914 106 1012296 107 1720570 108 53837 109 289371 110 711491 111 948075 112 2930 113 2606599 114 192719 115 1518504 116 19357 117 478828 118 149626 119 31512 120 283586 121 253212 122 729939 123 2702997 124 636827 125 1390221 126 568548 127 989824 128 1207752 129 439710 130 566067 131 130210 132 671081 133 727984 134 1719070 135 1978249 136 583184 137 400139 138 1296206 139 1436 140 972964 141 1138482 142 95876 143 2454766 144 577820 145 419309 146 3843188 147 2826401 148 5775642 149 1328767 150 619441 151 152815 152 10557064 153 1030310 154 22166 155 11852405 156 4796605 157 1475107 158 190116 159 468236 160 8487485 161 411590 162 2489884 163 2936135 164 2371768 165 5978290 166 464414 167 1860470 168 11042351 169 25073 170 916481 171 845594 172 473139 173 1156887 174 699027 175 560671 176 1179803 177 996960 178 2015073 179 2919369 180 2664246 181 444518 182 9577643 183 80326 184 1193876 185 2033039 186 1586576 187 1010789 188 222278 189 2513519 190 1136011 191 1782901 192 272879 193 29348 194 2745063 195 19077 196 1689457 197 4341791 198 11596401 199 547757 200 1699675 201 2247580 202 3961787 203 8224695 204 457400 205 4279727 206 5492775 207 1205677 208 286337 209 752150 210 3006874 211 2728597 212 4640544 213 4791677 214 579723 215 3942661 216 2431533 217 3388786 218 1944606 219 2692552 220 4233768 221 14013382 222 2209253 223 1192857 224 963989 225 290644 226 16846441 227 799145 228 430794 229 10404301 230 5410219 231 3586443 232 1154049 233 1828350 234 6608859 235 10823714 236 396641 237 2395969 238 5019699 239 10285274 240 9429037 241 11263506 242 690829 243 842366 244 6681502 245 866516 246 3119679 247 490657 248 2726786 249 3586425 250 2165864 251 6023651 252 12238296 253 2039554 254 2285407 255 1115468 256 39739 257 890104 258 8297166 259 9962836 260 12812739 261 2532183 262 91119 263 1638264 264 576754 265 1802417 266 84269 267 10149164 268 4276679 269 5369304 270 5212723 271 2577680 272 2121779 273 372875 274 5503970 275 767052 276 8839144 277 26895063 278 3683556 279 4366983 280 15167473 281 12207270 282 10803120 283 8239584 284 4766284 285 11125001 286 506845 287 15797375 288 13230442 289 19304420 290 9156713 291 6060502 292 4124472 293 19375220 294 2012458 295 754846 296 17331 297 2210840 298 4717150 299 984593 300 3260474 301 15587819 302 169924 303 5423604 304 6672253 305 5418268 306 8566501 307 1630727 308 4872804 309 335631 310 3242229 311 4478147 312 14357452 313 34054678 314 2728779 315 13528975 316 14150256 317 3656434 318 3315691 319 12450914 320 25995140 321 1173253 322 2409299 323 2307933 324 16534269 325 2400044 326 771932 327 352713 328 510653 329 36180782 330 151012 331 8195980 332 4733507 333 4923921 334 1587364 335 163594 336 728119 337 40003953 338 3695620 339 15130002 340 647312 341 217687 342 21593071 343 10981113 344 1192704 345 9774357 346 5755690 347 874225 348 14709738 349 18271704 350 7450925 351 4453563 352 1302695 353 27788558 354 24928235 355 9370111 356 9804474 357 24862052 358 4533823 359 117236 360 16139942 361 2083046 362 2089559 363 15122727 364 215585 365 22536985 366 318846 367 25288987 368 26732174 369 11120438 370 28552850 371 5600444 372 19293212 373 8890545 374 2831133 375 86834546 376 7942283 377 6803945 378 1479714 379 42415990 380 8102074 381 6194095 382 4513157 383 17425235 384 12401134 385 5961589 386 20702085 387 24979967 388 338332 389 5762837 390 2708123 391 49840082 392 1542034 393 8285079 394 5183643 395 30140127 396 6772774 397 9688200 398 4182248 399 1776226 400 23544761 401 13274309 402 15294859 403 3133936 404 899303 405 1139153 406 8711167 407 6336081 408 1990894 409 27877836 410 1719264 411 9388896 412 3420275 413 5464495 414 134687 415 1601559 416 34389604 417 65736995 418 453943 419 29317501 420 22735 421 36997345 422 14082930 423 3953687 424 779607 425 2650198 426 17160308 427 12156039 428 2101432 429 35002630 430 11923012 431 7222314 432 10211477 433 7435148 434 22337764 435 18083605 436 21374395 437 57813671 438 16848764 439 82888054 440 359152 441 11273660 442 13511905 443 9700554 444 17207749 445 1512393 446 21232098 447 18614292 448 6250797 449 2702550 450 9275592 451 7362739 452 6001467 453 13983582 454 17516999 455 3857676 456 10265532 457 3290041 458 9951102 459 3844096 460 7961143 461 36636719 462 15280821 463 36015485 464 47669785 465 93276101 466 882127 467 3802957 468 6323100 469 9992488 470 23695596 471 24013939 472 50681673 473 7149567 474 5777803 475 9208736 476 3256658 477 18898467 478 32435710 479 2550406 480 85285264 481 4650303 482 28688680 483 565139 484 48785826 485 9013449 486 8341336 487 15761377 488 1768542 489 40077287 490 37491772 491 50004028 492 9209687 493 43779496 494 34287751 495 8410905 496 2032392 497 12802509 498 922712 499 4075001 500 14655991 501 5487045 502 676270 503 218333 504 30774002 505 43312556 506 7541971 507 17532410 508 4505459 509 36792144 510 4557801 511 4819095 512 35800545 513 12236860 514 1168932 515 2575029 516 8358862 517 3150594 518 14289 519 44817891 520 24713822 521 22602599 522 48409943 523 2083119 524 37181476 525 31377691 526 1359709 527 434627 528 25993150 529 15423383 530 18612939 531 3324837 532 76519048 533 50567460 534 99234391 535 14766681 536 8226713 537 32180761 538 7045970 539 24358832 540 15587984 541 8775608 542 12531245 543 9726241 544 12280025 545 1984878 546 25233812 547 3242721 548 15536388 549 56775235 550 75605324 551 7021652 552 30166038 553 4124688 554 56205248 555 6869272 556 19144627 557 24287092 558 39737999 559 34490264 560 184613999 561 10646518 562 14231735 563 2765744 564 2514380 565 27193367 566 21948945 567 39321340 568 16209308 569 37626128 570 2766441 571 9974783 572 42229245 573 20585979 574 34391590 575 66149005 576 26141054 577 18075362 578 2878520 579 11020702 580 62938944 581 27451791 582 15002975 583 7064523 584 1885752 585 6178657 586 81925441 587 42665545 588 6842948 589 14466422 590 79427963 591 7472965 592 2178097 593 6560334 594 42811800 595 7725035 596 30012754 597 147307318 598 688423 599 79619324 600 22674483 601 19325164 602 4831871 603 5555330 604 43284630 605 39570781 606 26756176 607 3770593 608 29135122 609 61179322 610 277912 611 11908411 612 16207114 613 13227171 614 851557 615 36595421 616 46011445 617 9647677 618 10500904 619 39300562 620 58183795 621 104256 622 202463929 623 58011699 624 8564212 625 15381217 626 12421683 627 20652667 628 59705636 629 70165693 630 38323122 631 12249210 632 34423495 633 92875897 634 92715409 635 65826543 636 19335979 637 95748924 638 18003760 639 2478510 640 4977993 641 11899333 642 15649723 643 8461795 644 57312692 645 178957679 646 6032378 647 6656643 648 6703632 649 8556135 650 9697354 651 42779721 652 129474880 653 89572718 654 9328955 655 37910886 656 14971918 657 54412666 658 42829405 659 12034318 660 8668248 661 67683758 662 36475611 663 11483450 664 15335418 665 47038781 666 17108516 667 42243767 668 32021523 669 119254534 670 55652052 671 9317339 672 510865 673 8378945 674 41559383 675 21432525 676 16381569 677 13784168 678 47662187 679 95299190 680 2947953 681 140545770 682 31026924 683 17931782 684 12925515 685 52179122 686 70937652 687 22885290 688 20081340 689 4866485 690 50837490 691 18199391 692 43986601 693 16452974 694 212906216 695 22040684 696 5256661 697 16033965 698 1566311 699 11727329 700 14542433 701 86328865 702 107948143 703 130543312 704 63359830 705 48739802 706 16669072 707 35599933 708 49285331 709 49051862 710 33039651 711 95543073 712 93279672 713 96103820 714 67281987 715 74157075 716 5090076 717 3332088 718 40248300 719 43301379 720 24917249 721 104088701 722 74422569 723 21591386 724 115238373 725 17130474 726 8806328 727 30897163 728 14929800 729 246370 730 106272848 731 11390593 732 62986269 733 8839366 734 1546485 735 31314374 736 44349161 737 138761910 738 24333454 739 8362642 740 4747443 741 89419214 742 29803017 743 86301331 744 60006980 745 11390576 746 11515377 747 22946240 748 122431036 749 8872545 750 55419809 751 58225430 752 29129385 753 23121799 754 61432939 755 811720 756 8081827 757 99010890 758 2159020 759 14836396 760 12948794 761 112279671 762 36718870 763 34581642 764 2611246 765 292448598 766 98589185 767 42756445 768 23701885 769 117152019 770 56362036 771 12085278 772 121885369 773 40861763 774 51087691 775 60307140 776 35812137 777 14012731 778 27820441 779 57268861 780 31360750 781 40206391 782 92816591 783 9547975 784 79850824 785 82634296 786 47374537 787 41509348 788 87967695 789 12339223 790 59648319 791 69490330 792 7423134 793 44572736 794 10433533 795 104125915 796 80697639 797 30245392 798 21766703 799 47793895 800 86770653 801 72035839 802 9771847 803 40611477 804 30862010 805 102316871 806 6076485 807 30397186 808 7110131 809 59723537 810 44579587 811 40566022 812 4239992 813 65863467 814 34371303 815 4694724 816 23701667 817 18416119 818 112397240 819 113093258 820 1622680 821 68160188 822 57239837 823 13968444 824 95126383 825 118454704 826 84166095 827 13646160 828 42968092 829 45681288 830 92137668 831 11788291 832 144354719 833 50108924 834 70622668 835 136807921 836 1810797 837 60380090 838 98454561 839 60107600 840 262922968 841 16045517 842 61783383 843 7505401 844 66931281 845 20882150 846 22350549 847 15265358 848 12960056 849 256272926 850 8765113 851 15083463 852 5297146 853 79270180 854 81715431 855 7532225 856 13476522 857 12701843 858 23972617 859 51311626 860 51612166 861 22896014 862 174567236 863 28300435 864 70130733 865 6050666 866 40986722 867 6346302 868 126382701 869 144263377 870 25074903 871 175884361 872 35533078 873 19379256 874 28380559 875 204110397 876 6600499 877 14294906 878 62701323 879 39268853 880 19919590 881 91966832 882 31287168 883 218989229 884 117993501 885 64270427 886 30452439 887 22054157 888 28180791 889 15320773 890 18459657 891 8885255 892 30665692 893 59097026 894 250454931 895 290156937 896 22420673 897 170600867 898 130951609 899 57628489 900 82825923 901 45009960 902 35732506 903 18266300 904 451993799 905 122200421 906 53235258 907 54248587 908 270097554 909 32531879 910 51549872 911 17060111 912 81921909 913 139491445 914 142657632 915 9409608 916 72753590 917 5053286 918 15408071 919 37950403 920 361411145 921 23277884 922 42982263 923 220098998 924 174266868 925 109626148 926 39861710 927 3481601 928 15779307 929 64338426 930 37470470 931 13457077 932 140264095 933 166578030 934 243589682 935 49869539 936 32587858 937 33942496 938 101772587 939 153507639 940 148572707 941 98116524 942 45575225 943 63598011 944 43874122 945 20613064 946 49706958 947 55015262 948 114137709 949 87350268 950 78680157 951 30644084 952 26852545 953 36611470 954 34149335 955 100499832 956 8431823 957 126725887 958 33169233 959 24431874 960 159557784 961 16302026 962 57766922 963 172005940 964 4697500 965 44022653 966 80731599 967 80678785 968 25088355 969 101674016 970 158493694 971 34316964 972 230293337 973 4927658 974 89331253 975 3727520 976 288759050 977 95532618 978 164020080 979 40798715 980 123155 981 97403069 982 23025697 983 30428311 984 36476101 985 100342510 986 14392431 987 83783287 988 209599923 989 600637582 990 19292364 991 39209760 992 662150301 993 196954889 994 372636529 995 91736138 996 8193274 997 171208148 998 103671138 999 137310491