A = [
318615 348183 1182138 270045 305486 264780 260454 265412 258746 245490 246065 247079 246348 240735 238684 234321 230992 230912 227264 225863 223580 222528 221123 219132 219314 250728 251582 252120 283159 284950 286401 286497 288598 290034 290345 289971 287220 285607 283128 281754 279159 278223 276885 275041 274557 271173 269825 268267 264586 262225 261192 259367 257050 255842 253883 252089 250279 248322 245703 244204 241661 239212 238096 235767 234152 232482 231270 229667 227185 224236 222976 221541 219107 216520 215413 212938 211710 209259 207711 205358 203952 200549 198296 196836 194991 193313 191025 189273 187242 184666 183402 181336 180328 176910 175495 173854 172628 170127 167950 166865 164556 162280 160849 158677 157880 154972 153890 151938 150080 148782 147175 145764 143437 142586 140288 138500 136846 135543 133731 132365 130800 129584 127597 125923 124346 123614 122271 120423 118822 117533 116356 114537 112784 111940 110652 108810 107332 106658 105040 103729 102490 101399 99733 98525 97010 95951 94795 93818 92752 92025 91060 89375 88879 86964 85627 84711 84094 82387 81586 80533 79879 78222 77248 76137 75456 74518 73449 72746 71325 70778 69758 68494 67334 66803 65754 65024 64270 63074 62068 61227 60685 59910 59012 58376 57478 56996 55850 54535 54403 53465 53457 52200 51716 51004 50131 49802 48747 48347 47660 47037 46300 45850 44876 44200 43974 43239 42791 41990 41715 41083 40336 39839 39283 38664 37682 37424 37165 36595 35813 35727 34927 34745 33984 33755 33555 32765 32398 32290 31440 31204 30636 30567 30005 29746 29050 28416 28241 27679 27302 27245 26846 26372 25890 25690 25787 24981 24824 24262 24096 23791 23660 23028 22908 22523 22317 21798 21467 21531 21191 20536 20801 20060 19885 19785 19698 19386 19219 18718 18604 18045 18098 17846 17782 17435 17239 17113 16493 16314 16391 16500 16056 15751 15584 15421 15255 14889 14393 14653 14172 14092 13991 13828 13715 13884 13378 13270 13223 13064 12868 12553 12377 12260 12022 11888 11848 11723 11425 11302 11154 11090 11094 11014 10836 10491 10486 10285 10447 10159 9813 9720 9750 9374 9457 9364 9114 8977 8947 8809 8648 8708 8509 8455 8397 8240 8144 7961 7907 7732 7554 7555 7601 7398 7476 7258 7234 7400 7002 7008 6824 6844 7015 7408 6610 6848 6443 6250 7074 6386 6409 6189 6176 6078 6079 5967 5864 5845 5943 5774 5574 5704 5535 5354 5395 5232 5134 5092 5079 4949 4976 4906 4809 4824 4679 4628 4834 4726 4610 4574 4557 4538 4571 4546 4504 4366 4271 4189 3934 3926 3893 4051 3954 3955 3803 3942 3912 3751 3638 3712 3687 3714 3597 3515 3640 3532 3477 3438 3233 3323 3225 3290 3128 3164 3153 3172 3082 3200 3097 2950 2924 2932 2947 2959 2866 2846 2841 2789 2886 2720 2784 2556 2726 2785 2593 2678 2545 2585 2485 2603 2474 2510 2437 2368 2538 2327 2296 2283 2285 2220 2154 2202 2209 2224 2152 2129 2169 2199 2088 2109 2095 2064 1948 2088 2035 1966 2039 1949 1926 1976 1879 1920 1838 1865 1824 1751 1823 1867 1819 1739 1746 1795 1763 1706 1678 1698 1688 1660 1668 1649 1604 1625 1604 1561 1512 1604 1560 1514 1572 1521 1543 1502 1485 1502 1536 1440 1487 1451 1407 1469 1405 1464 1328 1365 1389 1370 1359 1332 1356 1250 1300 1343 1337 1297 1275 1323 1240 1277 1222 1224 1256 1232 1169 1212 1232 1162 1251 1161 1164 1200 1265 1178 1180 1153 1149 1108 1117 1086 1080 1094 1032 1098 1060 1010 1055 1098 1034 1033 1089 1006 1082 1069 965 1016 990 971 965 958 970 869 941 958 960 910 963 946 963 921 876 910 898 929 883 827 927 863 837 844 901 849 879 839 810 804 806 807 810 776 815 775 776 795 822 784 795 739 736 746 763 764 787 751 666 709 796 773 683 726 747 775 649 667 660 710 703 647 703 715 679 696 658 615 709 646 693 635 626 587 616 579 601 623 572 608 594 579 608 551 598 604 537 574 537 581 553 550 575 554 555 544 532 543 569 519 555 503 535 499 495 544 530 484 524 529 488 507 501 528 446 465 480 500 481 508 492 456 464 452 494 427 464 490 438 485 447 437 479 465 449 460 422 448 437 422 386 440 425 426 413 417 425 446 421 428 430 449 444 445 459 400 427 434 437 394 420 470 423 368 437 422 432 412 448 394 469 461 402 396 397 413 390 366 412 366 400 357 319 358 370 348 347 330 370 381 356 335 333 343 298 331 348 309 328 329 333 306 320 329 366 367 348 311 314 369 281 320 364 318 324 317 312 319 286 301 297 297 309 295 318 333 302 308 294 253 281 244 294 284 259 277 241 273 262 266 251 277 267 262 270 214 238 254 270 243 253 233 241 255 293 292 236 237 248 252 255 246 247 257 242 270 227 218 220 237 250 225 258 215 228 268 242 225 210 213 230 237 210 199 219 207 203 177 233 206 202 217 198 162 175 186 201 189 169 178 163 182 177 183 192 186 226 182 212 161 210 199 173 181 199 188 189 201 182 166 146 196 197 184 185 166 193 197 153 144 189 169 128 165 175 173 158 149 142 165 143 154 184 160 143 187 159 165 162 162 140 192 140 132 156 172 153 168 143 140 155 146 117 132 137 126 155 147 170 139 140 154 116 138 120 138 118 129 145 114 115 119 126 135 126 163 128 129 117 121 126 119 118 104 107 95 123 108 120 100 105 113 98 107 95 96 108 93 107 101 119 102 85 93 87 95 86 90 88 97 101 114 96 118 108 125 115 101 121 108 80 94 95 84 100 84 91 97 89 90 94 106 98 93 88 105 111 105 105 95 109 96 96 90 88 77 106 86 89 98 102 84 101 84 92 77 85 99 89 82 103 73 97 76 78 71 71 81 94 93 77 88 94 87 85 72 91 99 97 73 102 85 74 89 82 72 82 90 101 92 92 79 87 83 71 90 79 74 88 65 77 76 55 69 66 80 67 95 63 61 68 71 69 87 77 88 72 72 66 65 75 58 53 63 71 59 54 60 52 62 64 57 59 76 69 63 63 58 72 75 59 58 60 63 70 74 69 72 55 66 95 60 61 55 62 73 60 65 53 56 59 63 65 61 61 63 52 60 53 65 80 67 51 55 51 72 60 76 46 75 58 55 72 43 49 66 47 60 41 55 49 68 64 58 64 67 59 51 56 60 79 53 48 70 66 58 65 64 71 53 60 47 58 52 49 59 45 46 56 61 63 51 48 28 39 52 58 40 46 55 63 52 51 42 59 33 49 37 41 58 44 41 40 41 39 43 49 40 34 37 35 40 40 24 35 28 37 58 30 47 37 39 36 32 30 54 38 40 47 33 48 32 51 40 40 38 37 50 42 45 35 44 34 42 37 53 32 30 35 35 38 46 35 33 33 32 32 37 44 39 43 45 29 33 33 37 51 37 39 39 45 47 40 55 49 40 44 41 37 53 38 43 31 26 42 50 45 38 35 43 30 37 22 29 28 36 34 20 25 38 32 30 27 26 32 23 25 25 22 27 31 30 27 27 32 23 30 33 24 29 28 27 33 23 29 30 18 32 24 25 29 29 29 24 27 33 26 24 18 34 22 22 25 23 29 34 36 24 26 25 22 12 23 15 16 16 20 22 26 23 22 22 33 21 29 18 19 20 22 19 20 17 26 32 24 37 32 37 24 19 27 26 28 24 22 26 29 27 16 24 32 26 26 35 23 23 28 31 35 31 25 29 22 28 31 24 30 33 26 30 27 32 35 37 30 19 25 24 30 21 36 25 16 20 12 19 14 20 28 20 26 20 17 21 28 24 15 19 22 25 13 20 16 20 15 22 19 20 16 23 15 22 10 14 18 15 12 17 20 20 20 21 17 20 27 16 16 19 15 18 15 23 23 27 15 23 20 22 19 18 19 13 20 12 19 16 10 11 14 12 14 12 21 8 10 17 15 20 18 25 14 15 14 15 23 14 14 15 13 17 12 14 17 17 16 14 13 8 17 15 18 17 10 12 16 15 14 12 14 11 16 16 14 16 11 9 15 13 21 22 15 22 8 11 10 13 28 22 9 11 9 11 16 15 11 14 18 13 11 13 15 13 13 9 18 16 11 9 9 13 7 5 14 11 11 18 9 15 18 14 14 21 22 15 17 15 12 16 17 11 13 29 15 19 20 13 10 17 13 12 18 8 11 15 12 10 16 18 12 19 14 11 9 14 14 12 11 8 8 13 13 14 11 16 12 11 10 15 9 22 14 13 12 12 10 13 6 12 13 25 15 9 13 13 10 20 15 14 16 17 11 11 10 11 16 10 13 9 8 9 10 17 15 10 10 7 12 8 8 7 9 10 16 11 12 12 12 17 14 9 7 9 8 11 7 12 14 8 10 20 11 9 7 8 10 8 15 16 9 10 8 13 9 13 7 11 13 12 14 7 9 9 16 10 7 6 9 10 11 8 7 17 2 13 15 7 19 9 5 10 6 6 11 9 11 12 7 9 10 14 9 4 9 5 9 7 11 14 9 8 15 10 7 11 6 8 11 7 7 8 11 13 8 5 6 9 10 10 8 10 5 15 13 10 8 13 9 9 13 8 10 6 9 5 6 9 10 14 12 10 8 11 13 13 8 12 10 8 13 9 9 9 5 13 9 9 7 9 9 11 9 12 10 11 9 11 11 15 11 12 11 9 4 6 11 5 7 19 11 15 10 12 12 10 14 22 13 15 10 8 10 8 12 10 14 10 6 13 8 8 6 4 6 4 13 12 15 4 21 7 16 12 7 11 8 9 10 9 11 5 7 5 10 12 4 6 7 8 10 12 6 7 8 12 5 7 5 8 7 12 9 10 8 9 6 9 5 11 17 10 7 10 4 10 4 7 13 15 7 7 11 9 9 14 7 4 5 8 9 10 12 5 8 8 5 6 7 8 6 10 6 11 4 10 12 18 14 13 13 8 15 6 9 7 12 13 5 7 10 9 6 14 5 11 10 9 11 8 8 8 8 10 10 12 15 9 11 7 12 12 12 5 7 7 8 10 5 8 
];
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
 506347 217354 288993
 36554 14841 21713
 64193 26942 37251
 362443 167234 195209
 243899 111928 131971
 406970 191267 215703
 746208 350768 395440
 603272 260552 342720
 375283 172264 203019
 874155 416516 457639
 341555 140947 200608
 23580 9787 13793
 797612 372231 425381
 12585 5217 7368
 22500 9316 13184
 1097917 534035 563882
 23020 9744 13276
 279964 115523 164441
 1525567 808712 716855
 280000 119100 160900
 9 2 7
 10988022 6100616 4887406
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
42 58 0 1
64 7 0 0
93 15 0 1
115 22 0 0
60 23 1 0
55 29 29 0
184 41 55 8
1223 36 62 15
8545 56 91 32
39620 73 148 58
101792 91 164 96
225421 116 239 147
435962 163 312 216
800996 200 398 295
1172149 279 565 440
1374669 416 735 693
1213106 656 1014 993
870601 852 1248 1288
531993 1413 1609 1572
273275 1816 1924 2008
112679 2562 2219 2223
29296 3109 2390 2375
6424 3371 2455 2392
4407 2849 2426 2489
3872 2876 2542 2521
3656 3147 2582 2619
3662 3031 2646 2702
3530 2940 2935 2884
3542 3323 3090 3001
3679 3271 3318 3198
3729 3499 3504 3468
4197 3967 3685 3810
4766 4144 3981 3932
5025 4446 4254 4346
5264 4816 4706 4707
5543 5196 5068 5170
5964 5624 5535 5463
6719 6389 6235 6154
6993 6927 6731 7001
7599 7445 7478 7534
8428 8471 8179 8381
9305 9198 9451 9445
10581 10634 10621 10365
11829 11947 11968 11874
13293 13247 13209 13347
14859 14910 15002 15196
16659 16829 16753 16820
18582 18552 18716 18533
20419 20616 20454 20524
22727 22745 22329 22072
24316 24325 23948 24256
25594 25747 25662 25634
27164 27082 27089 27062
28307 28425 28260 28654
29857 29516 30142 29576
30493 30922 30235 30496
32514 32549 32506 32142
34573 34032 33982 33979
35281 35342 35219 35260
37169 36716 36603 36669
38650 38466 38445 38328
38572 38453 38585 38686
37675 36880 37187 36959
32435 32190 32264 32415
24129 24073 24576 24323
13776 14098 13745 13481
5833 6129 6118 5941
3288 3421 3368 3077
2943 2705 2452 2602
2366 2490 3159 2167
1560 1692 1684 1789
1441 1045 1130 1375
111 122 49 49
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
