A = [
146878 33819 33635 425169 20186 24759 24450 24338 26557 26644 30474 29343 29986 31293 32041 31714 31344 31632 31718 31456 31358 31153 31263 32426 167662 165558 167191 168349 172973 323891 320992 320534 321824 321061 334787 333450 331345 332079 329610 329432 328343 327477 325709 323812 323772 323911 321183 319998 318946 317586 315381 314083 314045 314078 313401 310328 311246 307957 308028 307450 304778 304089 302598 300030 300002 298767 297473 295222 295739 290061 290992 287418 285457 284319 283176 280877 279237 277952 273809 271214 269528 265874 266438 264788 261898 259506 256815 255381 251820 250082 246943 245324 242498 239211 237559 235813 233092 230108 229108 226923 223557 221639 217213 216720 213834 211652 210484 206049 204664 202223 199349 197111 194279 192395 189226 186896 185741 183112 180773 179318 176344 174916 172021 170868 167338 166000 163285 161382 159606 156929 154595 153054 151995 147779 146606 145143 143547 142438 140747 138741 136251 133559 131834 130387 128672 125938 125026 123760 121402 120612 119813 118180 115889 114273 112292 110589 109176 107801 106629 104187 102881 101764 99818 99440 98500 96755 94711 93453 92428 90596 89001 88655 86894 86024 84110 83157 81869 80469 79401 78450 76396 76157 74816 73554 72526 71769 70945 70257 68553 67240 66622 65338 64760 63471 63020 61871 60887 60453 59679 57817 57657 56761 55712 55445 54112 53832 52760 51824 51256 50312 50288 49410 48867 48064 46983 46289 45668 45262 44248 43819 43019 42169 41959 40832 40713 40055 39270 38564 38243 37643 36976 36662 35795 35539 35287 34306 33859 33270 32848 32503 31830 31597 30804 30505 29973 29809 29041 28622 28678 28091 27501 27602 26842 26481 26108 25464 25449 25140 24829 24385 24115 23597 23086 23063 22630 22287 21880 21918 21657 21313 20578 20264 20325 19807 19614 19276 18848 18712 18600 18267 18197 17995 17784 17238 17145 16573 16658 16659 16037 15932 15436 15359 14956 14735 14710 14926 14365 14188 14101 13950 13556 13375 13330 13067 12849 12580 12426 12228 12096 11981 11848 11739 11534 11206 11158 11154 10976 10740 10597 10376 10127 10077 10216 9909 9698 9619 9824 9306 9274 9070 9134 8984 8764 8624 8749 8388 8191 8255 8207 8159 8077 7652 7714 7626 7628 7398 7475 7375 7282 6998 7115 6848 6720 6630 6552 6493 6369 6412 6359 6299 6469 6141 6096 5921 5911 5835 5832 5737 5631 5512 5502 5550 5343 5259 5215 5165 5172 5016 5015 4979 5056 4778 4760 4714 4681 4729 4444 4492 4429 4507 4493 4298 4309 4206 4142 4153 4087 4036 3979 4036 3991 3958 3885 3836 3841 3800 3686 3678 3651 3736 3504 3455 3591 3610 3477 3453 3271 3312 3255 3187 3327 3272 3225 3115 3144 2909 2974 3063 2995 2912 3028 2834 2871 2880 2771 2917 2852 2659 2838 2771 2684 2605 2742 2660 2694 2617 2677 2529 2463 2654 2585 2514 2477 2512 2479 2403 2424 2389 2464 2348 2321 2358 2386 2386 2364 2391 2284 2310 2194 2192 2200 2143 2183 2194 2161 2182 2207 2191 2176 2121 2136 2167 2041 2100 2106 2042 2126 2022 2080 2072 1970 2036 1977 2034 1987 1989 1988 1920 1942 1909 1941 1851 1867 1912 1835 1949 1840 1920 1839 1905 1809 1852 1889 1843 1801 1802 1810 1723 1866 1845 1832 1802 1784 1754 1770 1724 1769 1673 1792 1669 1713 1672 1614 1689 1680 1725 1565 1701 1619 1610 1629 1602 1620 1623 1549 1623 1603 1563 1516 1530 1549 1584 1589 1628 1498 1491 1575 1539 1628 1524 1519 1507 1616 1517 1502 1520 1521 1485 1532 1577 1523 1461 1538 1455 1440 1484 1427 1452 1401 1469 1485 1406 1503 1453 1466 1407 1378 1417 1516 1478 1486 1494 1458 1462 1469 1431 1445 1469 1418 1450 1376 1457 1414 1453 1483 1626 1711 1653 1504 1415 1369 1483 1454 1399 1385 1399 1440 1416 1435 1382 1356 1327 1403 1304 1273 1364 1391 1400 1390 1286 1307 1358 1445 1392 1369 1348 1349 1300 1338 1292 1382 1333 1338 1332 1334 1327 1353 1337 1289 1337 1374 1241 1334 1293 1357 1278 1390 1300 1365 1337 1324 1225 1325 1289 1345 1326 1365 1338 1321 1276 1270 1317 1306 1253 1250 1266 1242 1237 1270 1271 1294 1273 1340 1279 1262 1253 1225 1274 1261 1290 1276 1260 1268 1325 1268 1242 1270 1349 1294 1296 1298 1302 1280 1349 1272 1332 1304 1351 1374 1336 1320 1360 1283 1273 1351 1367 1260 1253 1301 1346 1301 1212 1354 1279 1302 1265 1421 1334 1252 1342 1299 1311 1312 1241 1272 1365 1289 1262 1238 1283 1261 1332 1324 1308 1245 1182 1350 1286 1287 1231 1324 1275 1264 1264 1262 1274 1177 1249 1220 1261 1283 1249 1202 1232 1217 1184 1257 1154 1240 1227 1268 1214 1179 1315 1220 1185 1311 1232 1190 1245 1249 1244 1152 1233 1269 1275 1259 1247 1193 1250 1143 1192 1240 1200 1190 1218 1246 1182 1262 1202 1179 1108 1162 1217 1120 1170 1131 1182 1201 1286 1288 1271 1159 1231 1215 1195 1304 1200 1293 1256 1317 1307 1233 1184 1132 1103 1166 1114 1180 1171 1110 1266 1219 1158 1161 1165 1173 1132 1095 1180 1107 1186 1177 1082 1131 1172 1149 1129 1164 1114 1147 1226 1129 1193 1185 1083 1123 1151 1128 1082 1140 1070 1154 1222 1193 1178 1161 1167 1120 1164 1115 1164 1137 1163 1122 1178 1142 1129 1178 1170 1147 1147 1208 1145 1137 1203 1153 1192 1138 1190 1200 1143 1188 1179 1189 1169 1123 1182 1208 1122 1088 1175 1098 1157 1137 1198 1127 1125 1185 1094 1198 1206 1184 1171 1146 1056 1163 1119 1202 1197 1221 1135 1214 1165 1146 1178 1205 1201 1188 1082 1161 1108 1170 1098 1191 1135 1115 1122 1126 1120 1150 1156 1126 1189 1106 1182 1135 1146 1175 1141 1087 1142 1123 1164 1181 1155 1078 1118 1135 1188 1196 1117 1055 1145 1074 1099 1063 1124 1124 1173 1138 1211 1161 1136 1050 1120 1153 1138 1083 1073 1058 1112 1133 1102 1046 1074 1129 1127 1070 1172 1134 1129 1051 1044 1093 1090 1202 1069 1146 1135 1000 1106 1072 1102 1076 1059 990 1066 1046 1098 1083 1047 1066 1051 1117 1137 1098 1033 1066 1163 1084 1115 1027 1024 1101 1120 1084 1034 1064 1081 1058 1083 1073 1090 1104 1010 1006 1032 997 1032 1078 1044 1009 1137 1028 1019 1007 1028 1016 1049 1059 1010 993 1039 979 969 964 953 1026 953 1049 1017 968 953 980 1013 1002 977 990 1098 986 1026 1078 1069 1066 1066 1023 1019 1039 1028 1037 1026 1039 1060 987 1099 1061 1022 1014 954 1025 1020 1068 1064 999 970 1014 984 1001 1039 1056 1006 1009 1081 1006 1051 998 992 1026 1016 1071 1046 1069 976 1078 1026 1016 1092 934 1007 1060 1133 1006 1071 1059 1034 1079 1070 1067 1098 1054 1152 1057 1050 1024 1098 1070 1014 1035 1019 1033 979 1041 1092 1111 1131 1017 1079 1103 1076 1114 1081 1037 1065 1074 1068 1022 1077 1087 1063 1065 1064 1061 1028 1008 1064 1038 1088 1028 1081 1022 962 1002 1057 966 1036 1050 1039 1007 1044 1028 1052 1038 1069 991 1009 1045 1001 1028 1012 1047 1024 1046 993 1041 953 955 1057 1119 994 1009 949 1001 990 987 1035 990 953 990 967 983 980 973 992 1004 932 952 1006 980 977 894 950 953 869 934 904 884 964 958 933 881 842 922 934 884 928 862 894 900 871 938 880 868 872 875 893 895 904 937 920 899 953 888 1005 943 919 965 990 919 899 927 900 921 928 922 907 923 895 894 915 917 970 868 929 914 965 912 944 983 949 982 950 984 984 941 967 934 1043 911 1016 1053 959 1001 1076 917 1005 979 1003 1009 937 970 1027 963 972 932 946 939 942 1026 946 970 996 975 946 981 944 939 1007 961 1041 990 1018 1011 969 934 918 967 934 951 955 937 900 934 984 948 946 877 944 944 920 999 915 884 906 908 941 960 897 890 931 985 890 883 852 901 869 942 915 852 928 951 967 892 974 962 909 916 903 997 910 929 909 888 886 898 868 861 964 947 865 893 882 876 865 880 900 883 867 898 870 896 855 841 838 857 900 876 915 872 819 845 949 843 801 867 904 886 882 936 830 872 841 832 794 843 867 822 807 814 838 845 827 868 849 850 795 860 838 858 828 786 856 858 875 844 776 782 846 840 819 843 861 824 872 833 820 815 780 879 854 835 838 811 834 873 798 819 834 836 881 759 810 870 815 826 873 836 859 880 847 806 819 801 843 893 873 752 808 850 865 846 852 802 803 796 838 819 756 824 775 787 803 766 808 824 821 812 776 763 800 768 760 782 833 765 769 808 791 765 807 794 779 795 773 776 811 834 787 866 791 833 832 805 806 812 741 814 749 848 780 813 772 862 777 830 844 769 752 782 799 769 790 772 794 745 874 812 820 855 840 850 818 812 858 801 751 761 804 770 807 804 796 778 799 764 751 729 740 788 750 769 780 777 718 732 753 761 787 716 742 765 761 680 726 757 712 729 720 697 721 728 777 740 803 794 740 753 773 725 769 751 810 756 794 741 795 799 735 755 703 820 756 785 789 769 801 753 982 883 814 788 796 818 726 765 846 809 814 752 828 846 793 783 841 825 826 810 791 819 837 758 814 771 763 813 879 891 823 795 830 825 836 849 748 777 820 819 768 817 789 834 821 725 752 757 791 780 799 804 803 727 772 787 775 760 803 777 755 739 776 717 740 740 732 753 743 738 754 733 719 725 710 707 796 749 769 780 686 752 764 693 741 673 736 695 679 749 768 697 700 696 679 747 752 713 781 710 725 717 776 738 747 764 750 776 735 689 773 718 699 766 753 783 686 678 736 721 734 772 719 709 749 780 701 760 786 724 786 738 703 743 717 763 719 676 716 785 764 722 726 757 825 767 761 768 757 730 719 761 707 731 729 763 754 743 726 764 756 741 750 759 706 767 748 749 762 746 734 754 758 791 695 723 728 751 744 722 738 722 755 706 704 735 707 747 767 743 734 726 690 741 705 712 679 680 777 748 767 739 723 695 776 730 687 765 798 792 743 741 731 731 704 732 726 771 711 675 732 726 732 762 758 723 719 703 652 728 687 657 713 713 755 745 734 738 745 766 781 713 684 678 765 759 694 731 715 682 732 687 744 681 645 649 722 691 724 707 752 711 691 718 658 708 698 712 716 723 705 688 696 688 701 693 680 635 676 657 715 742 697 661 692 711 668 619 624 688 671 657 735 685 659 655 662 710 676 662 642 699 709 699 657 697 657 717 665 669 650 632 629 623 635 627 630 639 614 623 687 631 631 617 628 650 624 640 637 631 654 663 637 690 676 654 722 631 725 679 633 712 695 696 711 651 596 606 672 672 604 663 673 666 657 658 685 661 660 701 679 647 662 598 654 627 673 624 618 649 608 595 650 651 694 611 678 608 620 668 655 609 619 
];
B = [
0 0 0
 14911 6308 8603
 9937 3557 6380
 22993 11459 11534
 8785 3699 5086
 8833 3582 5251
 12546 5085 7461
 15302 6448 8854
 11043 4440 6603
 26674 11743 14931
 11530 4755 6775
 12336 5055 7281
 17195 6662 10533
 23721 10703 13018
 23831 7572 16259
 32872 15143 17729
 18447 7972 10475
 24550 9329 15221
 18862 8179 10683
 28956 13412 15544
 24281 10377 13904
 32717 16966 15751
 30163 13995 16168
 22054 10451 11603
 35739 18041 17698
 51034 24544 26490
 7317 3641 3676
 121242 69593 51649
 4644 2378 2266
 8334 5220 3114
 6253 3309 2944
 9861 5533 4328
 4631 2265 2366
 29980 17931 12049
 5929 2534 3395
 8914 6259 2655
 5307 3112 2195
 8784 4813 3971
 748 478 270
 37669 22797 14872
 18 16 2
 387 312 75
 1650 1281 369
 11691 8938 2753
 1018 769 249
 922 673 249
 1432 1104 328
 3982 3018 964
 86150 53709 32441
 159 120 39
 1520 1199 321
 1139 866 273
 1822 1380 442
 6583 5121 1462
 104558 70856 33702
 2761 2197 564
 2828 2232 596
 6729 5556 1173
 174251 142739 31512
 66209 53766 12443
 19935635 16411910 3523725
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 
];
D = [
1 22 0 0
2 0 0 1
4 3 0 0
0 4 0 1
2 4 0 4
2 6 90 2
139 1 287 22
333 5 345 41
631 12 385 86
3699 7 584 150
20082 10 688 234
69296 28 866 381
151532 28 1036 553
260846 119 1217 843
345262 257 1442 1083
378305 526 1999 1729
323585 994 2605 2500
225181 1840 3576 3598
126883 3092 4855 4904
56750 4823 6566 6450
24040 7741 8072 8069
13810 11426 10292 10197
12713 16703 13041 12918
14218 21905 16503 16485
17726 27224 19825 19889
20408 31563 23212 22907
22209 38674 26387 25653
25560 43483 29464 29166
28795 52026 34676 33918
33624 58156 39519 38582
37534 62530 43102 41947
43057 68157 48422 48495
47938 73851 53804 53327
52296 78263 59140 57617
57815 81801 64976 64720
63056 85495 70099 69982
67736 87639 74660 73738
72467 91279 79031 78618
77733 94497 85235 83245
83712 97536 89243 89195
87669 99897 93459 92682
91898 102001 95906 95126
93340 103792 98435 96819
97048 105368 102143 100386
98376 106926 103703 102051
100500 107713 104354 103468
101571 107623 103760 104086
100368 106039 104067 102420
99607 105051 102007 102364
98105 102225 101528 99308
97849 100331 98896 98413
95604 98242 97639 96242
94644 96087 95996 94988
93240 94885 94192 92949
92952 94023 94327 92774
92928 93050 92683 91938
93110 93430 94279 92766
93078 94703 93974 93587
97464 97181 98186 96879
100901 101042 101439 100102
104127 104279 105075 103479
107230 106823 108881 106901
110667 110375 110704 109759
110654 111306 111238 109779
104992 105199 105284 104917
95954 95363 96846 95391
82815 82414 82930 82343
68457 68074 68526 67369
52839 52332 53399 52015
36372 36432 36873 36768
16483 16539 16378 16343
2242 2200 2085 2254
0 5 4 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

];x = [
10 12 15 19 23 28 35 43 53 66 81 100 123 152 187 231 285 351 433 534 658 811 1000 1233 1520 1874 2310 2848 3511 4329 5337 6579 8111 10000 12328 15199 18738 23101 28480 35112 43288 53367 65793 81113 100000 123285 151991 187382 231013 284804 351119 432876 533670 657933 811131 1000000 1232847 1519911 1873817 2310130 2848036 3511192 4328761 5336699 6579332 8111308 10000000 12328467 15199111 18738174 23101297 28480359 35111917 43287613 53366992 65793322 81113083 100000000 123284674 151991108 187381742 231012970 284803587 351119173 432876128 533669923 657933225 811130831 1000000000 1232846739 1519911083 1873817423 2310129700 2848035868 3511191734 4328761281 5336699231 6579332247 8111308308 10000000000 
];
