A = [
1421431 1404048 5333376 1388726 1415342 1307098 1293349 1304299 1291392 1257705 1252785 1261084 1269302 1264634 1276196 1278106 1283258 1299068 1291065 1283625 1288340 1279300 1275094 1282399 1332145 2098621 2114483 2159078 2930504 2864762 2961250 2982589 2903036 2949989 3000878 2987437 2908972 2923387 2898391 2859495 2837686 2828065 2806574 2788284 2778085 2748817 2719782 2696162 2656897 2627310 2599245 2578544 2558676 2538777 2515427 2505165 2461163 2438002 2408880 2378168 2350329 2322958 2297594 2272878 2248826 2225475 2203586 2178993 2156189 2127217 2099124 2075388 2048893 2023877 1998596 1978842 1956824 1930181 1904964 1886317 1861621 1834807 1812706 1789310 1762898 1743584 1720392 1698713 1676794 1653637 1632667 1608576 1585633 1566589 1552165 1529745 1509250 1485972 1466443 1446566 1424948 1409984 1389295 1372529 1351934 1334442 1323766 1302430 1281210 1265743 1247623 1226410 1206560 1191196 1171985 1158454 1143077 1124811 1116222 1093345 1075330 1058482 1041664 1025679 1005383 990934 976111 963379 945990 934560 927431 912126 895163 882684 870739 854213 880477 829244 816542 804284 790538 776531 766343 756170 744775 733951 724263 708947 696686 686439 677474 664418 653438 647664 632307 623240 613409 602170 589989 582625 574743 565542 551890 544269 535136 525364 516659 506045 497536 490051 482294 474274 465977 458526 452447 443838 435338 428263 420389 413346 407999 399548 393680 387937 383390 375550 368530 362281 355899 349263 344290 338749 333666 328868 322031 315650 310778 306611 302128 296411 290444 286412 279139 275164 270838 266171 261499 256870 253000 249200 244261 238212 234507 229591 226388 222897 217855 215039 210600 209201 205309 200668 197609 194362 189902 186012 183789 182017 179331 174072 172365 169194 166191 162161 158998 156576 152769 150693 146937 144461 143005 140729 139258 136682 135274 132085 131205 128154 125992 124559 121709 119782 117675 115751 114136 110827 108664 107622 105020 103672 102786 98877 98308 97876 94905 93185 90275 88993 88126 86983 85902 84095 83226 82034 81104 79221 77732 75167 74741 75284 75109 71759 71759 69547 69103 67897 66042 65159 65754 63630 62193 60968 60846 60494 59022 57889 56420 55479 55133 56093 54176 53558 52556 52142 52312 49423 49001 51169 48376 47075 46303 46367 45011 44959 43988 43536 43153 41493 40347 39292 42161 36755 36574 35447 34624 36646 34960 33615 31296 31011 30308 29680 29321 28713 28603 28054 27731 27350 27648 27234 28260 27798 27691 27762 26985 26783 25554 24966 25089 24585 24278 24678 24557 23522 23200 23048 24561 22104 23582 21856 22222 21713 21262 21171 19793 20830 19999 19785 19082 18934 19177 18182 17754 18326 18393 17860 17909 17362 17058 16763 16244 16163 15869 15609 18678 17597 17128 17048 16767 17277 17611 17203 18633 16659 17027 15863 12530 12769 12571 12569 12178 12669 11890 12225 11667 12554 11516 11684 11518 11518 11228 11112 10892 11161 11312 10647 10770 10661 10273 10082 10553 9820 9836 9746 9660 9407 9491 9446 9758 9541 9009 8655 9071 8733 8662 8686 8753 8254 8208 8211 7425 7511 7441 7330 7290 7273 7369 7249 6964 6947 6873 7179 6863 6947 6652 6672 6491 6444 6442 6363 6499 6181 6028 6083 6208 5965 5978 5942 5927 5993 5966 5751 5884 5801 5643 5536 5515 5406 5444 5342 5364 5327 5285 5269 5293 5258 5219 5245 5177 5249 5193 5116 5279 5199 5203 5109 5077 5137 4915 5025 4936 4982 4723 5007 4877 5014 4961 4901 4754 4678 4593 4629 4624 4740 4773 4584 4472 4272 4282 4402 4377 4519 4093 4246 4491 4426 4251 4338 4298 4239 4392 4199 4187 4181 4178 4130 3970 4092 4014 4073 3829 3669 3765 4212 4162 4009 3857 4161 4017 4113 4015 4050 3881 4155 3953 3845 3932 4033 4068 3754 3387 3531 3500 3730 3407 3426 3474 3626 3605 3618 3733 3725 3385 3394 3561 3191 3272 2967 3067 3125 3241 3114 3011 3096 2925 2959 2805 2910 2963 2937 3036 2998 3046 3182 2920 2744 2902 2739 2880 2778 2734 2690 2639 2623 2679 2552 2692 2722 2541 2551 2692 2690 2719 2666 2385 2620 2653 2538 2535 2590 2491 2552 2480 2339 2394 2494 2412 2472 2375 2257 2450 2497 2529 2312 2347 2244 2460 2342 2200 2120 2310 2052 2266 2159 2123 2135 1961 2102 2140 1942 1958 1884 1823 1916 1989 1913 2137 1908 1947 1952 1820 1840 1870 1887 1891 1972 2380 2069 1972 1826 1678 1705 1703 1706 1616 1608 1561 1600 1576 1619 1607 1685 1508 1524 1578 1512 1541 1496 1474 1597 1562 1562 1604 1668 1667 1671 1752 1748 1883 1753 1652 1701 1697 1631 1895 1651 1629 1625 1596 1733 1773 1872 1662 1727 1663 1596 1672 1802 1821 1796 1773 1646 1744 1952 2035 1835 1685 1695 2061 1868 1987 2111 1854 2435 2028 2377 3540 2850 2167 2353 2019 2031 2014 2264 1764 1710 2458 2040 2248 1964 2124 1937 2164 1988 2074 2182 1439 1751 1620 1611 1341 1318 1270 1388 1227 1279 1262 1251 1203 1223 1447 1337 1268 1286 1358 1228 1317 1048 1062 1097 1074 1094 1043 1053 1095 1050 1128 1129 1122 988 1004 1096 1043 1160 1148 1106 1131 1225 1137 1123 1139 1042 1003 985 984 928 964 1027 1010 887 909 1011 969 942 940 948 1042 996 1009 921 1071 914 950 841 886 861 889 839 828 1077 936 970 922 984 939 933 1048 1183 1229 1134 1107 1202 1183 1276 1135 1326 1167 1149 1027 1141 1152 1276 1321 1039 1077 1210 997 918 890 904 978 843 870 834 803 850 807 830 826 1088 835 806 860 880 912 830 1039 860 1193 1132 1100 1146 1098 1060 1076 1046 937 852 817 925 718 724 661 626 653 716 951 641 812 673 613 689 664 659 713 685 780 706 675 724 669 650 660 602 653 626 662 670 743 800 598 607 581 563 556 514 595 497 491 520 476 455 465 551 516 469 461 475 482 473 399 514 433 423 463 404 405 400 479 414 414 358 389 389 377 362 390 407 361 414 457 405 448 446 467 444 457 424 414 353 404 392 385 377 316 351 341 303 324 377 357 373 284 328 322 312 318 319 308 330 349 275 324 330 280 296 362 357 369 386 374 411 484 345 355 321 284 309 276 284 250 264 277 287 288 285 290 292 272 289 301 289 310 274 242 310 298 232 429 383 393 484 433 341 448 390 348 342 347 385 424 339 471 313 364 329 376 413 454 438 260 252 286 255 294 307 431 396 345 431 348 372 404 254 269 280 320 282 282 262 284 264 295 226 240 240 194 217 225 212 241 257 238 207 220 207 224 207 219 214 240 251 187 244 229 235 226 236 240 227 241 225 273 273 233 247 262 223 188 203 235 207 190 207 207 236 217 211 195 196 179 181 193 184 168 177 170 196 197 188 195 193 195 187 197 202 200 173 197 197 155 177 169 171 187 178 155 170 185 174 175 163 236 229 228 230 226 280 283 253 241 248 268 280 313 343 314 278 263 285 281 241 263 282 254 297 301 271 391 288 303 329 274 287 277 301 476 386 427 513 249 271 307 290 280 236 253 265 282 261 249 241 279 145 228 195 168 139 158 124 181 161 156 176 191 200 179 195 182 194 151 183 173 141 166 126 136 140 134 144 148 128 130 142 117 103 120 115 105 128 126 121 111 116 100 123 131 119 115 107 108 112 97 102 88 79 102 119 97 108 106 99 104 112 95 107 101 130 113 107 107 127 116 93 118 116 120 117 133 124 107 124 110 122 132 116 115 114 111 213 208 186 226 224 188 202 214 184 186 205 161 220 187 175 203 166 173 193 190 181 182 171 205 156 145 180 147 121 164 163 170 166 163 97 79 77 68 73 90 81 81 70 76 89 76 78 78 78 83 90 82 98 93 81 82 73 92 100 75 91 74 83 95 102 94 87 87 81 87 87 94 80 72 80 64 90 67 82 67 68 60 59 56 73 70 67 72 65 65 66 56 50 52 48 44 58 64 43 59 59 57 54 144 107 53 60 70 59 72 49 59 57 66 49 61 70 71 79 71 84 86 79 100 70 77 96 63 75 66 75 64 75 59 55 64 56 80 58 43 61 65 78 58 82 53 72 73 62 64 58 70 52 55 78 64 66 63 74 54 47 58 44 67 45 43 44 39 56 65 54 45 65 63 63 59 51 43 47 84 75 72 62 50 59 55 52 54 58 45 58 63 45 49 54 38 48 45 57 41 52 45 50 51 41 51 54 57 58 71 54 60 53 65 57 50 53 51 59 71 57 76 61 50 60 58 72 66 61 59 58 65 76 69 65 75 56 61 123 129 116 124 108 102 100 71 44 68 58 59 48 44 52 44 46 53 53 45 59 46 55 44 51 57 51 52 67 49 57 56 60 68 49 48 58 55 55 50 39 46 49 46 56 49 57 40 48 44 50 44 54 50 48 45 45 50 39 37 48 39 49 53 63 65 70 55 60 71 65 54 59 51 68 62 59 73 69 80 64 84 54 59 60 64 64 63 58 50 38 43 57 53 52 44 50 47 38 53 47 37 39 35 40 45 53 52 57 55 50 78 65 74 77 86 78 58 61 76 59 79 94 86 84 100 96 134 90 89 84 88 89 105 120 89 94 167 86 94 95 100 107 122 123 80 75 83 75 683 507 749 1183 1078 721 714 545 798 402 50 34 28 24 31 30 36 36 44 49 48 33 39 41 47 36 51 40 38 37 34 27 42 45 31 45 50 49 84 49 46 43 48 41 43 43 43 44 56 46 36 46 36 40 41 52 44 32 43 48 34 44 53 48 41 38 33 42 28 30 38 45 31 36 34 42 33 34 41 28 33 29 28 32 32 36 21 24 37 35 28 32 17 34 41 35 49 26 29 26 26 41 31 30 33 27 35 27 24 27 19 33 30 34 25 26 45 23 29 35 35 32 22 26 41 30 31 30 39 33 28 26 33 43 27 45 28 51 30 39 35 37 17 22 28 29 31 21 28 22 31 18 33 23 29 32 31 31 31 24 30 20 31 20 34 18 23 36 24 40 27 27 26 36 25 32 35 34 23 33 36 30 31 44 22 36 26 26 33 36 30 42 33 30 37 35 31 35 34 34 26 46 46 34 21 28 22 44 31 31 27 27 30 38 36 29 28 16 33 38 31 33 43 35 27 45 32 29 25 27 26 34 40 23 26 47 63 57 53 74 74 32 24 38 34 32 27 43 41 36 31 39 36 35 36 32 29 48 22 33 23 29 22 30 32 28 22 13 30 16 20 25 37 39 22 28 27 19 17 18 13 9 18 33 31 29 35 33 20 40 31 30 33 40 38 34 37 29 25 41 41 39 35 19 22 28 24 22 21 30 32 19 31 26 31 25 30 24 27 33 26 32 18 25 
];
B = [
0 0 0
 571530 30951 540579
 311537 18396 293141
 983278 64639 918639
 304499 18213 286286
 324167 19297 304870
 441774 26308 415466
 501782 33818 467964
 386701 24977 361724
 962733 70323 892410
 356104 30276 325828
 400429 34774 365655
 487134 53176 433958
 641779 47726 594053
 308547 28084 280463
 931919 69665 862254
 335135 20134 315001
 351747 24431 327316
 369954 25400 344554
 748178 47738 700440
 398452 24710 373742
 1111179 81740 1029439
 677938 41260 636678
 594678 38606 556072
 1267944 72810 1195134
 1727611 111680 1615931
 281910 23398 258512
 4978816 357604 4621212
 155684 21157 134527
 330197 37450 292747
 217665 25036 192629
 343968 33920 310048
 147354 18990 128364
 1088329 101284 987045
 122083 16816 105267
 272725 29929 242796
 177004 20031 156973
 301424 31134 270290
 72225 12206 60019
 1304074 122163 1181911
 30598 8026 22572
 57428 13242 44186
 72727 12644 60083
 290883 27040 263843
 114281 23177 91104
 57423 10613 46810
 81764 12534 69230
 149552 20669 128883
 2267132 207450 2059682
 57687 16064 41623
 71640 13761 57879
 63927 13019 50908
 95210 18485 76725
 175902 20209 155693
 2482281 238841 2243440
 102035 18855 83180
 76075 13235 62840
 100088 18095 81993
 1182591 104422 1078169
 1067164 110672 956492
 117731844 16507260 101224584
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
109 223 9 1
58 29 3 0
61 56 1 5
24 76 3 4
24 100 6 5
41 111 72 19
1460 190 247 44
9328 199 322 132
42031 324 606 281
129021 463 919 582
689981 629 1327 952
1044556 1218 1984 1514
1387639 2331 2901 2343
1771693 4657 4090 3808
1933898 8495 5666 5325
1893680 15011 7840 7750
1511934 22366 10346 10168
959043 30527 12609 12772
452720 38291 15214 14907
141105 44338 17671 17741
41804 48058 19829 20452
31101 49025 22385 22771
31724 45677 25730 25006
32836 40358 28399 28240
34150 36636 31195 31033
36833 35475 33506 33780
39454 36465 36561 36648
41975 39144 39807 40217
45750 42854 44375 44001
49004 47019 48104 48455
53391 51420 52425 52653
57828 55642 56439 56960
62944 61199 61633 61856
67929 67028 67493 67494
74007 72958 72269 73327
79690 78889 78753 79070
86045 84687 84785 84780
91373 91120 90740 91133
95763 95971 95028 95822
98690 98302 98302 97969
99896 99732 99348 99329
97873 97897 97795 98571
93561 93143 93105 92718
84542 84258 84588 84640
74026 74105 74522 73980
61526 61649 61479 61439
47093 46903 46902 46927
33198 33459 33141 33130
21562 21786 21087 21726
11918 12090 12070 12087
5512 5470 5373 5468
1907 1817 1952 1879
556 550 536 523
75 83 99 80
2 4 0 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 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
