0 1 1 1 2 1 3 0 4 3 5 0 6 4 7 1 8 0 9 4 10 4 11 0 12 4 13 8 14 1 15 0 16 4 17 12 18 5 19 0 20 4 21 16 22 13 23 1 24 0 25 4 26 20 27 25 28 6 29 0 30 4 31 24 32 41 33 19 34 1 35 0 36 4 37 28 38 61 39 44 40 7 41 0 42 4 43 32 44 85 45 85 46 26 47 1 48 0 49 4 50 36 51 113 52 146 53 70 54 8 55 0 56 4 57 40 58 145 59 231 60 155 61 34 62 1 63 0 64 4 65 44 66 181 67 344 68 301 69 104 70 9 71 0 72 4 73 48 74 221 75 489 76 532 77 259 78 43 79 1 80 0 81 4 82 52 83 265 84 670 85 876 86 560 87 147 88 10 89 0 90 4 91 56 92 313 93 891 94 1365 95 1092 96 406 97 53 98 1 99 0 100 4 101 60 102 365 103 1156 104 2035 105 1968 106 966 107 200 108 11 109 0 110 4 111 64 112 421 113 1469 114 2926 115 3333 116 2058 117 606 118 64 119 1 120 0 121 4 122 68 123 481 124 1834 125 4082 126 5368 127 4026 128 1572 129 264 130 12 131 0 132 4 133 72 134 545 135 2255 136 5551 137 8294 138 7359 139 3630 140 870 141 76 142 1 143 0 144 4 145 76 146 613 147 2736 148 7385 149 12376 150 12727 151 7656 152 2442 153 340 154 13 155 0 156 4 157 80 158 685 159 3281 160 9640 161 17927 162 21021 163 15015 164 6072 165 1210 166 89 167 1 168 0 169 4 170 84 171 761 172 3894 173 12376 174 25312 175 33397 176 27742 177 13728 178 3652 179 429 180 14 181 0 182 4 183 88 184 841 185 4579 186 15657 187 34952 188 51324 189 48763 190 28743 191 9724 192 1639 193 103 194 1 195 0 196 4 197 92 198 925 199 5340 200 19551 201 47328 202 76636 203 82160 204 56485 205 23452 206 5291 207 532 208 15 209 0 210 4 211 96 212 1013 213 6181 214 24130 215 62985 216 111588 217 133484 218 105248 219 52195 220 15015 221 2171 222 118 223 1 224 0 225 4 226 100 227 1105 228 7106 229 29470 230 82536 231 158916 232 210120 233 187408 234 108680 235 38467 236 7462 237 650 238 16 239 0 240 4 241 104 242 1201 243 8119 244 35651 245 106666 246 221901 247 321708 248 320892 249 213928 250 90662 251 22477 252 2821 253 134 254 1 255 0 256 4 257 108 258 1301 259 9224 260 42757 261 136136 262 304437 263 480624 264 531012 265 401336 266 199342 267 60944 268 10283 269 784 270 17 271 0 272 4 273 112 274 1405 275 10425 276 50876 277 171787 278 411103 279 702525 280 852720 281 722228 282 413270 283 151606 284 32760 285 3605 286 151 287 1 288 0 289 4 290 116 291 1513 292 11726 293 60100 294 214544 295 547239 296 1006962 297 1333344 298 1253240 299 814606 300 350948 301 93704 302 13888 303 935 304 18 305 0 306 4 307 120 308 1625 309 13131 310 70525 311 265420 312 719026 313 1418065 314 2035869 315 2105960 316 1536834 317 764218 318 245310 319 46648 320 4540 321 169 322 1 323 0 324 4 325 124 326 1741 327 14644 328 82251 329 325520 330 933570 331 1965304 332 3042831 333 3439304 334 2790074 335 1578824 336 596258 337 140352 338 18428 339 1104 340 19 341 0 342 4 343 128 344 1861 345 16269 346 95382 347 396045 348 1198990 349 2684330 350 4460896 351 5475173 352 4896034 353 3115658 354 1360476 355 385662 356 65076 357 5644 358 188 359 1 360 0 361 4 362 132 363 1985 364 18010 365 110026 366 478296 367 1524510 368 3617900 369 6426200 370 8518004 371 8335338 372 5905732 373 2939300 374 981920 375 205428 376 24072 377 1292 378 20 379 0 380 4 381 136 382 2113 383 19871 384 126295 385 573678 386 1920555 387 4816890 388 9110530 389 12978900 390 13810511 391 10801766 392 6054958 393 2342396 394 591090 395 89148 396 6936 397 208 398 1 399 0 400 4 401 140 402 2245 403 21856 404 144305 405 683704 406 2398851 407 6341400 408 12728430 409 19405100 410 22328515 411 19137104 412 11960690 413 5281696 414 1573010 415 294576 416 31008 417 1500 418 21 419 0 420 4 421 144 422 2381 423 23969 424 164176 425 809999 426 2972529 427 8261955 428 17545320 429 28515630 430 35307415 431 32947615 432 22762456 433 11336654 434 3915406 435 885666 436 120156 437 8436 438 229 439 1 440 0 441 4 442 148 443 2521 444 26214 445 186032 446 954304 447 3656233 448 10660806 449 23886720 450 41244060 451 54712515 452 55276130 453 41899560 454 23297344 455 9197102 456 2458676 457 414732 458 39444 459 1729 460 22 461 0 462 4 463 152 464 2665 465 28595 466 210001 467 1118480 468 4466232 469 13633335 470 32148675 471 58789380 472 83228145 473 90583545 474 74847175 475 46059800 476 20533756 477 6374082 478 1300398 479 159600 480 10165 481 251 482 1 483 0 484 4 485 156 486 2813 487 31116 488 236215 489 1304512 490 5420536 491 17289568 492 42809481 493 82676100 494 124472205 495 145296060 496 130123305 497 87959360 498 43831100 499 15571184 500 3759074 501 574332 502 49609 503 1980 504 23 505 0 506 4 507 160 508 2965 509 33781 510 264810 511 1514513 512 6539016 513 21755800 514 56442816 515 114824775 516 183261585 517 228524205 518 220706850 519 162806535 520 89890900 521 36104940 522 10133156 523 1874730 524 209209 525 12145 526 274 527 1 528 0 529 4 530 164 531 3121 532 36594 533 295926 534 1750728 535 7843528 536 27176336 537 73732384 538 157634256 539 265937685 540 352996410 541 366002910 542 292929840 543 177850260 544 79936040 545 25704340 546 5633804 547 783541 548 61754 549 2254 550 24 551 0 552 4 553 168 554 3281 555 39559 556 329707 557 2015538 558 9358041 559 33715352 560 95488184 561 214077072 562 380762460 563 536257995 564 594527115 565 513636690 566 340656795 567 169826940 568 61809280 569 15766960 570 2658271 571 270963 572 14399 573 298 574 1 575 0 576 4 577 172 578 3445 579 42680 580 366301 581 2311464 582 11108769 583 41558880 584 122664520 585 287809456 586 538396716 587 802195680 588 947523525 589 879639600 590 633586635 591 347677200 592 141745320 593 41471300 594 8292075 595 1054504 596 76153 597 2552 598 25 599 0 600 4 601 176 602 3613 603 45961 604 405860 605 2641171 606 13124307 607 50916921 608 156379872 609 383297640 610 752473788 611 1182958140 612 1483781520 613 1474166715 614 1147223325 615 688333995 616 311572260 617 103280580 618 24059035 619 3712775 620 347116 621 16951 622 323 623 1 624 0 625 4 626 180 627 3785 628 49406 629 448540 630 3007472 631 15435771 632 62025690 633 197938752 634 505962160 635 1040283244 636 1721354856 637 2285977200 638 2421690240 639 2026862925 640 1321920630 641 659249460 642 245025900 643 65530335 644 12004850 645 1401620 646 93104 647 2875 648 26 649 0 650 4 651 184 652 3961 653 53019 654 494501 655 3413332 656 18076942 657 75149997 658 248855673 659 662342032 660 1423580884 661 2473828644 662 3468935340 663 3905471760 664 3501029640 665 2469143955 666 1347583455 667 556598160 668 168810915 669 36063885 670 5114395 671 440220 672 19826 673 349 674 1 675 0 676 4 677 188 678 4141 679 56804 680 543907 681 3861872 682 21084414 683 90585768 684 310881363 685 860280784 686 1929543044 687 3514111888 688 5190290196 689 6191448960 690 5922719880 691 4496006880 692 2669504085 693 1215847620 694 413836815 695 101594220 696 17119245 697 1841840 698 112930 699 3224 700 27 701 0 702 4 703 192 704 4325 705 60765 706 596926 707 4356373 708 24497746 709 108662710 710 386031360 711 1109136457 712 2591885076 713 4937692772 714 7664118840 715 9660384300 716 9828191640 717 7997036520 718 5138648040 719 2563431075 720 970434975 721 270405135 722 53183130 723 6956235 724 553150 725 23050 726 376 727 1 728 0 729 4 730 196 731 4513 732 64906 733 653730 734 4900280 735 28359618 736 129747124 737 476617128 738 1420017820 739 3452165860 740 6867235816 741 11178230728 742 14850674496 743 16019640600 744 13919756400 745 9634654920 746 5232935160 747 2186282595 748 684241950 749 154777350 750 24075480 751 2394990 752 135980 753 3600 754 28 755 0 756 4 757 200 758 4705 759 69231 760 714495 761 5497206 762 32715991 763 154244870 764 585279838 765 1806049180 766 4561302317 767 9459120892 768 16115923500 769 22514793336 770 25680024900 771 23747948040 772 17631691440 773 10371583200 774 4749713670 775 1654676925 776 425182485 777 77258610 778 9351225 779 689130 780 26650 781 404 782 1 783 0 784 4 785 204 786 4901 787 73744 788 779401 789 6150936 790 37616271 791 182604488 792 715026962 793 2282666308 794 5981320137 795 12911286752 796 22983159316 797 33693024064 798 40530699396 799 39767588640 800 31551447840 801 20006238120 802 9982648830 803 3840959520 804 1109424435 805 232035960 806 33426705 807 3084120 808 162630 809 4004 810 29 811 0 812 4 813 208 814 5101 815 78449 816 848632 817 6865431 818 43113477 819 215320479 820 869271832 821 2867946146 822 7787369317 823 17472589069 824 32442280208 825 49808947564 826 63045492732 827 65447613540 828 55299395880 829 37637929560 830 20354232030 831 8590673190 832 2764101360 833 657218445 834 110685315 835 12435345 836 851760 837 30654 838 433 839 1 840 0 841 4 842 212 843 5305 844 83350 845 922376 846 7644832 847 49264413 848 252936750 849 1051876320 850 3582973108 851 10070035625 852 23453909206 853 45353566960 854 72792106880 855 96738516796 856 105978312936 857 95066984520 858 69189377400 859 40360470150 860 18573322020 861 6605060880 862 1766642880 863 342721275 864 45862050 865 3935880 866 193284 867 4437 868 30 869 0 870 4 871 216 872 5513 873 88451 874 1000825 875 8493464 876 56129844 877 296050227 878 1267196799 879 4452244940 880 12937981771 881 31241278523 882 62826156029 883 105234387088 884 146547464360 885 169023805668 886 160514598060 887 124488773280 888 77998399710 889 38927554050 890 15195734070 891 4530744240 892 999939720 893 156547365 894 16371225 895 1045044 896 35091 897 463 898 1 899 0 900 4 901 220 902 5725 903 93756 904 1084175 905 9415840 906 63774676 907 345314640 908 1520133549 909 5504121260 910 16520954879 911 41311314148 912 86280065235 913 150587954048 914 219339571240 915 265762322464 916 266492910996 917 219555757800 918 147187777110 919 79288024200 920 33769056090 921 11135805120 922 2766582600 923 499268640 924 62233275 925 4980924 926 228375 927 4900 928 31 929 0 930 4 931 224 932 5941 933 99269 934 1172626 935 10416665 936 72268140 937 401444484 938 1816183776 939 6771318059 940 20973199819 941 54249295919 942 117521343758 943 213414110077 944 324573958328 945 412309786824 946 435516716664 947 380070355860 948 271676550390 949 157286423910 950 72696610140 951 26331539190 952 7297326840 953 1499208360 954 218780640 955 21352149 956 1273419 957 39991 958 494 959 1 960 0 961 4 962 228 963 6161 964 104994 965 1266382 966 11500840 967 81683980 968 465219160 969 2161498416 970 8291451608 971 26477321079 972 70770250798 973 158832657906 974 299694175312 975 475161912376 976 631649358064 977 701279039128 978 646563266856 979 491232308190 980 304474201020 981 151984634340 982 60100595280 983 18433131960 984 4265790960 985 718049280 986 83585424 987 6254343 988 268366 989 5394 990 32