A = [
1259453 1244554 7628725 1104089 1066489 1007901 995019 979679 978863 978105 995075 1022762 1062360 1105969 1160803 1221766 1281281 1349631 1420837 1487404 1550242 1617919 1675271 1733485 1787609 2029403 2077125 2119396 2339334 2191003 2257279 2282723 2122771 2174353 2158935 2162924 2146737 2102710 2082429 2049673 2024920 1995501 1963101 1946093 1919789 1898055 1880467 1860932 1843211 1827210 1808399 1791037 1774220 1763758 1747908 1733417 1721841 1710053 1696233 1685941 1674172 1662288 1659029 1649181 1635451 1635966 1629021 1728910 1729831 1726611 1825094 1822231 1816486 1802892 1786461 1769788 1759786 1746696 1730164 1714543 1698742 1685149 1668447 1650223 1641107 1625509 1609038 1592682 1577660 1565279 1546593 1532441 1518958 1499916 1487882 1472447 1452117 1437609 1421517 1406958 1389022 1373487 1357671 1343967 1326946 1312257 1298329 1282515 1265684 1253060 1238306 1224424 1207595 1193315 1180315 1166893 1152886 1138415 1126384 1111648 1100356 1087468 1074810 1064300 1049186 1034845 1022331 1010688 1000138 986336 974816 962587 951249 939100 926277 915083 905759 893885 883085 871836 859573 847301 837420 825936 816030 804477 793639 784219 775731 768275 755970 748105 738518 727777 719066 708384 699543 691630 682712 674040 664295 656039 647457 639156 630124 622673 614964 607227 600130 591934 585462 577224 570237 562095 556100 547169 538761 535031 526919 520072 513288 505900 498918 492927 486203 481123 475386 467337 462216 456099 450479 443200 438368 432373 424509 419824 414561 409957 403739 399359 392299 386911 381743 378552 373407 368608 362126 357814 353492 349006 344785 341768 335912 332127 326629 323159 317095 314757 309823 305832 302001 298448 293862 289996 286007 281836 279440 274788 271203 267335 264203 261130 258445 254793 250229 248294 244466 241689 238945 235323 232243 229891 225859 223254 219263 217241 213858 211012 208933 205029 201781 199383 197088 194614 192989 190112 187480 184900 183086 179833 177215 175462 172583 170954 167989 165615 163946 162588 160523 157856 155637 153763 151939 149840 147594 146182 144035 142060 140073 138049 136147 135056 133288 131781 129715 127580 126120 124878 123593 121256 120465 117871 116597 115276 113872 112112 110351 108847 108209 106562 105010 103320 102325 100655 100303 98499 96394 95633 94649 93355 92517 91241 90264 88887 87657 86896 85388 84836 82881 83267 81018 80663 78980 78322 76586 75754 74865 74087 72843 72386 71675 70544 69570 68493 67174 67054 66172 65255 64439 63975 62834 61829 61197 60873 59508 58954 58455 57769 56745 56092 55641 54675 54093 52992 52453 51811 51530 50721 50497 49881 48831 48641 48229 47133 46639 46051 45575 44257 44185 43988 43635 42828 42374 41884 41104 40964 40082 39923 39412 38402 38656 37834 36960 37147 36554 35924 35978 34928 34916 34416 34117 33724 33476 33020 32782 32000 31981 31193 30790 30428 29931 29882 29548 28946 28976 28308 28163 28025 27399 27305 26739 26353 25980 25811 25325 25153 25424 24782 24278 24351 23798 23687 23648 23370 22950 22797 22577 22167 22048 21910 21513 21492 21042 20846 20868 20505 20139 20135 19657 19440 19264 19006 19215 18696 18583 18251 18195 17891 17687 17450 17496 17313 17158 16748 17015 16408 16458 16265 16133 15804 15879 15703 15441 15472 15030 15033 14721 14934 14500 14211 14302 14010 13729 13738 13645 13503 13731 13391 13111 12905 12644 12865 12497 12483 12493 12458 12123 12116 11876 11907 11734 11726 11545 11427 11161 11316 10932 10959 11026 10826 10743 10627 10657 10420 10325 10112 10176 10033 9833 10203 9675 9639 9533 9579 9469 9418 9315 9298 9112 9199 8869 8896 8640 8800 8702 8513 8595 8327 8316 8212 8219 8065 8026 8055 8000 8042 7756 7884 7724 7617 7433 7372 7618 7380 7201 7423 7304 7276 7031 6992 6966 6929 7054 6889 6819 6841 6644 6657 6607 6520 6322 6513 6312 6381 6434 6204 6262 6130 6053 6055 6080 6032 6069 5867 5803 5844 5941 5644 5877 5599 5749 5565 5534 5507 5462 5528 5369 5270 5315 5187 5215 5099 5247 5180 5263 5232 4982 4991 5012 5140 4873 4889 4990 4927 4863 4829 4824 4768 4710 4588 4806 4571 4561 4627 4536 4454 4479 4417 4461 4401 4336 4274 4289 4234 4360 4222 4280 4124 4143 4079 4142 4039 4218 3995 4068 3965 3771 3946 3949 3926 3855 3730 3699 3888 3865 3820 3735 3751 3668 3675 3684 3640 3595 3514 3523 3485 3550 3517 3465 3405 3483 3470 3400 3387 3585 3361 3308 3240 3335 3388 3306 3156 3134 3277 3281 3012 3129 3253 3088 3039 3042 3003 3117 3008 2819 2957 2963 2913 2896 2894 2847 2881 2881 2858 2760 2895 2854 2760 2788 2735 2808 2669 2704 2627 2722 2721 2589 2619 2648 2625 2597 2575 2528 2600 2546 2509 2584 2509 2508 2377 2468 2480 2501 2369 2432 2450 2329 2340 2376 2397 2306 2319 2397 2301 2278 2271 2213 2309 2355 2305 2245 2264 2290 2153 2287 2180 2148 2115 2255 2155 2167 2236 2108 2096 2057 2023 2151 2079 2080 2105 2035 2045 2029 2041 2072 1971 2033 1959 1922 2025 1967 1920 1954 1930 1951 1928 1990 1866 1938 1939 1931 1941 1961 2022 2102 2051 2054 2106 2124 2173 2209 2119 2365 2372 2338 2273 2315 2166 2184 2119 2114 2099 2059 1955 1930 1883 1975 1856 1915 1809 1844 1893 1861 1688 1663 1648 1609 1567 1525 1568 1570 1561 1557 1579 1562 1505 1536 1568 1489 1567 1485 1516 1496 1560 1426 1480 1439 1468 1480 1456 1423 1467 1460 1433 1391 1352 1453 1386 1399 1426 1349 1374 1359 1400 1356 1386 1319 1348 1273 1389 1278 1276 1272 1330 1290 1286 1282 1231 1279 1304 1235 1255 1238 1248 1226 1197 1201 1225 1227 1249 1176 1283 1229 1208 1139 1294 1316 1171 1292 1342 1280 1273 1281 1324 1239 1258 1296 1239 1397 1338 1332 1376 1404 1388 1427 1369 1391 1360 1364 1493 1528 1469 1403 1275 1347 1308 1100 1084 1055 1065 1095 1089 1125 1078 1082 1065 1066 1121 1052 1097 1079 1088 1119 1025 1065 1030 1007 1038 1017 955 975 1016 1027 974 985 1068 969 887 870 958 912 890 906 865 891 893 881 897 894 860 787 846 784 890 760 816 808 811 743 846 796 836 796 847 792 802 825 791 764 751 765 801 791 766 813 797 758 790 750 775 748 785 748 724 782 744 793 788 794 767 747 791 743 789 823 844 805 751 820 819 831 761 823 809 819 774 774 810 850 838 845 768 902 905 905 863 941 895 876 904 1010 953 984 987 1042 913 1008 1010 910 971 906 977 988 896 951 970 1067 999 941 885 968 1030 865 996 897 876 841 821 889 779 801 807 767 765 698 751 699 696 733 692 693 639 639 630 631 655 628 545 537 568 541 526 508 477 498 438 460 491 480 459 463 438 426 435 479 450 465 464 419 454 453 404 472 441 423 421 446 444 450 419 440 419 407 398 430 425 392 454 387 404 373 421 400 375 416 388 413 365 358 390 378 376 349 378 334 379 362 322 341 383 396 369 344 414 394 376 344 396 397 348 376 340 321 332 340 342 354 347 363 348 337 339 362 326 335 344 334 342 322 295 334 323 359 308 304 298 334 310 313 327 366 329 337 302 284 265 316 306 305 294 301 269 298 309 330 270 321 295 299 274 255 266 282 307 273 279 285 271 280 274 285 277 270 259 257 238 227 262 251 260 231 262 242 255 226 239 237 248 239 246 231 231 277 238 244 265 253 245 228 233 247 239 229 213 222 227 230 232 212 253 222 226 258 230 227 220 239 238 228 191 199 204 210 218 226 218 223 185 201 213 223 221 192 197 219 218 201 189 209 197 207 215 194 202 217 216 192 218 219 206 195 205 189 198 174 205 185 185 180 168 173 195 210 193 185 173 192 183 154 168 194 166 180 182 191 183 195 196 161 167 168 174 144 161 176 169 158 162 140 179 170 156 161 137 155 152 167 183 171 167 167 140 165 163 168 141 153 164 146 165 160 148 144 172 142 142 177 154 149 146 172 148 165 136 147 137 141 125 136 141 153 136 126 135 144 137 159 141 130 128 139 138 157 142 134 127 138 142 118 133 128 114 126 133 133 110 95 130 124 129 115 113 118 131 111 127 130 114 126 126 120 96 114 113 137 106 127 113 110 121 119 115 117 113 108 126 110 102 95 123 96 101 113 109 116 107 110 113 137 131 108 119 132 97 100 92 106 95 89 81 130 115 90 104 93 93 107 75 104 92 86 88 82 96 116 97 98 78 83 88 86 98 101 93 98 95 92 105 101 94 88 85 89 100 85 106 83 95 75 72 92 101 86 91 99 83 94 73 91 86 77 88 91 75 75 76 86 76 85 87 80 73 83 84 71 100 68 91 80 68 79 83 79 71 75 85 87 75 74 82 69 73 65 83 91 76 85 77 82 73 77 76 80 75 72 63 74 71 80 82 58 69 98 69 61 68 48 84 70 61 60 71 82 62 73 65 70 53 65 77 55 58 66 57 65 45 58 59 57 62 51 51 54 79 65 67 64 64 69 54 55 50 43 55 51 57 59 61 59 62 73 53 61 49 48 64 59 54 48 64 65 73 55 42 57 51 55 48 53 40 52 54 60 66 55 52 52 47 63 56 56 53 55 63 42 60 44 53 39 45 48 47 45 49 43 48 47 48 47 50 53 42 47 43 55 45 35 48 37 41 51 52 37 47 48 47 54 58 50 32 46 51 43 42 42 44 43 45 54 37 41 36 39 42 41 45 32 48 41 44 34 38 35 34 27 40 45 26 41 43 40 31 31 29 34 20 32 32 30 31 34 33 29 30 33 32 31 25 26 45 35 24 27 34 29 30 42 27 27 40 25 34 28 33 28 25 24 36 19 29 26 26 31 36 34 25 24 38 28 16 15 18 24 24 19 23 27 25 17 28 26 28 34 21 25 28 28 22 28 24 33 23 21 19 32 23 22 22 22 39 36 18 22 29 20 22 19 23 20 23 26 22 26 31 25 16 15 21 19 28 23 16 25 26 29 21 19 18 18 21 17 13 23 23 17 13 21 18 19 21 26 12 24 18 19 34 19 12 28 22 12 27 23 20 16 28 23 19 14 15 19 24 15 17 15 22 18 11 23 24 16 18 22 21 21 23 19 21 19 23 26 16 19 8 13 19 17 18 21 19 10 16 14 12 14 18 22 17 21 18 19 12 20 24 20 25 15 17 14 10 13 11 16 14 18 15 21 19 17 8 14 12 15 9 10 14 12 13 7 25 11 15 12 15 20 12 15 19 16 16 12 18 7 12 13 18 25 13 11 11 17 12 11 15 17 15 13 14 12 10 15 11 24 9 18 10 10 17 18 11 7 13 13 12 7 14 14 9 7 19 14 9 10 19 7 11 11 8 11 11 12 4 15 7 18 11 16 9 17 5 12 9 17 16 17 15 15 13 15 9 14 11 11 12 16 16 14 16 8 13 
];
B = [
0 0 0
 750356 388310 362046
 838302 459081 379221
 675142 380545 294597
 1147557 714504 433053
 830845 528632 302213
 606496 401116 205380
 558241 374923 183318
 422756 285363 137393
 337687 231018 106669
 269774 185823 83951
 320027 220550 99477
 373282 257899 115383
 377284 261912 115372
 848077 597819 250258
 585410 421037 164373
 563808 410347 153461
 489766 363039 126727
 507021 380182 126839
 526313 395292 131021
 472348 355410 116938
 692366 520450 171916
 601747 455277 146470
 569716 432422 137294
 510167 388519 121648
 569923 434027 135896
 547366 418368 128998
 688309 525671 162638
 515549 397394 118155
 644016 495103 148913
 636314 490812 145502
 605825 468235 137590
 673575 520183 153392
 669866 517300 152566
 855807 662250 193557
 661656 513018 148638
 758426 588232 170194
 1584158 1231968 352190
 727650 566053 161597
 866314 676044 190270
 1432996 1116738 316258
 899613 700889 198724
 1359610 1060621 298989
 747031 584434 162597
 917598 718580 199018
 1411822 1103746 308076
 906976 711874 195102
 1380613 1081932 298681
 949706 745494 204212
 1375843 1079732 296111
 905211 713262 191949
 1359819 1068987 290832
 1029816 809805 220011
 1369385 1078426 290959
 945476 746709 198767
 1474844 1162059 312785
 1373151 1083272 289879
 942723 746701 196022
 1388216 1096663 291553
 829541 657814 171727
 97895815 79497160 18398655
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
114 229 113 20
19 30 2 3
23 59 2 4
20 71 3 3
25 67 6 7
23 96 5 10
211 124 34 26
1296 130 30 22
21892 134 60 32
196566 194 255 88
623557 227 2138 430
1479348 319 3154 1176
2794741 449 4117 2087
4170582 657 5829 3879
4747009 1116 7905 6378
4665161 2039 11831 10741
3890527 3559 16231 15215
2835705 5821 22756 22111
1795538 9632 31812 31361
901834 15082 42300 42455
352667 22335 55100 55246
129948 33051 69181 69424
91145 48258 85377 85426
102358 68665 103400 103016
121184 92837 124132 124058
144418 121444 148578 148766
171787 153203 175480 175812
201414 186865 205621 206475
233133 221710 239261 239279
265759 256255 271212 272402
296815 287779 301680 301704
325234 315918 329076 328908
350654 339656 352014 352478
364334 360253 371542 371763
375777 373547 384575 384770
386525 386958 394915 396403
395045 396174 404461 405326
405509 404877 411690 413564
413660 414517 422520 423421
424746 426038 432249 432746
439120 439915 444945 445803
453946 455189 460005 461536
471818 473108 477747 478498
491971 493132 496914 497950
513232 514951 519108 517634
535830 536808 538477 540858
554706 556334 559055 560138
571582 571920 573865 574983
581546 583141 583336 584807
584824 585648 586270 587300
580306 582039 583804 583195
571782 572007 571449 571282
552404 552185 552591 551761
525845 528101 525324 526672
494309 496217 493983 495219
458826 459505 458879 459960
422092 422999 421516 422121
386602 386115 384152 385821
351487 350422 349800 351199
319685 320370 319343 319652
293228 293961 293251 292710
274192 273650 274854 275127
259096 260293 259893 261998
250500 249886 249563 250557
252263 251227 250597 251319
263330 263885 262476 262933
280976 282572 280770 282179
304142 305099 304205 304329
338483 338728 339027 339507
379811 380285 379506 379858
434574 434573 432189 434449
463530 462715 463801 464446
493135 493561 492801 493159
510336 509259 510338 510166
505345 504361 502510 504487
458486 456979 457734 457557
383516 382741 381774 383381
267715 267927 266503 268035
139886 140001 138662 138913
50985 51022 51039 50865
8048 7819 7990 7848
69 76 61 62
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
