A = [
1179873 1189605 4503786 1178037 1202594 1110133 1098562 1108173 1095466 1068962 1065492 1074388 1079772 1077295 1090417 1091495 1098346 1111875 1105053 1098746 1104477 1095755 1091967 1098918 1144253 1809715 1827212 1863464 2530901 2469466 2550066 2565272 2496935 2537505 2584609 2573407 2507166 2517747 2499837 2467289 2445830 2432756 2416772 2402970 2392209 2363068 2340705 2315678 2286418 2262100 2235871 2217249 2203396 2182953 2161393 2140037 2119188 2097246 2074895 2050992 2022724 2006240 1982628 1969961 1948312 1926086 1905185 1885367 1866471 1839274 1817398 1795295 1773211 1754027 1734982 1716171 1694002 1670979 1653751 1633172 1611552 1588926 1570830 1550037 1528930 1510868 1492271 1475079 1456371 1436127 1416549 1397569 1377988 1360799 1344175 1323262 1306114 1286875 1270821 1252312 1236385 1216542 1200121 1183139 1168715 1152330 1138866 1126481 1107005 1092560 1077175 1060242 1046406 1031203 1011905 1001145 987991 972595 958861 942504 927836 914754 899808 885643 870858 856865 845445 836360 819819 809235 797051 785049 773326 761968 749400 736897 730809 717961 706912 695328 683630 672393 661487 651247 638987 630199 621731 607195 598643 590976 586878 574517 563483 555126 543503 537280 528944 518972 510134 501069 495078 484976 476008 470640 461583 453567 446186 440652 432349 424019 417997 409616 404351 397670 392340 384206 376914 371962 364980 358558 352857 345605 340341 334334 331461 325043 318329 312819 308494 302417 298241 290712 286224 282741 277316 272370 268532 264136 259567 253348 249318 246268 240837 237598 233312 230193 225915 222069 218735 215006 210075 205251 201869 197230 194239 191208 187630 184804 181393 178801 175671 171535 169322 167011 163058 160103 157812 155816 152910 149393 147048 144355 141818 138999 137243 134289 131068 129683 125810 124095 122252 120803 118526 116400 115070 113244 110615 108927 106923 105695 102725 100662 99336 98846 97251 94173 93134 92099 89106 88197 87638 85051 84028 82852 80524 78955 77565 76068 75156 74045 73037 71837 70776 70356 69053 67192 65748 64024 62991 63277 62861 60286 60010 58397 57720 57020 55032 54297 52275 51570 50665 49799 50463 50320 49383 48743 47659 45473 46593 47438 44091 43149 42225 41457 40867 39342 38957 38653 39932 38447 37118 37929 37025 37055 35943 36022 35152 32856 31735 30840 33496 30545 30226 28641 28281 28848 28051 26252 25869 25352 24949 24641 24018 23749 23461 23061 22990 22461 22549 21934 21943 21538 21315 21253 20397 22309 21576 20887 20699 20110 19588 20134 19600 18878 18713 18855 20173 18003 19464 18049 18135 17593 17344 17107 16097 16616 16181 15995 14975 15104 15560 14781 14424 14440 14430 14516 14222 13878 13477 13232 12841 12724 12913 12782 15604 14451 14057 13971 13779 14110 14377 13752 14794 13163 13627 12850 9558 9433 9521 9408 9264 9665 9307 9638 9416 10188 9100 9198 8786 8887 8848 8911 8602 8847 8398 8031 8100 8113 7750 7846 8022 7508 7424 7263 7282 7067 6905 6903 6994 7175 7045 6687 6916 6780 6639 6574 6073 6115 5903 6221 5705 5896 5991 5791 5875 5774 5995 5701 5450 5482 5563 5442 5317 5174 5077 5039 4935 5023 4797 4769 4885 4694 4521 4539 4822 4417 4570 4483 4493 4492 4344 4217 4421 4287 4201 4203 4171 4060 3879 3944 3943 4035 4083 4056 4063 3997 3924 3929 3975 4055 4161 3910 4002 3920 4124 4085 4060 3984 3671 3850 3728 3724 3631 3889 3685 3658 3523 3431 3429 3551 3542 3496 3494 3553 3546 3541 3566 3385 3282 3308 3336 3400 3157 3107 3405 3312 3233 3366 3238 3310 3363 3211 3276 3253 3242 3245 3078 3211 3179 3235 2920 2841 2957 3229 3264 3203 3047 3410 3258 3297 3163 3229 3045 3315 3157 3030 2931 3061 3114 2954 2736 2725 2816 2900 2786 2741 2743 2891 2882 2800 2866 2862 2656 2671 2832 2394 2519 2287 2396 2458 2662 2492 2353 2397 2332 2381 2296 2328 2390 2290 2381 2266 2400 2442 2319 2190 2210 2029 2172 2118 2080 2126 1891 2004 2022 1969 1961 2078 1986 1914 1978 1890 1919 1876 1895 1986 1917 1862 1839 1897 1887 1948 1965 1816 1933 2047 1859 2025 1795 1780 1904 2023 1967 1738 1751 1781 1880 1878 1624 1760 1735 1550 1722 1624 1638 1666 1504 1484 1479 1383 1358 1453 1389 1542 1438 1455 1483 1441 1409 1503 1424 1406 1333 1342 1408 1467 1482 1464 1408 1351 1221 1276 1280 1207 1196 1236 1270 1238 1181 1210 1133 1184 1213 1150 1268 1127 1168 1117 1157 1164 1133 1146 1104 1221 1284 1356 1402 1353 1437 1339 1296 1408 1273 1282 1315 1320 1278 1235 1228 1333 1355 1453 1346 1410 1329 1224 1203 1395 1449 1456 1364 1318 1319 1446 1450 1325 1225 1238 1533 1405 1474 1532 1221 1423 1223 1115 1287 1258 1060 1264 1241 1229 1647 1857 1390 1330 1413 1257 1265 1177 1283 1157 1218 1142 1192 1072 1039 1123 960 973 985 920 996 986 860 954 970 849 857 887 1066 968 931 963 1050 923 901 836 796 829 774 748 823 833 793 810 796 794 774 829 840 857 884 946 1001 882 904 955 837 817 880 777 813 704 756 766 759 771 743 650 714 780 761 731 683 711 763 785 766 726 836 733 681 651 692 720 721 702 666 775 702 670 680 658 702 666 789 884 969 872 861 982 919 949 900 1002 829 840 836 897 821 919 971 699 760 800 773 566 587 614 742 639 736 694 694 718 627 622 639 876 693 650 644 703 745 657 846 678 921 886 832 824 785 832 821 734 674 653 641 667 527 553 528 488 471 527 797 512 668 546 526 525 469 442 531 544 643 611 515 536 462 496 485 501 500 470 520 427 484 505 414 449 460 411 422 410 496 401 381 404 400 355 390 390 393 286 290 318 310 341 280 341 354 349 428 339 353 337 366 324 320 291 318 315 331 312 317 335 328 292 370 301 356 354 385 339 364 348 330 319 309 333 282 297 255 270 248 260 262 259 276 299 235 248 232 239 238 262 217 267 266 230 283 270 224 255 300 288 300 320 306 334 338 245 266 208 233 249 247 221 203 244 254 254 261 236 255 256 253 247 241 234 282 222 231 225 253 197 387 323 330 412 355 306 370 342 289 295 268 311 341 275 400 259 292 285 290 343 346 345 241 206 230 213 227 213 250 257 270 243 185 198 197 213 184 193 239 216 220 193 202 222 219 177 197 182 159 203 168 163 187 159 170 153 189 173 162 153 173 144 181 180 156 183 189 187 184 201 193 181 161 176 201 171 173 157 169 164 155 143 177 140 166 162 174 179 180 177 168 171 179 153 155 140 150 158 169 191 152 175 158 142 142 155 158 170 157 136 154 155 124 130 151 154 172 136 140 152 161 165 144 126 196 207 206 207 203 233 231 239 198 210 226 243 275 270 241 212 203 250 233 184 208 217 221 243 238 201 309 219 245 293 230 227 208 260 404 362 391 456 211 225 254 241 215 224 180 225 240 222 189 204 234 116 141 130 92 99 126 84 122 124 123 95 82 111 103 129 126 115 110 133 111 93 96 97 108 101 101 92 115 106 111 111 93 81 92 90 76 94 91 76 77 70 83 94 85 84 88 81 95 88 92 108 74 82 90 91 60 66 72 68 74 77 81 80 63 85 68 68 76 71 78 65 67 77 79 89 90 90 68 92 75 77 70 63 79 73 91 176 154 135 189 185 143 181 179 155 148 167 122 182 141 142 174 130 142 161 165 159 149 146 175 140 120 154 108 113 71 68 63 62 65 81 49 50 51 56 63 66 63 58 56 70 59 48 48 50 53 81 51 78 63 71 69 48 56 71 54 73 58 54 52 43 54 56 67 64 58 72 59 54 52 50 44 57 37 50 45 43 50 36 31 48 46 32 35 28 49 38 34 20 41 28 33 45 23 28 27 41 34 42 59 39 40 44 43 37 57 34 48 42 47 33 36 45 38 56 37 47 55 41 63 47 52 55 35 39 48 54 45 50 32 37 38 50 48 35 31 45 52 48 44 50 43 60 48 44 44 41 54 35 30 49 37 38 31 42 35 31 37 32 33 34 37 33 26 31 34 27 37 31 38 38 29 24 37 40 36 22 36 37 32 28 29 34 31 36 31 43 31 32 24 40 21 24 29 29 23 22 31 26 26 24 30 29 38 28 30 28 36 25 39 33 34 32 32 19 25 33 42 31 23 27 22 36 27 31 29 28 38 36 32 28 42 29 30 43 37 26 35 36 30 29 31 30 21 29 33 32 27 26 31 21 30 31 34 33 37 26 25 30 34 29 23 45 27 35 28 28 33 26 25 37 31 28 30 20 20 24 33 28 27 35 29 22 38 29 25 23 21 33 18 34 25 16 28 28 24 23 28 27 25 31 35 32 49 51 40 44 33 50 35 39 63 47 50 42 43 39 42 43 36 43 34 50 50 24 32 26 24 27 36 39 35 22 31 27 19 24 30 23 23 30 26 43 22 28 38 28 21 16 30 25 25 18 25 30 21 31 26 25 29 22 29 41 26 37 29 37 43 38 32 29 42 25 38 37 19 24 29 23 21 21 31 17 25 34 27 32 37 29 33 27 35 24 26 30 23 23 18 25 18 27 27 22 24 26 26 30 29 27 36 31 27 21 18 25 30 31 29 26 22 32 38 39 32 22 31 34 42 30 36 27 38 29 32 27 26 19 21 35 21 20 23 22 21 24 30 22 23 25 23 22 21 24 24 15 17 23 27 24 15 21 11 15 22 18 27 27 15 15 7 13 19 13 11 25 13 20 22 15 12 16 18 8 11 19 30 25 24 15 17 11 11 17 16 17 14 16 14 16 14 15 13 16 16 18 20 25 32 17 15 15 13 16 18 19 14 23 13 15 16 22 18 19 11 22 20 17 13 23 17 16 21 18 23 11 17 13 25 21 18 18 18 19 21 10 15 13 21 11 13 9 12 19 12 20 10 20 11 18 14 13 12 20 24 15 28 27 19 31 22 18 16 17 24 29 15 8 26 20 22 19 24 19 16 20 24 17 20 25 7 19 22 21 17 20 21 28 19 20 19 16 24 26 20 21 29 22 17 23 26 22 20 23 23 12 28 20 27 19 20 13 22 20 23 30 20 22 25 28 22 19 20 15 13 30 27 17 20 16 15 23 12 12 14 14 14 15 13 14 13 10 21 10 8 17 12 16 18 17 19 11 9 14 8 11 5 14 12 10 27 16 12 19 21 17 19 18 24 15 25 19 27 34 15 13 15 16 12 19 5 14 11 19 14 7 19 15 16 18 22 10 12 21 12 14 22 18 
];
B = [
0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 216966 79051 137915
 343762 121736 222026
 147286 50219 97067
 1088281 366999 721282
 122261 47512 74749
 272887 96498 176389
 177438 66144 111294
 301817 111763 190054
 72618 27154 45464
 1303195 456419 846776
 30685 14001 16684
 57481 24753 32728
 73109 29596 43513
 291150 103663 187487
 114057 46285 67772
 57368 24239 33129
 81796 31067 50729
 149835 58040 91795
 2266713 834515 1432198
 57632 28333 29299
 71577 30905 40672
 63892 28569 35323
 95198 41141 54057
 175880 68817 107063
 2481345 950490 1530855
 101896 43588 58308
 76167 32771 43396
 100100 46060 54040
 1182890 459354 723536
 1066906 438466 628440
 117706970 52630482 65076488
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
91 192 2 1
46 29 1 0
43 45 0 2
9 66 2 0
3 67 2 0
13 82 79 5
1251 148 211 38
8478 155 318 102
39065 253 538 246
120344 352 848 506
641911 478 1218 856
972578 1010 1744 1360
1291122 1970 2640 2106
1646449 4118 3678 3461
1791819 7537 5156 4845
1748622 13379 7092 7022
1392832 20120 9412 9169
880907 27551 11617 11260
414526 34596 13734 13475
127808 40021 15971 15986
36969 43236 17885 18324
27663 43866 19986 20253
28091 40850 22999 22199
28840 35785 25430 25254
30162 32413 28077 27907
32578 31260 30447 30181
34645 32519 32963 33427
37573 35014 36494 36323
41307 38836 40349 40254
44872 42887 44703 44614
49697 47841 49144 48996
54382 52315 53884 53599
60338 58427 59305 59596
66326 65192 66378 66133
74202 73289 73057 73724
82849 81907 82843 82300
93111 92183 92061 92422
104199 104732 104212 104946
117579 117658 117261 117676
132346 132053 132019 131612
149503 149621 149378 148699
168416 168392 168882 168171
189210 189129 189377 189078
212429 212691 212469 213479
239776 239823 240476 239453
268339 268389 268790 268465
299344 299405 299991 299767
331460 331453 332222 331920
364574 365800 364874 365477
396194 397209 397620 396919
424234 424222 424499 424702
447859 448190 448063 447340
467480 467492 468166 467489
486549 485484 487045 485958
503249 504135 504113 504629
523878 521936 522006 522703
545158 545068 543696 543357
565134 566707 567332 564152
585827 585820 587918 585797
598986 598613 599471 596815
601916 601771 601306 600700
578314 578329 578948 577673
521357 522297 522097 521162
418656 416929 417321 418567
278544 279034 280000 280129
134348 134215 134502 134947
36822 36938 37039 36911
3975 3982 4013 3934
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
