0 1 1 1 2 1 3 1 4 2 5 1 6 1 7 3 8 3 9 1 10 1 11 4 12 6 13 4 14 1 15 1 16 5 17 10 18 10 19 5 20 1 21 1 22 6 23 15 24 21 25 15 26 6 27 1 28 1 29 7 30 21 31 38 32 38 33 21 34 7 35 1 36 1 37 8 38 28 39 62 40 82 41 62 42 28 43 8 44 1 45 1 46 9 47 36 48 95 49 158 50 158 51 95 52 36 53 9 54 1 55 1 56 10 57 45 58 138 59 278 60 356 61 278 62 138 63 45 64 10 65 1 66 1 67 11 68 55 69 192 70 459 71 724 72 724 73 459 74 192 75 55 76 11 77 1 78 1 79 12 80 66 81 259 82 716 83 1359 84 1690 85 1359 86 716 87 259 88 66 89 12 90 1 91 1 92 13 93 78 94 340 95 1072 96 2388 97 3612 98 3612 99 2388 100 1072 101 340 102 78 103 13 104 1 105 1 106 14 107 91 108 436 109 1546 110 3977 111 7143 112 8731 113 7143 114 3977 115 1546 116 436 117 91 118 14 119 1 120 1 121 15 122 105 123 549 124 2165 125 6331 126 13270 127 19404 128 19404 129 13270 130 6331 131 2165 132 549 133 105 134 15 135 1 136 1 137 16 138 120 139 680 140 2953 141 9702 142 23346 143 40145 144 48213 145 40145 146 23346 147 9702 148 2953 149 680 150 120 151 16 152 1 153 1 154 17 155 136 156 830 157 3943 158 14391 159 39248 160 78079 161 110846 162 110846 163 78079 164 39248 165 14391 166 3943 167 830 168 136 169 17 170 1 171 1 172 18 173 153 174 1001 175 5161 176 20758 177 63412 178 144004 179 237926 180 281885 181 237926 182 144004 183 63412 184 20758 185 5161 186 1001 187 153 188 18 189 1 190 1 191 19 192 171 193 1194 194 6646 195 29218 196 99044 197 253642 198 481202 199 665936 200 665936 201 481202 202 253642 203 99044 204 29218 205 6646 206 1194 207 171 208 19 209 1 210 1 211 20 212 190 213 1410 214 8429 215 40255 216 150128 217 429234 218 923675 219 1474030 220 1724817 221 1474030 222 923675 223 429234 224 150128 225 40255 226 8429 227 1410 228 190 229 20 230 1 231 1 232 21 233 210 234 1651 235 10553 236 54419 237 221715 238 701334 239 1694020 240 3080278 241 4167649 242 4167649 243 3080278 244 1694020 245 701334 246 221715 247 54419 248 10553 249 1651 250 210 251 21 252 1 253 1 254 22 255 231 256 1918 257 13053 258 72337 259 319902 260 1111066 261 2984286 262 6118161 263 9463554 264 10955956 265 9463554 266 6118161 267 2984286 268 1111066 269 319902 270 72337 271 13053 272 1918 273 231 274 22 275 1 276 1 277 23 278 253 279 2212 280 15978 281 94711 282 452180 283 1712577 284 5074010 285 11617824 286 20333473 287 26967566 288 26967566 289 20333473 290 11617824 291 5074010 292 1712577 293 452180 294 94711 295 15978 296 2212 297 253 298 23 299 1 300 1 301 24 302 276 303 2535 304 19366 305 122331 306 627401 307 2576027 308 8358655 309 21197983 310 41586849 311 62568296 312 71747613 313 62568296 314 41586849 315 21197983 316 8358655 317 2576027 318 627401 319 122331 320 19366 321 2535 322 276 323 24 324 1 325 1 326 25 327 300 328 2888 329 23272 330 156070 331 856196 332 3790834 333 13387017 334 37325559 335 81395474 336 137660443 337 179363219 338 179363219 339 137660443 340 81395474 341 37325559 342 13387017 343 3790834 344 856196 345 156070 346 23272 347 2888 348 300 349 25 350 1 351 1 352 26 353 325 354 3272 355 27738 356 196899 357 1150890 358 5469521 359 20904057 360 63662026 361 153157333 362 288775366 363 423827204 364 481927039 365 423827204 366 288775366 367 153157333 368 63662026 369 20904057 370 5469521 371 1150890 372 196899 373 27738 374 3272 375 325 376 26 377 1 378 1 379 27 380 351 381 3689 382 32823 383 245881 384 1526029 385 7751809 386 31905865 387 105514211 388 278175095 389 580348439 390 951773099 391 1220645380 392 1220645380 393 951773099 394 580348439 395 278175095 396 105514211 397 31905865 398 7751809 399 1526029 400 245881 401 32823 402 3689 403 351 404 27 405 1 406 1 407 28 408 378 409 4140 410 38574 411 304186 412 1998238 413 10809466 414 47701082 415 170414662 416 489387583 417 1122098059 418 2041189827 419 2930052082 420 3306721747 421 2930052082 422 2041189827 423 1122098059 424 489387583 425 170414662 426 47701082 427 10809466 428 1998238 429 304186 430 38574 431 4140 432 378 433 28 434 1 435 1 436 29 437 406 438 4626 439 45056 440 373086 441 2586826 442 14851369 443 69988201 444 268854338 445 836500223 446 2095063691 447 4198875671 448 6698172187 449 8469670541 450 8469670541 451 6698172187 452 4198875671 453 2095063691 454 836500223 455 268854338 456 69988201 457 14851369 458 2586826 459 373086 460 45056 461 4626 462 406 463 29 464 1 465 1 466 30 467 435 468 5149 469 52318 470 453971 471 3313618 472 20129407 473 100940381 474 415200370 475 1392863995 476 3789690574 477 8316898463 478 14647025315 479 20610187227 480 23103546417 481 20610187227 482 14647025315 483 8316898463 484 3789690574 485 1392863995 486 415200370 487 100940381 488 20129407 489 3313618 490 453971 491 52318 492 5149 493 435 494 30 495 1 496 1 497 31 498 465 499 5710 500 60431 501 548339 502 4203650 503 26944659 504 143310446 505 628826838 506 2264610212 507 6660304419 508 15916900906 509 30759314533 510 47858330027 511 59751268929 512 59751268929 513 47858330027 514 30759314533 515 15916900906 516 6660304419 517 2264610212 518 628826838 519 143310446 520 26944659 521 4203650 522 548339 523 60431 524 5710 525 465 526 31 527 1 528 1 529 32 530 496 531 6310 532 69449 533 657816 534 5284919 535 35654481 536 200544395 537 935499747 538 3602530299 539 11401550962 540 29521754623 541 62255678444 542 106471029184 543 147149569937 544 163954719933 545 147149569937 546 106471029184 547 62255678444 548 29521754623 549 11401550962 550 3602530299 551 935499747 552 200544395 553 35654481 554 5284919 555 657816 556 69449 557 6310 558 496 559 32 560 1 561 1 562 33 563 528 564 6951 565 79447 566 784148 567 6589217 568 46679837 569 276920111 570 1369050618 571 5617414032 572 19053747924 573 53208497715 574 121823730193 575 227758858649 576 346455647466 577 427620043188 578 427620043188 579 346455647466 580 227758858649 581 121823730193 582 53208497715 583 19053747924 584 5617414032 585 1369050618 586 276920111 587 46679837 588 6589217 589 784148 590 79447 591 6951 592 528 593 33 594 1 595 1 596 34 597 561 598 7634 599 90483 600 929217 601 8151803 602 60513724 603 377695372 604 1973388789 605 8599507814 606 31145838129 607 93413835366 608 231133372097 609 470006470302 610 782699950921 611 1064292193155 612 1179368199427 613 1064292193155 614 782699950921 615 470006470302 616 231133372097 617 93413835366 618 31145838129 619 8599507814 620 1973388789 621 377695372 622 60513724 623 8151803 624 929217 625 90483 626 7634 627 561 628 34 629 1 630 1 631 35 632 595 633 8360 634 102638 635 1095033 636 10012331 637 77729786 638 509286820 639 2804893465 640 12943063585 641 49886530009 642 160086446069 643 426251919917 644 938402208188 645 1702312789215 646 2536932820701 647 3098921874391 648 3098921874391 649 2536932820701 650 1702312789215 651 938402208188 652 426251919917 653 160086446069 654 49886530009 655 12943063585 656 2804893465 657 509286820 658 77729786 659 10012331 660 1095033 661 102638 662 8360 663 595 664 35 665 1 666 1 667 36 668 630 669 9131 670 115973 671 1283753 672 12214479 673 98992114 674 679458944 675 3935246687 676 19176845702 677 78416589271 678 268307110355 679 765810553922 680 1817493589162 681 3575047202821 682 5810944641145 683 7785731682375 684 8584854507319 685 7785731682375 686 5810944641145 687 3575047202821 688 1817493589162 689 765810553922 690 268307110355 691 78416589271 692 19176845702 693 3935246687 694 679458944 695 98992114 696 12214479 697 1283753 698 115973 699 9131 700 630 701 36 702 1 703 1 704 37 705 666 706 9948 707 130575 708 1497670 709 14806986 710 125065299 711 897550387 712 5454754621 713 28001883268 714 121137783933 715 440532535023 716 1343083647947 717 3422798820158 718 7269419548289 719 12828998763081 720 18765251930880 721 22706876714336 722 22706876714336 723 18765251930880 724 12828998763081 725 7269419548289 726 3422798820158 727 1343083647947 728 440532535023 729 121137783933 730 28001883268 731 5454754621 732 897550387 733 125065299 734 14806986 735 1497670 736 130575 737 9948 738 666 739 37 740 1 741 1 742 38 743 703 744 10812 745 146509 746 1739235 747 17843174 748 156825742 749 1174710817 750 7476230003 751 40337576517 752 184137141976 753 709658353856 754 2303543214269 755 6281113240954 756 14346858034610 757 27374582189179 758 43520962907152 759 57531599072449 760 63150696347462 761 57531599072449 762 43520962907152 763 27374582189179 764 14346858034610 765 6281113240954 766 2303543214269 767 709658353856 768 184137141976 769 40337576517 770 7476230003 771 1174710817 772 156825742 773 17843174 774 1739235 775 146509 776 10812 777 703 778 38 779 1 780 1 781 39 782 741 783 11725 784 163866 785 2011044 786 21382157 787 195273163 788 1524182384 789 10139491312 790 57377825688 791 275728489848 792 1123147713976 793 3869959738739 794 11253009782467 795 27543168313959 796 56598154217538 797 97396764932850 798 140054548924370 799 168019802864669 800 168019802864669 801 140054548924370 802 97396764932850 803 56598154217538 804 27543168313959 805 11253009782467 806 3869959738739 807 1123147713976 808 275728489848 809 57377825688 810 10139491312 811 1524182384 812 195273163 813 21382157 814 2011044 815 163866 816 11725 817 741 818 39 819 1 820 1 821 40 822 780 823 12688 824 182716 825 2315859 826 25488255 827 241543591 828 1961591927 829 13616563443 830 80658572482 831 407137330234 832 1748528420248 833 6377763562362 834 19716320093968 835 51539441680323 836 113644489902318 837 210863747274164 838 328507377677026 839 428950868006614 840 468906907743356 841 428950868006614 842 328507377677026 843 210863747274164 844 113644489902318 845 51539441680323 846 19716320093968 847 6377763562362 848 1748528420248 849 407137330234 850 80658572482 851 13616563443 852 1961591927 853 241543591 854 25488255 855 2315859 856 182716 857 12688 858 780 859 40 860 1 861 1 862 41 863 820 864 13702 865 203156 866 2656597 867 30232314 868 296922468 869 2505295845 870 18117643429 871 112138874471 872 593359340384 873 2680633675960 874 10324180773751 875 33836385643061 876 94171684103748 877 222068151319325 878 442674069605521 879 744335584185307 880 1053729605737904 881 1254203676259317 882 1254203676259317 883 1053729605737904 884 744335584185307 885 442674069605521 886 222068151319325 887 94171684103748 888 33836385643061 889 10324180773751 890 2680633675960 891 593359340384 892 112138874471 893 18117643429 894 2505295845 895 296922468 896 30232314 897 2656597 898 203156 899 13702 900 820 901 41 902 1 903 1 904 42 905 861 906 14769 907 225258 908 3036352 909 35691065 910 362859333 911 3176735744 912 23897930720 913 154297223106 914 854227966555 915 4051039912271 916 16435648394863 917 56957984953714 918 168293787410434 919 423091343200967 920 903058981415160 921 1633036002350526 922 2497153810753861 923 3224054761822791 924 3511055861792836 925 3224054761822791 926 2497153810753861 927 1633036002350526 928 903058981415160 929 423091343200967 930 168293787410434 931 56957984953714 932 16435648394863 933 4051039912271 934 854227966555 935 154297223106 936 23897930720 937 3176735744 938 362859333 939 35691065 940 3036352 941 225258 942 14769 943 861 944 42 945 1 946 1 947 43 948 903 949 15890 950 249125 951 3458380 952 41948573 953 440982687 954 4000855578 955 31265392802 956 210245759234 957 1215731876026 958 6040254442640 959 25759224803009 960 94165640581481 961 294597723588846 962 787292374243830 963 1793669203203275 964 3476713271434627 965 5722559632166880 966 7985539402955568 967 9436198576099344 968 9436198576099344 969 7985539402955568 970 5722559632166880 971 3476713271434627 972 1793669203203275 973 787292374243830 974 294597723588846 975 94165640581481 976 25759224803009 977 6040254442640 978 1215731876026 979 210245759234 980 31265392802 981 4000855578 982 440982687 983 41948573 984 3458380 985 249125 986 15890 987 903 988 43 989 1 990 1 991 44 992 946 993 17066 994 274834 995 3926124 996 49095461 997 533116513 998 5006529307 999 40589580919 1000 283864457645 1001 1711629515717 1002 8893311803288 1003 39785187344640 1004 153074045166090 1005 505815233377732 1006 1433076549933650 1007 3474830541120303 1008 7197018067415555 1009 12709200311077741 1010 19103303941166466 1011 24409000822287120 1012 26489459993078577 1013 24409000822287120 1014 19103303941166466 1015 12709200311077741 1016 7197018067415555 1017 3474830541120303 1018 1433076549933650 1019 505815233377732 1020 153074045166090 1021 39785187344640 1022 8893311803288 1023 1711629515717 1024 283864457645 1025 40589580919 1026 5006529307 1027 533116513 1028 49095461 1029 3926124 1030 274834 1031 17066 1032 946 1033 44 1034 1 1035 1 1036 45 1037 990 1038 18299 1039 302492 1040 4443200 1041 57230559 1042 641296907 1043 6227059846 1044 52311576362 1045 379958553422 1046 2385414538420 1047 12939571214238 1048 60609786443266 1049 244929423333271 1050 852885690423821 1051 2555357570098898 1052 6576489626189647 1053 14512404865254862 1054 27409918119960636 1055 44235826671937330 1056 60915302319083703 1057 71502249794936819 1058 71502249794936819 1059 60915302319083703 1060 44235826671937330 1061 27409918119960636 1062 14512404865254862 1063 6576489626189647 1064 2555357570098898 1065 852885690423821 1066 244929423333271 1067 60609786443266 1068 12939571214238 1069 2385414538420 1070 379958553422 1071 52311576362 1072 6227059846 1073 641296907 1074 57230559 1075 4443200 1076 302492 1077 18299 1078 990 1079 45 1080 1 1081 1 1082 46 1083 1035 1084 19590 1085 332180 1086 5013419 1087 66459997 1088 767790614 1089 7700687784 1090 66955197073 1091 504441688632 1092 3292693836049 1093 18617648073304 1094 91149261293395 1095 386126521878076 1096 1413886252439326 1097 4469373396485774 1098 12177769635106916 1099 28553270792841266 1100 57513242973001878 1101 99354783785434881 1102 146989104303781723 1103 186019020622747394 1104 201226384388401603 1105 186019020622747394 1106 146989104303781723 1107 99354783785434881 1108 57513242973001878 1109 28553270792841266 1110 12177769635106916 1111 4469373396485774 1112 1413886252439326 1113 386126521878076 1114 91149261293395 1115 18617648073304 1116 3292693836049 1117 504441688632 1118 66955197073 1119 7700687784 1120 767790614 1121 66459997 1122 5013419 1123 332180 1124 19590 1125 1035 1126 46 1127 1 1128 1 1129 47 1130 1081 1131 20940 1132 364011 1133 5640773 1134 76898983 1135 915113564 1136 9471182197 1137 85139554179 1138 664548763580 1139 4504047835373 1140 26506588609169 1141 135418760834249 1142 600275706405859 1143 2306796186299231 1144 7676614083938914 1145 22092448315951135 1146 54899523996300578 1147 117609710247677267 1148 216856757621316647 1149 343650947615465932 1150 467455464071152468 1151 545322412037046138 1152 545322412037046138 1153 467455464071152468 1154 343650947615465932 1155 216856757621316647 1156 117609710247677267 1157 54899523996300578 1158 22092448315951135 1159 7676614083938914 1160 2306796186299231 1161 600275706405859 1162 135418760834249 1163 26506588609169 1164 4504047835373 1165 664548763580 1166 85139554179 1167 9471182197 1168 915113564 1169 76898983 1170 5640773 1171 364011 1172 20940 1173 1081 1174 47 1175 1 1176 1 1177 48 1178 1128 1179 22351 1180 398069 1181 6329461 1182 88670824 1183 1086051424 1184 11588440207 1185 107593107031 1186 869081420809 1187 6108452397503 1188 37364579356906 1189 198892827329649 1190 920991338535476 1191 3707523614846261 1192 12962624499959009 1193 39315389100970916 1194 103297410457850146 1195 234757307445260603 1196 460770745512190325 1197 779921952219304045 1198 1136996379688009190 1199 1426168544688273363 1200 1538178860105446451 1201 1426168544688273363 1202 1136996379688009190 1203 779921952219304045 1204 460770745512190325 1205 234757307445260603 1206 103297410457850146 1207 39315389100970916 1208 12962624499959009 1209 3707523614846261 1210 920991338535476 1211 198892827329649 1212 37364579356906 1213 6108452397503 1214 869081420809 1215 107593107031 1216 11588440207 1217 1086051424 1218 88670824 1219 6329461 1220 398069 1221 22351 1222 1128 1223 48 1224 1 1225 1 1226 49 1227 1176 1228 23824 1229 434473 1230 7083871 1231 101908854 1232 1283680218 1233 14109180217 1234 135169314103 1235 1128690963225 1236 8217351162952 1237 52176711530255 1238 288967641585518 1239 1395617720404364 1240 5875079264569396 1241 21540182850012291 1242 68709956239911512 1243 190449873601926283 1244 458064721240253104 1245 954607924509058449 1246 1721288186132491762 1247 2681909932893809518 1248 3606814553842490521 1249 4183623065982540607 1250 4183623065982540607 1251 3606814553842490521 1252 2681909932893809518 1253 1721288186132491762 1254 954607924509058449 1255 458064721240253104 1256 190449873601926283 1257 68709956239911512 1258 21540182850012291 1259 5875079264569396 1260 1395617720404364 1261 288967641585518 1262 52176711530255 1263 8217351162952 1264 1128690963225 1265 135169314103 1266 14109180217 1267 1283680218 1268 101908854 1269 7083871 1270 434473 1271 23824 1272 1176 1273 49 1274 1 1275 1 1276 50 1277 1225 1278 25360 1279 473311 1280 7908608 1281 116755293 1282 1511389042 1283 17097642483 1284 168864047302 1285 1456202127445 1286 10969478813952 1287 72213553688766 1288 415549388576241 1289 2090163715276408 1290 9186361414539510 1291 35256320249442159 1292 118051287941678788 1293 344476448026425097 1294 874878868046323084 1295 1931258777681071526 1296 3700297106667930211 1297 6145663016257492404 1298 8837748480692330535 1299 10994347290102109926 1300 11825153818978315742 1301 10994347290102109926 1302 8837748480692330535 1303 6145663016257492404 1304 3700297106667930211 1305 1931258777681071526 1306 874878868046323084 1307 344476448026425097 1308 118051287941678788 1309 35256320249442159 1310 9186361414539510 1311 2090163715276408 1312 415549388576241 1313 72213553688766 1314 10969478813952 1315 1456202127445 1316 168864047302 1317 17097642483 1318 1511389042 1319 116755293 1320 7908608 1321 473311 1322 25360 1323 1225 1324 50 1325 1