A = [
407375 403495 2116553 333733 322560 301600 287599 284353 276677 260821 256590 251876 247086 243377 239579 235459 232170 229965 227666 225027 224101 221423 220164 219327 223989 302149 302112 305585 384612 386495 390862 394891 396325 401937 404054 401813 397670 393559 390733 386048 385700 383246 381591 380820 380749 376353 373369 369049 364802 363965 360987 358311 357102 356997 353897 351865 349916 346791 344753 340441 338714 335982 334731 334336 331521 329932 328274 325991 323226 319353 317049 315549 313261 311452 308709 308090 305829 302818 298909 296600 294206 291888 290510 288375 286738 284741 281484 280867 278293 275048 273023 269757 268115 266147 264464 263486 260830 258456 257530 253914 251539 249498 245754 244972 244610 241572 240520 239222 235501 233751 232582 230232 227208 226138 224076 221548 218665 216998 216248 214081 212317 210166 208652 205989 204950 203587 201298 200008 198671 196298 194923 193143 191567 189579 187142 185542 184842 182317 181086 179055 177523 175305 174576 173214 170827 169435 168127 166565 164585 164139 163604 161287 158945 157649 155620 154480 153371 152358 150437 149920 147748 145921 144198 143532 141866 141090 139226 138459 136854 134980 134148 132946 130644 129166 128664 127468 125518 124143 123063 121932 121168 118729 117663 116948 116091 114315 113831 111559 111234 109842 109068 108369 106142 105204 104481 103445 101958 100535 100169 98753 97526 96587 95478 94533 93229 92689 91335 90058 88967 88305 86962 86434 85523 83417 82480 81625 81047 79916 79174 78063 76731 76368 75834 74642 73509 72961 71756 71457 69878 68685 68687 67810 67112 65467 64602 64624 63367 62455 61893 60197 60342 59580 58604 58028 57181 56808 55986 55530 54982 54043 52932 52371 51894 50943 50877 49622 49197 48431 47876 47486 46987 45794 45702 44843 44243 43650 43684 42340 42233 41280 40803 40321 39405 38967 39055 38100 37776 37165 36737 36379 35664 35062 34701 34948 33817 33463 32891 32612 31966 31316 31184 30748 30220 29753 29442 29353 28770 28208 28015 27971 26684 26385 26192 25942 25620 24982 24985 24239 24228 23675 23610 23313 23227 22644 22548 22052 21463 21185 20923 20446 20592 19751 19129 19305 19084 18939 18509 17834 17512 17590 17326 17040 16786 16372 16531 16062 15633 15616 15394 15256 15020 14657 14533 14602 14207 13884 13623 13635 13196 13186 12929 14340 12730 12442 12600 12316 14022 11937 11741 11519 11473 11207 11111 10757 10570 10757 10313 10100 9809 9855 9758 9601 9462 8993 8902 8855 8660 8433 8405 8227 8258 7967 7911 7731 8075 8005 7945 7824 7980 7576 7620 7255 7481 7146 7139 6947 6338 6220 6165 6092 5963 6159 5949 5976 5939 5822 5735 5552 5386 5363 5343 5115 5224 5091 4894 4843 4746 4801 4644 4443 4641 4362 4488 4374 4332 4147 4349 4115 4150 4002 3942 3929 3793 3805 3785 3624 3546 3444 3604 3369 3348 3264 3358 3294 3169 3131 3065 3059 3084 3067 2818 2879 2730 2880 2778 2721 2638 2635 2642 2495 2474 2458 2443 2447 2398 2311 2306 2366 2215 2212 2242 2210 2186 2123 2097 2028 2047 2040 1963 1974 1900 1881 1893 1915 1819 1895 1797 1801 1772 1675 1725 1730 1722 1648 1622 1614 1601 1488 1580 1536 1509 1582 1487 1505 1443 1519 1426 1440 1395 1347 1334 1356 1308 1359 1355 1308 1333 1300 1218 1236 1212 1159 1160 1208 1195 1123 1146 1115 1119 1163 1114 1121 1035 1068 1081 1049 1102 1039 967 995 942 920 989 946 970 975 946 918 917 908 890 892 865 915 819 799 810 894 917 818 788 807 806 810 759 762 829 745 769 734 813 764 705 742 762 715 726 656 675 676 686 680 639 736 648 618 639 619 629 618 591 624 585 650 596 566 611 591 562 568 534 550 568 569 556 518 494 563 559 534 518 506 524 480 479 458 480 486 470 472 505 459 517 471 471 460 447 477 433 442 429 460 507 446 398 443 419 450 398 448 400 402 405 414 387 391 354 427 370 402 376 387 378 377 366 384 391 374 337 342 344 333 321 357 366 368 343 355 355 356 347 301 343 289 320 307 303 306 286 274 317 300 293 309 296 302 285 294 285 283 306 289 281 278 260 286 275 310 263 257 289 319 294 292 309 307 300 321 278 315 280 275 289 280 240 240 281 260 270 257 255 260 252 293 271 258 238 290 282 279 296 285 269 294 279 287 279 328 333 390 291 311 413 477 333 328 322 284 264 277 273 296 261 216 211 227 201 212 221 205 198 228 206 203 243 192 219 217 193 195 233 241 191 209 189 208 228 212 207 205 178 243 227 219 201 222 229 230 207 218 214 208 181 186 173 186 217 184 201 170 201 162 152 141 160 157 146 153 161 156 159 159 172 175 148 153 165 158 197 190 184 185 189 159 141 157 171 184 173 167 188 179 152 153 138 146 165 158 152 156 153 158 160 150 161 141 137 164 136 129 141 140 126 115 98 147 127 109 106 123 142 116 122 119 114 114 130 128 132 120 135 114 93 137 110 123 127 130 132 138 144 147 134 127 140 129 131 128 116 123 117 122 126 112 111 110 137 101 116 104 97 115 87 90 104 107 124 121 120 102 95 112 105 97 95 140 103 109 109 116 124 124 109 103 119 101 106 124 107 108 108 116 86 89 96 81 90 84 78 85 84 72 92 91 83 76 80 100 99 96 79 85 69 71 99 67 89 94 95 97 82 82 55 78 90 78 76 61 86 80 62 62 63 67 75 61 59 65 59 63 69 63 53 55 54 58 54 57 67 55 45 58 66 96 62 68 71 60 72 71 64 64 61 61 63 55 55 64 55 64 44 59 76 54 65 55 52 48 63 56 51 45 69 64 53 56 72 46 57 68 86 68 54 62 58 57 70 55 43 57 58 53 41 38 45 49 53 54 69 61 72 73 48 51 56 50 64 71 60 62 42 50 71 52 47 54 46 45 44 47 51 37 53 48 34 44 56 46 37 37 35 49 43 36 39 43 44 59 46 42 56 48 46 44 48 46 35 50 36 62 43 49 58 29 32 40 54 41 30 38 41 43 37 26 42 43 46 27 36 46 46 47 42 36 42 46 35 48 30 38 27 44 36 50 36 40 36 43 38 41 23 31 38 29 28 34 32 41 31 42 32 28 38 38 33 37 32 35 38 44 44 46 34 32 55 31 55 46 30 47 43 49 39 27 49 41 45 34 36 45 48 38 49 51 45 45 50 54 51 58 49 52 43 47 47 39 40 39 34 34 33 33 44 29 25 31 30 21 31 30 21 28 31 33 26 22 28 28 22 26 23 29 30 21 27 23 26 24 13 23 24 28 23 22 13 18 15 22 22 19 24 25 23 23 19 30 29 23 24 22 25 16 17 26 18 28 15 18 19 34 27 21 25 21 26 14 28 14 24 15 19 20 19 21 20 31 20 20 17 23 28 21 27 28 25 18 35 20 24 22 18 32 22 18 27 30 20 20 23 25 30 28 24 22 22 19 17 26 23 23 21 24 18 19 8 15 18 10 17 20 18 15 20 18 13 14 15 10 19 10 14 7 13 5 15 19 24 14 6 14 19 17 15 12 18 25 19 17 14 15 12 11 15 17 18 13 11 14 16 10 17 16 10 16 17 12 15 16 9 12 10 7 12 7 11 12 13 10 9 5 8 8 10 13 7 10 11 9 23 10 18 18 9 14 18 20 21 16 20 13 18 16 16 13 18 22 18 15 19 20 27 11 22 24 22 20 21 16 20 28 18 14 23 30 25 28 22 27 24 24 22 18 25 31 28 23 26 29 22 15 12 25 26 20 19 11 11 11 15 11 8 14 20 18 18 9 15 14 11 9 12 13 5 13 10 8 11 5 7 8 19 9 13 6 6 7 5 6 10 10 19 10 7 6 3 7 8 6 7 10 8 8 4 9 10 6 5 3 3 3 11 4 8 10 3 12 5 5 4 6 10 9 5 5 6 4 4 7 6 6 8 11 2 6 9 11 5 7 5 8 3 5 7 7 3 3 5 11 12 6 14 6 6 5 8 5 8 12 10 9 8 6 5 11 6 12 4 5 7 6 8 7 5 6 3 4 13 12 8 15 3 5 7 5 2 9 6 4 4 4 4 2 6 3 4 4 7 5 7 9 5 9 3 5 9 8 9 6 6 7 11 12 10 15 9 12 9 9 10 8 7 10 4 16 9 12 14 6 5 5 9 4 3 1 5 8 8 6 0 7 6 7 3 4 4 8 5 7 8 4 8 6 8 3 2 8 6 5 7 9 7 6 6 7 7 4 11 3 2 2 14 10 8 7 5 4 7 4 6 7 7 4 4 9 3 3 9 7 6 7 8 8 7 9 3 3 7 5 5 4 5 5 5 6 4 3 2 4 3 7 7 4 3 5 5 4 7 6 4 5 3 1 11 4 4 7 4 5 0 5 7 2 3 4 8 6 2 1 4 4 5 2 5 3 4 1 4 4 1 3 2 5 4 6 14 8 1 3 6 3 3 4 2 1 0 3 6 1 3 3 3 3 0 5 3 1 2 1 0 3 2 4 4 2 2 4 4 3 6 5 4 5 1 3 4 1 2 3 3 1 5 1 4 2 0 2 0 2 1 4 1 3 2 6 2 2 0 2 3 1 4 3 4 4 5 1 3 1 6 6 3 2 1 1 3 2 4 1 2 5 3 4 2 4 4 1 1 4 4 8 2 2 4 0 3 5 7 9 3 4 4 4 9 2 7 2 3 6 2 2 6 4 5 6 6 4 4 6 8 7 0 3 3 3 4 2 1 4 2 8 5 4 3 6 3 4 5 5 8 4 2 1 5 3 5 5 7 6 4 3 3 5 1 5 2 6 3 6 2 6 4 4 2 2 4 2 4 3 5 2 4 2 1 6 4 2 4 3 7 5 1 2 4 3 3 3 4 0 3 2 3 3 1 3 3 1 2 1 5 6 2 1 5 4 1 3 2 4 2 3 2 5 1 3 0 5 2 4 5 3 7 9 6 2 1 2 7 3 1 2 1 2 0 2 3 1 1 1 3 3 4 2 5 4 5 4 3 4 2 2 
];
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
 838929 245188 593741
 62584 19068 43516
 111713 34036 77677
 593664 191253 402411
 399368 128380 270988
 660334 213466 446868
 1213312 393452 819860
 1017552 321951 695601
 614894 195826 419068
 1413557 469700 943857
 578595 183699 394896
 39854 12692 27162
 1299663 434415 865248
 21471 6968 14503
 37501 12040 25461
 1762842 600321 1162521
 38903 12670 26233
 459599 147214 312385
 2359755 838327 1521428
 454763 147087 307676
 17 10 7
 15804757 5760902 10043855
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
19 62 0 2
11 7 0 0
28 6 0 0
38 10 0 0
21 9 0 0
22 17 21 1
65 22 44 3
235 19 69 13
996 26 78 28
3284 42 108 47
7679 40 139 79
16499 87 188 106
33969 99 249 164
72420 165 349 286
145728 270 489 413
290476 521 709 726
478081 1099 1110 1064
558745 2242 1581 1568
465814 3771 2264 2191
283959 5227 2872 2909
123816 6263 3425 3458
31411 6618 3844 3901
7652 5705 4056 4087
6026 5143 4164 4253
5641 5359 4555 4433
5682 5542 4605 4736
5742 5044 4913 4839
5806 5122 5262 5197
6295 5465 5708 5731
6466 5947 6059 6193
7078 6323 6602 6719
7442 6932 7094 7228
8179 7651 7724 7864
8983 8522 8610 8645
9801 9479 9573 9554
10904 10525 10936 10652
12082 11745 12169 11731
13606 13439 13511 13508
15243 15084 15365 15108
17306 17166 17325 17219
19535 19496 19829 19476
22696 22484 22362 22539
25560 25618 25507 25675
28976 29123 28987 29271
33004 33145 33062 32826
37659 37855 37469 37888
42454 42597 42451 41935
47121 47169 46930 47114
51903 52162 52647 52895
57807 57710 57698 57494
62807 63006 63028 62905
67319 67386 67427 67115
72249 71467 71729 71492
76535 75884 76545 76126
80778 80710 81791 80911
85547 85271 85174 85006
91635 92181 91906 91431
97873 97787 96846 97661
103693 103714 104374 103615
109128 108924 109322 108829
114804 115482 114746 114461
116554 115627 116001 116353
111716 111355 111480 110636
96454 96486 96547 95956
71426 71671 71325 71277
38418 38727 38481 38430
14618 15028 15104 14532
6336 6297 6669 6185
4643 4574 4400 4510
3988 4236 4843 3881
2688 2748 2660 2886
2042 1657 1637 2031
101 99 57 55
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
