1 8 2 16 3 16 4 28 5 32 6 28 7 48 8 52 9 52 10 48 11 80 12 86 13 78 14 86 15 80 16 132 17 137 18 125 19 125 20 137 21 132 22 216 23 218 24 193 25 196 26 193 27 218 28 216 29 352 30 345 31 302 32 294 33 294 34 302 35 345 36 352 37 572 38 547 39 472 40 448 41 428 42 448 43 472 44 547 45 572 46 928 47 869 48 743 49 682 50 635 51 635 52 682 53 743 54 869 55 928 56 1504 57 1385 58 1175 59 1049 60 943 61 916 62 943 63 1049 64 1175 65 1385 66 1504 67 2436 68 2214 69 1868 70 1626 71 1420 72 1323 73 1323 74 1420 75 1626 76 1868 77 2214 78 2436 79 3944 80 3549 81 2982 82 2543 83 2162 84 1941 85 1858 86 1941 87 2162 88 2543 89 2982 90 3549 91 3944 92 6384 93 5702 94 4777 95 4007 96 3333 97 2887 98 2652 99 2652 100 2887 101 3333 102 4007 103 4777 104 5702 105 6384 106 10332 107 9178 108 7673 109 6355 110 5193 111 4363 112 3845 113 3678 114 3845 115 4363 116 5193 117 6355 118 7673 119 9178 120 10332 121 16720 122 14794 123 12350 124 10131 125 8166 126 6688 127 5681 128 5184 129 5184 130 5681 131 6688 132 8166 133 10131 134 12350 135 14794 136 16720 137 27056 138 23872 139 19908 140 16216 141 12936 142 10383 143 8544 144 7460 145 7096 146 7460 147 8544 148 10383 149 12936 150 16216 151 19908 152 23872 153 27056 154 43780 155 38551 156 32127 157 26035 158 20611 159 16288 160 13062 161 10961 162 9921 163 9921 164 10961 165 13062 166 16288 167 20611 168 26035 169 32127 170 38551 171 43780 172 70840 173 62292 174 51887 175 41894 176 32983 177 25764 178 20247 179 16432 180 14191 181 13458 182 14191 183 16432 184 20247 185 25764 186 32983 187 41894 188 51887 189 62292 190 70840 191 114624 192 100695 193 83848 194 67524 195 52952 196 41012 197 31739 198 25073 199 20778 200 18686 201 18686 202 20778 203 25073 204 31739 205 41012 206 52952 207 67524 208 83848 209 100695 210 114624 211 185468 212 162821 213 135550 214 108962 215 85210 216 65594 217 50190 218 38829 219 31086 220 26614 221 25150 222 26614 223 31086 224 38829 225 50190 226 65594 227 85210 228 108962 229 135550 230 162821 231 185468 232 300096 233 263331 234 219193 235 175976 236 137349 237 105273 238 79892 239 60845 240 47391 241 38866 242 34739 243 34739 244 38866 245 47391 246 60845 247 79892 248 105273 249 137349 250 175976 251 219193 252 263331 253 300096 254 485568 255 425947 256 354517 257 284371 258 221653 259 169374 260 127789 261 96211 262 73373 263 58075 264 49313 265 46466 266 49313 267 58075 268 73373 269 96211 270 127789 271 169374 272 221653 273 284371 274 354517 275 425947 276 485568 277 785668 278 689052 279 573462 280 459720 281 357998 282 272985 283 205117 284 153162 285 114988 286 88498 287 71888 288 63907 289 63907 290 71888 291 88498 292 114988 293 153162 294 205117 295 272985 296 357998 297 459720 298 573462 299 689052 300 785668 301 1271240 302 1114751 303 927708 304 743401 305 578544 306 440519 307 330056 308 245023 309 181872 310 137025 311 107340 312 90487 313 85028 314 90487 315 107340 316 137025 317 181872 318 245023 319 330056 320 440519 321 578544 322 743401 323 927708 324 1114751 325 1271240 326 2056912 327 1803532 328 1500875 329 1202365 330 935327 331 711477 332 532022 333 393354 334 289617 335 214803 336 163561 337 131743 338 116536 339 116536 340 131743 341 163561 342 214803 343 289617 344 393354 345 532022 346 711477 347 935327 348 1202365 349 1500875 350 1803532 351 2056912 352 3328156 353 2917988 354 2428263 355 1944941 356 1512543 357 1149773 358 858611 359 633040 360 463451 361 339869 362 253319 363 196637 364 164671 365 154356 366 164671 367 196637 368 253319 369 339869 370 463451 371 633040 372 858611 373 1149773 374 1512543 375 1944941 376 2428263 377 2917988 378 3328156 379 5385072 380 4721200 381 3928792 382 3146409 383 2446424 384 1858822 385 1386835 386 1020526 387 744194 388 541407 389 397274 390 299668 391 239533 392 210932 393 210932 394 239533 395 299668 396 397274 397 541407 398 744194 399 1020526 400 1386835 401 1858822 402 2446424 403 3146409 404 3928792 405 4721200 406 5385072 407 8713232 408 7638842 409 6356682 410 5090378 411 3957398 412 3005953 413 2241302 414 1647142 415 1197894 416 866638 417 628854 418 464297 419 357462 420 297570 421 278298 422 297570 423 357462 424 464297 425 628854 426 866638 427 1197894 428 1647142 429 2241302 430 3005953 431 3957398 432 5090378 433 6356682 434 7638842 435 8713232 436 14098308 437 12359669 438 10285073 439 8235737 440 6402125 441 4861910 442 3623632 443 2660663 444 1931419 445 1391967 446 1002147 447 728484 448 544898 449 432561 450 379349 451 379349 452 432561 453 544898 454 728484 455 1002147 456 1391967 457 1931419 458 2660663 459 3623632 460 4861910 461 6402125 462 8235737 463 10285073 464 12359669 465 14098308 466 22811544 467 19998110 468 16641325 469 13324984 470 10357693 471 7864766 472 5860053 473 4300194 474 3117685 475 2241020 476 1604669 477 1153650 478 844621 479 645502 480 534437 481 498792 482 534437 483 645502 484 844621 485 1153650 486 1604669 487 2241020 488 3117685 489 4300194 490 5860053 491 7864766 492 10357693 493 13324984 494 16641325 495 19998110 496 22811544 497 36909856 498 32357349 499 26925938 500 21559506 501 16757850 502 12723338 503 9478413 504 6952615 505 5036476 506 3613828 507 2578024 508 1839176 509 1325851 510 984281 511 776494 512 678422 513 678422 514 776494 515 984281 516 1325851 517 1839176 518 2578024 519 3613828 520 5036476 521 6952615 522 9478413 523 12723338 524 16757850 525 21559506 526 26925938 527 32357349 528 36909856 529 59721404 530 52354999 531 43566772 532 34883188 533 27113432 534 20584516 535 15332788 536 11243911 537 8140492 538 5834048 539 4151332 540 2945864 541 2100588 542 1526383 543 1158804 544 954684 545 889320 546 954684 547 1158804 548 1526383 549 2100588 550 2945864 551 4151332 552 5834048 553 8140492 554 11243911 555 15332788 556 20584516 557 27113432 558 34883188 559 43566772 560 52354999 561 59721404 562 96631264 563 84711857 564 70492187 565 56441302 566 43869023 567 33304007 568 24805102 569 18186947 570 13162217 571 9425368 572 6695317 573 4733897 574 3350052 575 2397181 576 1767583 577 1386546 578 1207267 579 1207267 580 1386546 581 1767583 582 2397181 583 3350052 584 4733897 585 6695317 586 9425368 587 13162217 588 18186947 589 24805102 590 33304007 591 43869023 592 56441302 593 70492187 594 84711857 595 96631264 596 156352672 597 137066333 598 114058403 599 91323005 600 70980043 601 53884408 602 40131355 603 29420573 604 21286835 605 15235133 606 10809823 607 7624260 608 5367463 609 3799533 610 2742331 611 2069421 612 1697203 613 1578248 614 1697203 615 2069421 616 2742331 617 3799533 618 5367463 619 7624260 620 10809823 621 15235133 622 21286835 623 29420573 624 40131355 625 53884408 626 70980043 627 91323005 628 114058403 629 137066333 630 156352672 631 252983940 632 221777634 633 184550000 634 147762726 635 114846496 636 87184023 637 64929471 638 47596504 639 34432014 640 24634376 641 17465418 642 12298121 643 8627261 644 6061670 645 4308764 646 3157690 647 2464204 648 2138827 649 2138827 650 2464204 651 3157690 652 4308764 653 6061670 654 8627261 655 12298121 656 17465418 657 24634376 658 34432014 659 47596504 660 64929471 661 87184023 662 114846496 663 147762726 664 184550000 665 221777634 666 252983940 667 409336616 668 358843377 669 298607778 670 239084051 671 185823806 672 141063753 673 105053374 674 77005305 675 55700606 676 39841475 677 28232514 678 19857633 679 13897106 680 9714681 681 6832098 682 4901147 683 3678286 684 3004209 685 2789166 686 3004209 687 3678286 688 4901147 689 6832098 690 9714681 691 13897106 692 19857633 693 28232514 694 39841475 695 55700606 696 77005305 697 105053374 698 141063753 699 185823806 700 239084051 701 298607778 702 358843377 703 409336616 704 662320560 705 580620386 706 483157117 707 386844995 708 300667401 709 228242803 710 169974912 711 124589256 712 90113131 713 64445841 714 45652091 715 32086117 716 22419098 717 15617886 718 10903265 719 7703967 720 5614541 721 4360799 722 3774020 723 3774020 724 4360799 725 5614541 726 7703967 727 10903265 728 15617886 729 22419098 730 32086117 731 45652091 732 64445841 733 90113131 734 124589256 735 169974912 736 228242803 737 300667401 738 386844995 739 483157117 740 580620386 741 662320560 742 1071657180 743 939463102 744 781764197 745 625927159 746 486488133 747 369301279 748 275019857 749 201581202 750 145792961 751 104255263 752 73835541 753 51869047 754 36202997 755 25161694 756 17478413 757 12220119 758 8718077 759 6510207 760 5296937 761 4910498 762 5296937 763 6510207 764 8718077 765 12220119 766 17478413 767 25161694 768 36202997 769 51869047 770 73835541 771 104255263 772 145792961 773 201581202 774 275019857 775 369301279 776 486488133 777 625927159 778 781764197 779 939463102 780 1071657180 781 1733977744 782 1520082790 783 1264920578 784 1012770159 785 787152282 786 597538492 787 444985829 788 326156268 789 235883988 790 168666941 791 119435236 792 83875218 793 58500663 794 40595834 795 28104622 796 19507747 797 13709094 798 9940448 799 7687265 800 6635088 801 6635088 802 7687265 803 9940448 804 13709094 805 19507747 806 28104622 807 40595834 808 58500663 809 83875218 810 119435236 811 168666941 812 235883988 813 326156268 814 444985829 815 597538492 816 787152282 817 1012770159 818 1264920578 819 1520082790 820 1733977744 821 2805634928 822 2459545156 823 2046684000 824 1638695212 825 1273636980 826 966833859 827 719996220 828 527722424 829 381653476 830 272885864 831 193214940 832 135658899 833 94573716 834 65560444 835 45285120 836 31278964 837 21752900 838 15441147 839 11477900 840 9306096 841 8615348 842 9306096 843 11477900 844 15441147 845 21752900 846 31278964 847 45285120 848 65560444 849 94573716 850 135658899 851 193214940 852 272885864 853 381653476 854 527722424 855 719996220 856 966833859 857 1273636980 858 1638695212 859 2046684000 860 2459545156 861 2805634928 862 4539612676 863 3979627171 864 3311603763 865 2651463151 866 2060785639 867 1564366108 868 1164972042 869 853862765 870 617512581 871 441514221 872 312590789 873 219443154 874 152935636 875 105945391 876 73070215 877 50304027 878 34735003 879 24289944 880 17531086 881 13503273 882 11626201 883 11626201 884 13503273 885 17531086 886 24289944 887 34735003 888 50304027 889 73070215 890 105945391 891 152935636 892 219443154 893 312590789 894 441514221 895 617512581 896 853862765 897 1164972042 898 1564366108 899 2060785639 900 2651463151 901 3311603763 902 3979627171 903 4539612676 904 7345247608 905 6439171512 906 5358286907 907 4290156026 908 3334418803 909 2531193384 910 1884957699 911 1381568356 912 999139723 913 714359190 914 505742683 915 355005316 916 247361523 917 171280680 918 118013443 919 81065306 920 55706219 921 38554104 922 27241963 923 20164676 924 16296227 925 15067462 926 16296227 927 20164676 928 27241963 929 38554104 930 55706219 931 81065306 932 118013443 933 171280680 934 247361523 935 355005316 936 505742683 937 714359190 938 999139723 939 1381568356 940 1884957699 941 2531193384 942 3334418803 943 4290156026 944 5358286907 945 6439171512 946 7345247608 947 11884860288 948 10418797827 949 8669889772 950 6941616720 951 5395200428 952 4095552560 953 3049918607 954 2235413357 955 1616624478 956 1155830138 957 818266658 958 574345782 959 400139957 960 276986183 961 190718648 962 130815428 963 89602872 964 61578532 965 42867915 966 30808113 967 23642490 968 20309262 969 20309262 970 23642490 971 30808113 972 42867915 973 61578532 974 89602872 975 130815428 976 190718648 977 276986183 978 400139957 979 574345782 980 818266658 981 1155830138 982 1616624478 983 2235413357 984 3049918607 985 4095552560 986 5395200428 987 6941616720 988 8669889772 989 10418797827 990 11884860288 991 19230107900 992 16857968441 993 14028175738 994 11231770166 995 8729615014 996 6626738654 997 4934864586 998 3616962993 999 2615734842 1000 1870143610 1001 1323938650 1002 929242282 1003 647334618 1004 448011777 1005 308343210 1006 211289390 1007 144412102 1008 98775398 1009 68061466 1010 47889449 1011 35310634 1012 28450866 1013 26274538 1014 28450866 1015 35310634 1016 47889449 1017 68061466 1018 98775398 1019 144412102 1020 211289390 1021 308343210 1022 448011777 1023 647334618 1024 929242282 1025 1323938650 1026 1870143610 1027 2615734842 1028 3616962993 1029 4934864586 1030 6626738654 1031 8729615014 1032 11231770166 1033 14028175738 1034 16857968441 1035 19230107900 1036 31114968192 1037 27276765327 1038 22698064525 1039 18173384180 1040 14124811017 1041 10722283557 1042 7984770872 1043 5852356649 1044 4232328387 1045 3025925518 1046 2142130631 1047 1503472943 1048 1047297766 1049 724727211 1050 498648353 1051 341474816 1052 233057373 1053 158901777 1054 108732524 1055 75382357 1056 53963367 1057 41270922 1058 35376715 1059 35376715 1060 41270922 1061 53963367 1062 75382357 1063 108732524 1064 158901777 1065 233057373 1066 341474816 1067 498648353 1068 724727211 1069 1047297766 1070 1503472943 1071 2142130631 1072 3025925518 1073 4232328387 1074 5852356649 1075 7984770872 1076 10722283557 1077 14124811017 1078 18173384180 1079 22698064525 1080 27276765327 1081 31114968192 1082 50345076096 1083 44134732783 1084 36726239233 1085 29405151511 1086 22854421393 1087 17349014178 1088 12919622521 1089 9469298935 1090 6848030681 1091 4896018319 1092 3465990509 1093 2432593622 1094 1694445341 1095 1172452111 1096 806552681 1097 552094327 1098 376449289 1099 256126914 1100 174443521 1101 119716375 1102 83909041 1103 61647343