A = [
361035 360568 1576805 268308 263026 245122 233448 227805 221896 213247 208222 204416 200118 196608 194426 191299 188193 186510 184633 183390 181930 180150 178921 178829 181842 250075 249503 252809 321659 321242 325374 328074 328858 333087 333551 331987 328169 325437 322128 318952 318580 316120 315471 314170 314206 310679 308249 305035 303027 301170 298453 296959 295021 294098 293183 290933 289657 286446 285509 281863 279910 277782 276066 275998 272330 272748 271421 268558 267868 265238 262628 260245 259015 257413 254591 253707 252078 250036 247326 245449 243855 242599 240908 239639 237327 235077 233454 231819 230935 228649 226889 224388 222989 221349 219834 218761 216872 215032 213269 210796 208808 207907 204875 204276 202930 201073 200472 199592 196053 194739 192536 190814 188685 187756 186247 183477 181609 181054 180029 178049 176919 174380 172558 169920 169027 168016 165855 164765 163511 161268 159848 159935 157922 155957 154175 153022 151346 149612 148936 147083 146123 144253 143569 142393 140991 139597 137639 136351 134722 133788 132709 131026 130033 129753 127611 126475 125551 124204 122061 121612 120120 118426 117154 115852 114074 113480 112112 111259 109800 108523 107750 106680 105444 104244 103383 102496 100577 99846 98952 97383 97348 96059 94281 94177 92501 92089 91226 89688 87919 87565 86576 86355 84762 83814 82700 81765 81812 80419 79363 78237 77478 76277 75794 74525 73712 72830 71896 70768 70442 69421 68772 67593 67228 66341 65278 64893 64328 63174 62516 61418 60739 59867 59737 58345 57831 56862 56110 55741 55027 53715 53625 52882 52321 51235 50444 50357 49297 48489 48108 47016 46912 46302 45226 45450 44635 44620 43595 43189 42745 41885 40713 41140 40631 39687 39429 38665 37991 37504 37126 36604 36597 35389 34957 34753 33999 33781 33075 32364 32348 31712 31478 31139 30588 30378 30246 29466 29437 28695 28085 28009 27263 27075 26836 26740 26125 25670 25392 24950 24986 24629 24179 23961 23369 23095 22671 22700 22237 21728 21462 21491 20888 20526 20633 20683 20115 19650 19691 19232 18948 18545 18411 18134 17807 17691 17571 16867 16699 16600 16329 15975 16068 15179 14998 14835 14612 14633 14096 13724 13464 13361 13288 13016 12824 12474 12354 12343 12242 12070 11948 11863 11820 11579 11542 11545 11169 10936 10698 10525 10372 10182 10125 10944 9995 9825 9862 9595 10634 9173 9271 8993 9122 8739 8687 8493 8262 8347 8086 7896 7789 7705 7682 7474 7297 7301 7177 7028 7100 6902 6825 6774 6596 6519 6300 6248 6470 6310 6179 6022 6191 6043 5978 5937 5950 5708 5744 5668 5375 5165 5167 4971 4919 5004 4758 4818 4822 4857 4776 4522 4475 4395 4226 4190 4190 4202 4149 4004 3971 3950 3841 3709 3835 3546 3641 3611 3592 3474 3500 3370 3353 3463 3266 3162 3151 3158 3148 3139 2956 2798 2981 2762 2781 2747 2606 2674 2624 2607 2574 2600 2519 2512 2353 2510 2396 2429 2276 2253 2268 2206 2288 2139 2157 2081 2060 2088 1995 1981 1970 1937 1905 1943 1935 1908 1897 1825 1822 1760 1749 1777 1660 1627 1629 1636 1652 1608 1606 1610 1582 1500 1531 1538 1513 1493 1492 1480 1409 1434 1392 1298 1311 1318 1306 1349 1334 1332 1395 1295 1294 1276 1208 1238 1137 1218 1143 1223 1123 1139 1154 1106 1091 1100 1030 1028 1029 1079 1022 1023 1012 1053 1040 1055 1084 1045 993 998 973 897 991 1037 1004 1021 953 877 938 1003 976 1033 1002 1014 937 902 938 875 837 866 844 833 906 884 888 923 856 887 843 839 877 696 788 718 727 740 765 699 780 763 787 792 795 738 724 741 714 738 645 748 688 652 674 638 663 611 613 650 707 695 661 641 686 627 651 644 568 576 545 563 546 528 537 571 518 541 505 512 512 511 502 438 485 498 473 463 454 474 499 428 458 431 441 466 485 435 395 432 410 420 431 404 441 414 435 439 425 437 419 418 366 370 362 409 332 388 364 387 419 371 391 409 386 370 340 341 341 366 348 357 345 379 344 376 353 329 337 313 315 317 345 330 323 288 300 272 306 300 294 303 277 324 281 330 311 276 340 301 294 293 280 303 292 320 306 270 297 310 281 279 303 268 330 293 272 299 297 270 272 277 254 278 266 299 296 283 299 281 283 316 294 288 244 292 291 254 295 340 286 333 372 418 487 437 394 449 320 357 369 421 301 325 456 363 378 300 315 358 343 307 236 279 259 306 246 208 208 251 212 221 254 224 228 249 200 266 273 298 255 271 263 267 268 269 231 210 212 218 239 253 249 250 221 248 192 204 205 219 203 205 204 176 217 191 202 201 244 198 195 219 241 185 164 200 248 177 196 180 168 176 190 180 185 178 211 191 172 193 181 169 157 193 180 176 180 172 187 174 185 188 188 171 198 197 173 176 171 197 188 171 173 160 180 180 172 162 166 175 161 171 148 169 155 150 126 137 151 117 120 128 118 141 148 124 154 147 155 127 136 153 142 149 147 138 137 175 180 175 151 165 160 132 122 132 141 125 144 126 167 122 110 141 133 94 117 132 108 109 111 128 133 122 126 106 128 109 98 114 108 91 116 158 115 117 133 133 279 134 116 119 112 93 119 108 113 109 110 120 95 105 130 90 114 90 96 92 78 92 90 98 91 81 67 99 105 88 82 99 78 73 97 74 87 101 92 95 90 75 57 83 90 81 66 64 82 79 66 66 71 67 57 62 74 83 78 67 74 90 71 72 83 91 74 73 86 73 64 76 84 92 78 92 98 83 74 71 88 96 69 81 64 76 69 69 88 76 54 58 74 70 62 59 63 63 60 63 56 65 68 66 51 63 56 62 61 68 75 67 59 45 51 59 60 52 61 56 56 56 42 59 57 63 64 66 87 71 51 76 59 44 66 60 75 78 85 75 61 64 67 60 65 72 49 62 53 61 78 56 53 58 55 66 53 59 51 57 57 59 50 49 57 61 44 48 51 48 61 71 67 57 53 60 54 44 54 47 54 49 67 42 35 58 52 44 40 50 46 58 38 45 46 61 44 48 42 51 58 52 50 56 75 47 42 62 41 52 50 59 55 44 56 56 51 43 45 46 50 42 41 39 41 45 47 40 36 49 39 38 40 43 46 40 47 45 48 56 60 56 49 35 55 28 60 54 51 63 49 59 45 38 34 56 44 49 59 52 48 36 50 47 44 44 48 48 42 51 37 39 37 41 42 39 47 43 53 34 34 33 43 33 32 27 29 36 24 29 31 39 29 38 23 30 36 22 26 24 25 27 37 30 31 20 33 25 23 22 18 23 26 19 9 21 17 24 21 26 19 25 17 37 37 33 37 34 22 30 24 28 34 28 25 35 20 26 22 29 22 25 20 29 17 23 20 19 30 17 31 25 25 21 29 38 19 19 21 34 23 26 29 29 21 21 26 21 22 21 26 33 22 19 27 20 18 22 29 22 30 30 19 19 21 27 18 26 29 19 26 24 18 17 13 28 23 19 25 27 25 29 24 14 14 15 17 15 17 10 17 14 15 11 16 24 14 10 14 18 17 19 17 14 12 18 15 19 21 14 16 19 14 23 16 16 16 16 10 16 19 16 15 19 16 12 12 17 9 15 13 11 8 10 12 15 17 13 14 10 14 18 12 8 10 12 21 7 20 20 19 9 9 17 13 10 17 18 21 13 14 21 19 23 18 16 11 25 25 21 37 19 25 18 20 26 37 25 27 39 21 17 31 31 24 23 18 21 28 18 19 18 16 21 21 20 23 32 21 23 19 31 34 19 21 19 16 17 23 22 17 21 22 20 18 15 11 15 18 15 13 9 16 18 16 15 20 13 10 10 20 20 15 10 13 11 8 15 12 11 17 8 13 8 9 11 10 9 6 11 6 12 6 9 13 10 11 12 15 12 14 9 10 15 12 16 9 8 14 13 14 12 6 11 13 7 12 10 9 9 9 19 8 12 17 13 11 12 6 12 10 14 14 11 9 11 15 19 21 13 13 6 6 6 9 10 10 11 9 8 5 4 6 8 8 9 7 10 8 2 10 7 5 8 3 9 21 11 13 17 10 6 10 9 4 10 8 10 1 5 6 7 8 7 5 6 4 3 3 9 11 8 7 11 12 20 5 6 13 9 9 16 17 15 14 13 11 8 8 12 10 17 7 14 9 11 14 9 10 12 22 12 11 8 1 7 10 8 18 12 11 8 14 25 23 26 20 14 16 9 11 19 24 5 6 10 6 6 14 12 10 6 6 7 9 9 14 6 3 6 6 7 8 9 7 10 9 6 6 8 10 4 8 11 4 5 7 54 82 70 75 86 61 47 73 32 7 4 6 3 8 12 9 9 6 7 7 9 4 9 8 9 6 5 11 4 9 5 6 10 9 9 12 6 14 6 15 11 9 6 10 11 3 8 10 9 3 4 5 7 7 12 10 8 10 6 9 8 7 6 4 9 2 7 6 6 5 4 6 6 10 4 3 6 7 4 14 8 10 8 7 4 4 5 2 4 4 5 3 3 6 4 6 4 5 3 5 3 4 3 3 7 5 7 5 2 4 5 4 6 6 4 8 5 4 2 3 5 3 2 4 1 6 5 9 1 1 5 4 6 4 5 6 4 5 4 4 0 2 6 5 4 7 3 5 4 5 5 5 4 2 6 4 5 5 5 3 5 3 4 4 3 1 6 5 3 11 9 7 3 4 5 8 9 6 3 5 6 10 5 5 9 5 7 7 9 8 8 7 9 2 10 6 4 8 2 8 7 4 8 4 4 3 4 4 4 8 7 12 3 1 1 7 2 5 6 10 7 7 9 5 8 5 8 1 13 5 4 7 5 6 3 4 3 9 6 3 5 3 4 5 5 5 10 4 4 5 4 8 6 4 2 5 5 2 2 3 1 4 3 7 2 3 4 2 2 3 1 3 5 3 4 10 3 4 2 3 3 2 6 3 3 2 3 5 8 0 6 10 4 7 5 9 3 2 4 7 2 8 3 4 2 2 0 8 4 2 4 7 7 6 1 5 3 7 7 4 4 5 4 
];
B = [
0 0 0
 134083 27309 106774
 63998 13587 50411
 221053 50688 170365
 143718 30545 113173
 85967 18272 67695
 217455 51517 165938
 176877 39513 137364
 100984 21870 79114
 302089 71199 230890
 317541 70511 247030
 58017 12290 45727
 907359 211785 695574
 121643 28810 92833
 39410 9198 30212
 205152 57109 148043
 66729 18295 48434
 20909 5311 15598
 227952 63747 164205
 18954 4666 14288
 19896 5066 14830
 4855 1335 3520
 101 19 82
 4531 1267 3264
 340998 99338 241660
 22830 5965 16865
 29514 8186 21328
 355299 105502 249797
 20845 5926 14919
 44232 12686 31546
 562708 158326 404382
 41524 12246 29278
 73083 21590 51493
 398145 123355 274790
 260085 80467 179618
 428922 132562 296360
 802587 249950 552637
 675303 205911 469392
 399636 122303 277333
 935574 297608 637966
 388890 119457 269433
 26939 8300 18639
 878614 282711 595903
 14110 4403 9707
 25135 7885 17250
 1188309 387805 800504
 26045 8116 17929
 311136 96573 214563
 1589624 540061 1049563
 305053 95882 209171
 11 6 5
 10633857 3700467 6933390
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
28 69 0 1
12 8 0 0
26 10 0 0
32 9 0 1
27 12 1 0
32 14 24 4
56 21 35 1
105 22 51 11
418 44 59 28
1445 55 80 42
3401 67 114 52
7897 100 149 86
17546 124 200 140
41025 190 257 237
88655 249 419 341
184332 485 545 536
293531 993 853 845
327501 2024 1218 1270
277340 3372 1782 1752
185942 4886 2274 2331
97309 5830 2739 2897
28943 6209 3052 3198
6610 5217 3282 3243
4657 4469 3465 3499
4465 4607 3650 3625
4469 4681 3622 3758
4609 4059 3804 3839
4625 4128 4101 4063
4987 4440 4488 4414
5071 4660 4725 4629
5330 4842 5042 5090
5797 5255 5485 5462
6193 5830 5853 5840
6868 6464 6666 6423
7477 7098 7208 7158
8254 8059 8210 8058
9243 8940 9135 8946
10360 10202 10160 10209
11512 11398 11664 11524
13109 13116 13076 13143
14888 14781 14694 14742
17168 17078 16815 16919
19491 19324 19433 19525
21983 21894 21943 21812
25145 24949 24987 24907
28391 28359 28499 28657
31766 32279 32113 31937
35620 35720 35935 35509
39295 39602 39754 40023
43923 43759 44131 43598
48191 47721 48250 47995
51549 51648 51673 51392
55594 54938 55193 55058
58458 58597 58823 58276
62969 62156 63069 62643
66415 66749 66128 66429
71673 71903 71441 71798
76249 76233 75890 76399
81544 80743 82015 80692
86544 86001 86423 86104
90855 90885 90631 90297
92057 91914 91931 91917
88268 88030 88733 87928
77035 77079 77242 76898
56847 57398 57157 56335
31092 31385 31377 30749
12670 13535 13612 12558
7128 6906 7301 6634
5500 5436 5324 5343
4784 5034 5473 4604
3415 3472 3413 3599
2255 2014 1943 2321
166 144 148 129
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
