A = [
1526645 1411872 5904485 1377015 1305793 1271211 1228560 1241374 1229653 1200073 1206362 1226454 1234676 1243921 1262208 1273584 1285365 1315239 1304522 1301167 1320211 1312392 1311805 1330097 1402010 2407528 2417443 2481647 3470788 3366786 3465362 3489550 3382275 3454179 3500065 3469978 3393268 3380183 3352943 3306437 3274955 3268694 3246052 3231786 3226455 3182409 3141419 3103619 3052792 3013979 2979742 2953938 2934098 2907415 2880799 2871140 2818365 2776260 2741704 2704127 2666139 2634447 2605124 2575306 2551006 2522381 2489009 2458973 2426356 2392599 2358631 2324567 2297791 2270064 2242519 2212147 2187031 2155420 2123151 2091657 2060882 2026258 2005236 1980661 1952717 1927941 1899862 1875465 1845188 1816400 1789795 1762696 1734687 1711132 1691520 1671292 1641741 1618664 1596251 1572406 1542784 1521226 1496505 1478944 1457189 1438212 1417957 1399232 1373911 1353161 1329489 1304790 1286006 1265625 1246312 1229076 1209772 1190750 1182514 1154330 1135099 1114728 1096796 1075102 1055162 1039916 1022445 1005973 991806 977061 964814 945598 930471 914209 899435 882245 907263 853640 841828 826199 811636 798132 785999 773582 759299 745573 732656 721544 706234 696088 685405 673905 659959 651729 636970 625003 615504 605286 593449 583241 573255 562159 551068 543838 534340 522661 514669 504602 493609 485678 477885 469446 461545 454058 445888 436645 427856 421302 414831 406835 399751 391326 384874 378165 373158 366762 359669 352457 346942 338972 333792 328870 323549 318545 313314 306970 301921 296698 292021 286690 282157 276038 270167 263928 261203 255950 250868 245849 242644 238526 234626 228839 225503 220134 218210 214058 210329 205065 202319 199800 195921 191848 189025 185048 180959 177303 175495 173331 170162 166749 164587 161492 158836 156197 152536 150646 147237 144746 141099 138731 137447 135663 133030 130563 129461 127400 126126 122790 121180 118945 116603 114628 113020 110794 109460 106821 104682 104178 101727 100737 99097 97063 96025 95317 92762 91082 89166 87138 86358 86082 84274 82932 81120 80858 79579 77323 76891 74783 73470 74399 74510 71298 71537 70369 69798 68650 66198 65666 66721 65354 63750 62624 61898 61364 60320 58830 58181 57240 56810 57756 56624 54576 54276 54682 53376 51405 50936 51403 50257 49421 48605 48221 47578 47153 46479 45296 45237 43884 43310 42274 45465 40148 39935 38835 37952 39427 38213 35962 34234 34021 33378 33409 32455 32481 32142 31355 31335 30654 30860 30764 31474 31414 30707 31120 30626 29861 29087 28333 28794 28063 27848 28185 28154 27103 27240 26747 27851 25955 27011 26024 26522 26152 25031 24649 23457 23453 23587 23151 22473 22476 23207 21841 21849 22156 21888 21605 21629 21500 21005 20662 20208 20132 19839 19387 22310 21448 20806 21012 21252 21463 21589 21124 21845 20922 20856 20195 16132 16262 16197 15934 15838 15702 15514 15128 15267 15569 14883 15031 14962 14986 14517 14464 14308 14616 14275 14490 14048 13999 13890 13653 13687 13386 13375 13167 13046 13028 13162 13173 13011 12759 12426 12088 12448 12437 11904 12143 11779 11808 11519 11509 10860 10956 10565 10560 10569 10302 10360 10324 10312 10132 10148 10137 10032 9910 9960 9952 9745 9563 9674 9500 9584 9257 9213 9051 9084 8877 9003 8859 8755 8739 8680 8589 8640 8704 8281 8427 8250 8276 8250 8124 8152 8010 8023 8161 8072 7981 7762 7862 7829 7758 7655 7707 7672 7631 7581 7458 7679 7585 7529 7556 7400 7213 7211 7450 7172 7075 7032 7153 6954 6780 6829 7112 6774 7291 7183 6869 6647 6663 6556 6590 6445 6621 6278 6495 6447 6757 6427 6389 6544 6348 6444 6263 6496 6235 6256 6273 6117 6073 5889 6171 6027 5608 5851 6091 6003 5832 5965 6144 5983 6014 5961 5896 5723 5749 5947 5728 5744 5845 5879 5514 5175 5211 5179 5234 5010 5100 5117 5323 5219 5153 5306 5284 4995 5085 5144 4704 4722 4625 4688 4717 4755 4728 4560 4508 4450 4319 4372 4443 4423 4415 4642 4588 4609 4600 4287 4158 4260 4176 4185 4129 4176 4074 3984 4108 4030 4092 4124 4128 4135 4086 4105 4010 4178 4091 3852 3912 3913 3801 3858 3901 3823 3712 3513 3670 3558 3652 3633 3654 3528 3496 3581 3596 3653 3536 3336 3594 3393 3521 3416 3152 3341 3297 3258 3153 3144 3177 2808 3016 3081 2990 3044 2811 2901 2898 2995 2925 2963 3081 2944 3003 2842 2887 2922 2847 2959 2990 3249 3049 2923 2743 2591 2703 2604 2608 2552 2537 2644 2561 2490 2545 2420 2625 2441 2418 2388 2429 2352 2306 2297 2418 2368 2373 2484 2526 2452 2431 2408 2570 2448 2386 2512 2545 2415 2321 2475 2291 2476 2451 2371 2294 2398 2411 2259 2333 2452 2328 2373 2373 2408 2410 2480 2399 2389 2559 2633 2361 2323 2344 2437 2472 2468 2432 2485 2577 2275 2504 2665 2461 2450 2491 2384 2361 2266 2467 2261 2042 2468 2238 2273 2166 2265 2236 2309 2166 2178 2313 1998 1987 2090 2013 1860 1929 1823 1892 1709 1732 1684 1805 1766 1731 1814 1777 1771 1717 1714 1660 1783 1562 1529 1565 1545 1491 1509 1499 1642 1510 1576 1545 1442 1436 1507 1564 1430 1634 1512 1526 1489 1488 1513 1433 1506 1408 1373 1303 1245 1218 1267 1306 1328 1331 1260 1284 1260 1282 1306 1286 1315 1305 1319 1298 1369 1292 1354 1229 1190 1220 1204 1229 1269 1367 1334 1313 1363 1397 1389 1324 1292 1546 1507 1409 1420 1333 1413 1590 1436 1431 1440 1383 1322 1392 1457 1441 1454 1259 1297 1430 1261 1227 1176 1194 1159 1096 1081 1087 1045 991 960 1076 1064 1146 1144 1084 1090 1158 1139 1114 1117 1074 1228 1341 1365 1441 1384 1327 1425 1245 1261 1200 1179 1149 899 984 972 930 993 906 1043 870 943 907 855 914 880 890 930 958 960 921 1025 895 864 948 864 951 831 871 886 884 850 848 818 797 767 799 757 759 730 706 715 712 723 743 728 822 736 698 727 702 698 771 670 672 719 668 667 637 660 665 629 603 631 537 599 606 601 585 619 591 621 635 676 635 641 665 653 631 651 691 583 622 610 575 559 574 527 533 535 552 542 514 539 539 515 527 490 538 495 516 494 489 466 462 481 473 453 483 501 524 563 526 540 513 664 551 505 537 469 457 479 465 419 431 464 458 437 429 469 402 416 459 456 460 440 468 465 479 487 484 592 529 565 639 606 486 548 547 505 519 505 455 590 515 566 525 452 537 542 535 599 586 400 431 393 356 422 480 485 466 462 462 436 440 480 424 400 448 424 407 369 412 428 389 401 343 386 348 357 349 312 351 370 386 388 315 326 345 332 346 349 332 329 379 371 398 368 366 342 399 332 365 370 402 390 397 390 389 368 384 367 339 342 330 318 306 360 340 359 352 294 341 338 343 309 299 283 295 285 315 310 294 346 317 301 322 330 336 310 361 337 298 285 283 305 266 253 317 305 283 248 304 264 272 311 324 311 304 286 372 338 358 338 377 351 336 354 394 438 346 369 385 410 332 350 341 360 386 412 391 425 330 363 384 419 399 377 400 536 505 463 431 371 358 383 364 353 326 324 366 316 355 329 304 400 279 326 268 287 250 255 233 235 255 248 285 274 275 271 278 284 272 262 231 198 237 281 213 218 220 263 243 270 200 234 227 231 198 200 170 202 196 190 200 207 213 184 212 180 195 179 181 196 210 172 187 192 162 170 155 179 170 190 198 198 205 193 187 190 207 208 194 196 161 208 161 195 193 208 205 170 191 188 170 194 190 173 175 167 195 205 246 272 265 286 254 245 300 284 262 316 269 270 320 274 250 296 245 254 275 286 268 245 271 226 227 210 261 239 185 226 234 210 228 245 147 138 137 152 143 137 130 128 154 130 163 133 137 145 159 153 140 144 147 126 137 160 142 157 155 130 135 126 131 135 126 151 129 119 137 148 140 150 138 124 115 98 118 122 123 107 132 122 115 116 113 117 117 117 125 108 100 123 80 107 118 117 97 106 120 122 111 106 124 170 152 119 104 107 115 93 115 118 113 122 105 110 106 138 137 124 112 113 145 122 152 124 117 105 120 128 128 126 147 128 102 109 109 122 97 107 131 120 96 110 135 110 99 106 116 110 131 102 107 111 135 137 119 115 109 119 131 92 95 101 102 121 104 95 111 108 90 116 110 109 111 114 111 106 128 105 113 115 89 103 102 100 93 105 102 99 94 103 107 86 98 100 106 74 91 109 85 97 107 90 90 98 88 106 108 110 102 107 88 108 93 100 106 90 102 111 109 91 91 104 98 94 116 87 105 122 120 94 113 110 99 102 101 99 124 120 129 102 109 116 101 113 107 93 85 108 110 90 111 113 93 80 88 113 77 91 117 100 98 81 88 88 114 89 103 108 84 80 88 96 104 115 89 90 104 102 90 72 110 111 72 95 109 99 101 102 91 87 94 93 96 84 96 90 110 90 79 92 98 82 120 113 100 103 121 100 121 90 113 97 90 131 116 107 105 97 106 114 95 107 105 126 103 88 64 99 96 90 68 88 83 72 95 96 90 86 75 73 89 97 96 81 87 74 104 97 77 100 94 89 114 113 89 112 83 95 88 90 103 134 112 100 103 118 120 94 91 126 111 123 125 142 121 107 99 123 107 122 106 142 101 108 101 385 343 456 521 557 429 394 386 533 247 56 72 66 73 65 74 61 85 58 84 77 75 81 97 76 78 74 79 78 88 84 67 65 80 90 64 65 79 89 90 63 65 88 89 73 89 68 86 94 59 69 92 86 61 80 77 79 59 80 83 65 58 79 69 63 65 70 69 80 58 74 87 63 78 64 86 75 79 68 64 88 67 71 64 48 56 58 60 46 60 47 58 82 74 75 89 76 72 72 68 67 68 76 69 64 64 61 73 46 60 62 68 55 57 75 62 72 75 46 68 61 49 68 69 57 74 63 61 74 63 72 63 76 73 60 69 69 47 67 76 59 64 63 59 70 73 62 62 54 50 55 71 60 63 52 54 71 58 60 56 43 61 64 47 54 66 65 74 63 59 72 59 58 58 57 60 54 64 73 61 71 53 54 51 60 56 65 68 46 54 46 57 53 62 50 66 56 53 52 60 53 60 61 66 63 54 60 69 71 55 58 71 48 52 49 62 60 52 55 57 49 66 74 60 61 66 65 59 68 53 52 61 46 62 57 53 70 70 92 75 88 39 59 53 56 51 47 48 49 52 63 66 42 59 52 45 51 48 33 59 53 56 60 48 37 51 42 34 53 43 60 52 60 54 61 48 46 47 36 53 43 39 48 38 57 48 56 50 56 60 62 60 62 64 61 63 61 65 64 50 62 58 54 59 51 48 43 54 45 66 68 47 51 54 53 50 63 47 41 46 59 61 49 50 
];
B = [
0 0 0
 620077 26579 593498
 335721 16361 319360
 1087199 55824 1031375
 334913 17073 317840
 357708 17690 340018
 483879 24182 459697
 556134 30907 525227
 427750 23633 404117
 1074817 63027 1011790
 414664 32504 382160
 466711 37956 428755
 595119 62489 532630
 706569 46823 659746
 349417 32319 317098
 1028714 60554 968160
 358171 17556 340615
 381529 22676 358853
 399457 22210 377247
 801928 39313 762615
 426683 21406 405277
 1222408 68376 1154032
 746008 35330 710678
 663096 34576 628520
 1385238 60213 1325025
 1949575 96346 1853229
 317742 23382 294360
 5634309 300716 5333593
 182796 22877 159919
 380747 40310 340437
 241097 25444 215653
 372827 31286 341541
 168855 21785 147070
 1175889 86907 1088982
 139302 19099 120203
 291699 30538 261161
 192464 19667 172797
 326312 29092 297220
 89133 14998 74135
 1397341 101953 1295388
 40774 10259 30515
 76821 16863 59958
 84934 15528 69406
 293144 23307 269837
 150826 29149 121677
 68870 13196 55674
 94523 14993 79530
 170129 23404 146725
 2360256 167036 2193220
 78592 21441 57151
 85050 16507 68543
 76494 16147 60347
 116954 22831 94123
 190162 20801 169361
 2586829 195267 2391562
 121559 22225 99334
 87890 15558 72332
 115114 20737 94377
 1231266 89936 1141330
 1056516 92132 964384
 128061264 15721348 112339916
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
46 111 7 1
16 29 2 1
15 26 0 0
26 38 0 2
27 56 3 0
42 62 65 6
731 85 184 30
4380 113 292 121
24767 161 499 252
87579 248 852 548
938511 367 1138 945
1361183 693 1703 1406
1669916 1188 2477 2186
1929215 2340 3517 3293
1880202 4044 4833 4586
1613557 7029 6629 6365
1094335 10553 8347 8288
583644 14789 10471 10289
240996 19113 12537 12783
77049 23465 14608 14724
30236 26806 16572 17292
25185 29121 19562 19840
26952 30386 22828 22113
28859 30720 25544 25194
31129 31126 28181 28559
33796 32405 31079 31417
36868 34728 34598 34557
39271 38112 37824 37832
43862 41836 41962 42003
46901 46058 45931 46309
51143 50098 50415 50527
55799 54297 55090 55145
60898 60364 59909 59491
66337 65224 64871 64918
72071 71094 71114 71020
76901 76802 76538 76635
83199 82584 81920 81900
87865 87543 87314 87227
91831 91029 91141 91233
94134 93235 92807 93656
94143 94395 93626 93850
92080 91748 91178 92299
86731 86237 86192 86915
78818 78458 78884 78733
68364 68733 68462 67950
56223 56308 56444 56543
42967 43074 43131 43186
30285 30445 30333 30531
19721 19676 19843 19711
10870 11129 10991 10881
5043 5001 4904 4959
1658 1786 1707 1699
478 469 484 439
59 92 78 79
4 1 2 2
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
