0 1 1 1 2 0 3 1 4 1 5 0 6 1 7 1 8 1 9 0 10 1 11 2 12 1 13 1 14 0 15 1 16 2 17 3 18 1 19 1 20 0 21 1 22 3 23 3 24 4 25 1 26 1 27 0 28 1 29 3 30 6 31 4 32 5 33 1 34 1 35 0 36 1 37 4 38 6 39 10 40 5 41 6 42 1 43 1 44 0 45 1 46 4 47 10 48 10 49 15 50 6 51 7 52 1 53 1 54 0 55 1 56 5 57 10 58 20 59 15 60 21 61 7 62 8 63 1 64 1 65 0 66 1 67 5 68 15 69 20 70 35 71 21 72 28 73 8 74 9 75 1 76 1 77 0 78 1 79 6 80 15 81 35 82 35 83 56 84 28 85 36 86 9 87 10 88 1 89 1 90 0 91 1 92 6 93 21 94 35 95 70 96 56 97 84 98 36 99 45 100 10 101 11 102 1 103 1 104 0 105 1 106 7 107 21 108 56 109 70 110 126 111 84 112 120 113 45 114 55 115 11 116 12 117 1 118 1 119 0 120 1 121 7 122 28 123 56 124 126 125 126 126 210 127 120 128 165 129 55 130 66 131 12 132 13 133 1 134 1 135 0 136 1 137 8 138 28 139 84 140 126 141 252 142 210 143 330 144 165 145 220 146 66 147 78 148 13 149 14 150 1 151 1 152 0 153 1 154 8 155 36 156 84 157 210 158 252 159 462 160 330 161 495 162 220 163 286 164 78 165 91 166 14 167 15 168 1 169 1 170 0 171 1 172 9 173 36 174 120 175 210 176 462 177 462 178 792 179 495 180 715 181 286 182 364 183 91 184 105 185 15 186 16 187 1 188 1 189 0 190 1 191 9 192 45 193 120 194 330 195 462 196 924 197 792 198 1287 199 715 200 1001 201 364 202 455 203 105 204 120 205 16 206 17 207 1 208 1 209 0 210 1 211 10 212 45 213 165 214 330 215 792 216 924 217 1716 218 1287 219 2002 220 1001 221 1365 222 455 223 560 224 120 225 136 226 17 227 18 228 1 229 1 230 0 231 1 232 10 233 55 234 165 235 495 236 792 237 1716 238 1716 239 3003 240 2002 241 3003 242 1365 243 1820 244 560 245 680 246 136 247 153 248 18 249 19 250 1 251 1 252 0 253 1 254 11 255 55 256 220 257 495 258 1287 259 1716 260 3432 261 3003 262 5005 263 3003 264 4368 265 1820 266 2380 267 680 268 816 269 153 270 171 271 19 272 20 273 1 274 1 275 0 276 1 277 11 278 66 279 220 280 715 281 1287 282 3003 283 3432 284 6435 285 5005 286 8008 287 4368 288 6188 289 2380 290 3060 291 816 292 969 293 171 294 190 295 20 296 21 297 1 298 1 299 0 300 1 301 12 302 66 303 286 304 715 305 2002 306 3003 307 6435 308 6435 309 11440 310 8008 311 12376 312 6188 313 8568 314 3060 315 3876 316 969 317 1140 318 190 319 210 320 21 321 22 322 1 323 1 324 0 325 1 326 12 327 78 328 286 329 1001 330 2002 331 5005 332 6435 333 12870 334 11440 335 19448 336 12376 337 18564 338 8568 339 11628 340 3876 341 4845 342 1140 343 1330 344 210 345 231 346 22 347 23 348 1 349 1 350 0 351 1 352 13 353 78 354 364 355 1001 356 3003 357 5005 358 11440 359 12870 360 24310 361 19448 362 31824 363 18564 364 27132 365 11628 366 15504 367 4845 368 5985 369 1330 370 1540 371 231 372 253 373 23 374 24 375 1 376 1 377 0 378 1 379 13 380 91 381 364 382 1365 383 3003 384 8008 385 11440 386 24310 387 24310 388 43758 389 31824 390 50388 391 27132 392 38760 393 15504 394 20349 395 5985 396 7315 397 1540 398 1771 399 253 400 276 401 24 402 25 403 1 404 1 405 0 406 1 407 14 408 91 409 455 410 1365 411 4368 412 8008 413 19448 414 24310 415 48620 416 43758 417 75582 418 50388 419 77520 420 38760 421 54264 422 20349 423 26334 424 7315 425 8855 426 1771 427 2024 428 276 429 300 430 25 431 26 432 1 433 1 434 0 435 1 436 14 437 105 438 455 439 1820 440 4368 441 12376 442 19448 443 43758 444 48620 445 92378 446 75582 447 125970 448 77520 449 116280 450 54264 451 74613 452 26334 453 33649 454 8855 455 10626 456 2024 457 2300 458 300 459 325 460 26 461 27 462 1 463 1 464 0 465 1 466 15 467 105 468 560 469 1820 470 6188 471 12376 472 31824 473 43758 474 92378 475 92378 476 167960 477 125970 478 203490 479 116280 480 170544 481 74613 482 100947 483 33649 484 42504 485 10626 486 12650 487 2300 488 2600 489 325 490 351 491 27 492 28 493 1 494 1 495 0 496 1 497 15 498 120 499 560 500 2380 501 6188 502 18564 503 31824 504 75582 505 92378 506 184756 507 167960 508 293930 509 203490 510 319770 511 170544 512 245157 513 100947 514 134596 515 42504 516 53130 517 12650 518 14950 519 2600 520 2925 521 351 522 378 523 28 524 29 525 1 526 1 527 0 528 1 529 16 530 120 531 680 532 2380 533 8568 534 18564 535 50388 536 75582 537 167960 538 184756 539 352716 540 293930 541 497420 542 319770 543 490314 544 245157 545 346104 546 134596 547 177100 548 53130 549 65780 550 14950 551 17550 552 2925 553 3276 554 378 555 406 556 29 557 30 558 1 559 1 560 0 561 1 562 16 563 136 564 680 565 3060 566 8568 567 27132 568 50388 569 125970 570 167960 571 352716 572 352716 573 646646 574 497420 575 817190 576 490314 577 735471 578 346104 579 480700 580 177100 581 230230 582 65780 583 80730 584 17550 585 20475 586 3276 587 3654 588 406 589 435 590 30 591 31 592 1 593 1 594 0 595 1 596 17 597 136 598 816 599 3060 600 11628 601 27132 602 77520 603 125970 604 293930 605 352716 606 705432 607 646646 608 1144066 609 817190 610 1307504 611 735471 612 1081575 613 480700 614 657800 615 230230 616 296010 617 80730 618 98280 619 20475 620 23751 621 3654 622 4060 623 435 624 465 625 31 626 32 627 1 628 1 629 0 630 1 631 17 632 153 633 816 634 3876 635 11628 636 38760 637 77520 638 203490 639 293930 640 646646 641 705432 642 1352078 643 1144066 644 1961256 645 1307504 646 2042975 647 1081575 648 1562275 649 657800 650 888030 651 296010 652 376740 653 98280 654 118755 655 23751 656 27405 657 4060 658 4495 659 465 660 496 661 32 662 33 663 1 664 1 665 0 666 1 667 18 668 153 669 969 670 3876 671 15504 672 38760 673 116280 674 203490 675 497420 676 646646 677 1352078 678 1352078 679 2496144 680 1961256 681 3268760 682 2042975 683 3124550 684 1562275 685 2220075 686 888030 687 1184040 688 376740 689 475020 690 118755 691 142506 692 27405 693 31465 694 4495 695 4960 696 496 697 528 698 33 699 34 700 1 701 1 702 0 703 1 704 18 705 171 706 969 707 4845 708 15504 709 54264 710 116280 711 319770 712 497420 713 1144066 714 1352078 715 2704156 716 2496144 717 4457400 718 3268760 719 5311735 720 3124550 721 4686825 722 2220075 723 3108105 724 1184040 725 1560780 726 475020 727 593775 728 142506 729 169911 730 31465 731 35960 732 4960 733 5456 734 528 735 561 736 34 737 35 738 1 739 1 740 0 741 1 742 19 743 171 744 1140 745 4845 746 20349 747 54264 748 170544 749 319770 750 817190 751 1144066 752 2496144 753 2704156 754 5200300 755 4457400 756 7726160 757 5311735 758 8436285 759 4686825 760 6906900 761 3108105 762 4292145 763 1560780 764 2035800 765 593775 766 736281 767 169911 768 201376 769 35960 770 40920 771 5456 772 5984 773 561 774 595 775 35 776 36 777 1 778 1 779 0 780 1 781 19 782 190 783 1140 784 5985 785 20349 786 74613 787 170544 788 490314 789 817190 790 1961256 791 2496144 792 5200300 793 5200300 794 9657700 795 7726160 796 13037895 797 8436285 798 13123110 799 6906900 800 10015005 801 4292145 802 5852925 803 2035800 804 2629575 805 736281 806 906192 807 201376 808 237336 809 40920 810 46376 811 5984 812 6545 813 595 814 630 815 36 816 37 817 1 818 1 819 0 820 1 821 20 822 190 823 1330 824 5985 825 26334 826 74613 827 245157 828 490314 829 1307504 830 1961256 831 4457400 832 5200300 833 10400600 834 9657700 835 17383860 836 13037895 837 21474180 838 13123110 839 20030010 840 10015005 841 14307150 842 5852925 843 7888725 844 2629575 845 3365856 846 906192 847 1107568 848 237336 849 278256 850 46376 851 52360 852 6545 853 7140 854 630 855 666 856 37 857 38 858 1 859 1 860 0 861 1 862 20 863 210 864 1330 865 7315 866 26334 867 100947 868 245157 869 735471 870 1307504 871 3268760 872 4457400 873 9657700 874 10400600 875 20058300 876 17383860 877 30421755 878 21474180 879 34597290 880 20030010 881 30045015 882 14307150 883 20160075 884 7888725 885 10518300 886 3365856 887 4272048 888 1107568 889 1344904 890 278256 891 324632 892 52360 893 58905 894 7140 895 7770 896 666 897 703 898 38 899 39 900 1 901 1 902 0 903 1 904 21 905 210 906 1540 907 7315 908 33649 909 100947 910 346104 911 735471 912 2042975 913 3268760 914 7726160 915 9657700 916 20058300 917 20058300 918 37442160 919 30421755 920 51895935 921 34597290 922 54627300 923 30045015 924 44352165 925 20160075 926 28048800 927 10518300 928 13884156 929 4272048 930 5379616 931 1344904 932 1623160 933 324632 934 376992 935 58905 936 66045 937 7770 938 8436 939 703 940 741 941 39 942 40 943 1 944 1 945 0 946 1 947 21 948 231 949 1540 950 8855 951 33649 952 134596 953 346104 954 1081575 955 2042975 956 5311735 957 7726160 958 17383860 959 20058300 960 40116600 961 37442160 962 67863915 963 51895935 964 86493225 965 54627300 966 84672315 967 44352165 968 64512240 969 28048800 970 38567100 971 13884156 972 18156204 973 5379616 974 6724520 975 1623160 976 1947792 977 376992 978 435897 979 66045 980 73815 981 8436 982 9139 983 741 984 780 985 40 986 41 987 1 988 1 989 0 990 1 991 22 992 231 993 1771 994 8855 995 42504 996 134596 997 480700 998 1081575 999 3124550 1000 5311735 1001 13037895 1002 17383860 1003 37442160 1004 40116600 1005 77558760 1006 67863915 1007 119759850 1008 86493225 1009 141120525 1010 84672315 1011 129024480 1012 64512240 1013 92561040 1014 38567100 1015 52451256 1016 18156204 1017 23535820 1018 6724520 1019 8347680 1020 1947792 1021 2324784 1022 435897 1023 501942 1024 73815 1025 82251 1026 9139 1027 9880 1028 780 1029 820 1030 41 1031 42 1032 1 1033 1 1034 0 1035 1 1036 22 1037 253 1038 1771 1039 10626 1040 42504 1041 177100 1042 480700 1043 1562275 1044 3124550 1045 8436285 1046 13037895 1047 30421755 1048 37442160 1049 77558760 1050 77558760 1051 145422675 1052 119759850 1053 206253075 1054 141120525 1055 225792840 1056 129024480 1057 193536720 1058 92561040 1059 131128140 1060 52451256 1061 70607460 1062 23535820 1063 30260340 1064 8347680 1065 10295472 1066 2324784 1067 2760681 1068 501942 1069 575757 1070 82251 1071 91390 1072 9880 1073 10660 1074 820 1075 861 1076 42 1077 43 1078 1 1079 1 1080 0