A = [
186156 188811 518066 140583 142554 133107 128849 128921 125729 121033 120124 118150 117050 115319 114391 112296 111166 111135 109528 109195 108273 107399 107432 107588 112838 175681 176254 180525 243350 244140 248691 251222 252066 258816 258552 257474 255509 253544 251809 249292 248445 246738 244105 244266 241866 240576 237929 236504 234285 231395 229804 228249 226628 225879 223812 222531 221320 218166 216675 214878 212636 210795 209451 206794 206196 203798 202292 199726 198267 196949 194859 193796 192266 188854 188249 185956 185352 183149 182030 179779 178264 175722 174234 172914 171940 170026 167463 166961 164799 162220 161243 159462 157832 156510 155128 154265 152348 150981 149275 147251 146217 144315 143290 142363 139526 138975 137965 136186 134429 133542 131088 129947 128405 127294 126190 124867 122945 122289 120976 119043 117918 115968 114792 113551 111930 110966 109237 108167 106764 105700 105012 103754 102121 101357 99882 98578 97968 96142 94673 93943 92149 91293 90567 89770 89318 87425 86676 85137 84123 82682 82449 81681 79852 79407 77894 77314 76790 75459 74094 73696 72299 71917 70607 69263 68105 67063 66691 65919 64928 63671 62827 62159 60942 60895 59824 58695 58640 57383 56356 56057 54957 54089 53918 53391 52542 51919 50544 50008 49691 48943 48322 47993 47017 46689 45605 45203 44875 44083 43446 42619 42493 41630 40919 40070 39695 39217 38487 38126 37608 37302 36797 36063 35596 34968 34233 33890 33555 33176 32766 32088 31643 31486 31048 30650 30349 29255 28839 28372 27925 27835 27396 26898 26463 26015 25542 25518 27211 25779 24079 23812 24028 23487 22960 22637 22409 22263 21480 21330 21012 20862 20262 20235 28769 19736 19585 18992 18693 18611 18042 18025 17645 17428 17016 16575 16563 16179 15983 15717 15018 15095 15218 14910 14832 14456 14134 13861 13688 13711 13462 13328 13101 12926 12734 12629 12398 12138 11950 11909 11698 11318 11221 10945 10898 10696 10599 10420 10176 9984 10108 10019 9569 9550 9567 9616 9457 8847 8945 8910 8670 8488 8437 8324 8318 8334 8042 7897 7819 7521 7299 7267 7269 6892 6839 6592 6742 6686 6578 6250 6053 5843 5792 5710 5607 5491 5362 5415 5429 5331 5212 5262 5141 5250 5029 4935 4960 4835 4677 4806 4670 4458 4527 4598 4532 4197 4354 4183 4485 4045 4104 4025 4096 3892 3806 3688 3640 3602 3573 3556 3484 3467 3431 3246 3329 3197 3247 3178 3107 3091 3101 3000 2958 2972 2915 2925 3118 2948 2906 2913 2802 2822 2729 2738 2815 2787 2648 2611 2235 2263 2219 2163 2220 2175 2064 2080 2092 2007 2091 1948 2003 2061 1972 1978 1879 1866 1877 1754 1809 1802 1761 1736 1714 1708 1646 1606 1563 1613 1582 1596 1587 1551 1466 1466 1448 1452 1406 1550 1394 1364 1406 1385 1278 1218 1261 1238 1182 1090 1217 1243 1262 1172 1229 1198 1171 1189 1122 1160 1119 1130 1078 1031 1093 1047 976 1013 993 974 985 949 977 948 943 929 988 910 945 969 924 878 899 880 891 868 846 874 837 844 861 822 771 791 769 806 840 778 819 770 760 743 744 684 731 716 737 743 709 701 705 738 769 724 645 677 696 675 658 717 651 662 622 642 648 661 648 666 619 633 630 612 645 615 622 676 612 597 603 621 602 596 545 570 569 576 588 571 564 681 554 612 524 564 591 575 551 605 534 569 526 530 567 579 537 565 568 543 495 555 564 499 500 495 546 539 542 547 536 497 500 500 471 480 473 426 483 442 456 422 400 479 465 469 507 474 449 452 449 491 464 443 445 467 416 422 410 421 407 426 434 440 420 416 383 432 459 432 403 401 413 396 366 347 341 387 329 328 331 326 373 371 332 372 380 384 358 325 325 317 334 312 302 361 348 334 336 313 332 292 295 278 272 291 286 277 274 287 286 278 299 267 268 252 275 255 286 278 273 300 265 255 265 289 262 268 227 233 254 251 258 261 239 248 221 244 214 234 248 230 232 238 202 217 268 226 241 272 247 265 236 218 252 248 231 255 267 261 291 259 281 259 240 239 237 204 236 244 249 231 245 232 283 246 276 221 231 231 248 228 273 229 254 245 270 232 259 293 243 278 280 287 248 316 256 291 258 263 256 264 267 233 230 222 250 249 220 254 245 249 225 218 256 188 198 199 176 211 206 186 206 194 183 206 202 189 203 211 178 192 213 204 193 181 166 178 171 159 207 179 176 181 157 164 162 183 152 180 173 178 189 178 192 177 179 159 159 135 189 129 136 143 158 162 143 141 146 183 146 143 143 172 148 142 170 148 155 128 140 144 145 163 154 145 152 179 159 160 162 178 173 173 159 149 169 155 142 177 153 145 139 120 141 146 139 138 180 145 130 149 127 123 132 135 131 114 115 115 137 119 125 132 129 113 134 130 110 146 142 121 135 152 130 136 146 119 129 150 135 112 106 122 134 119 113 108 117 119 125 114 122 104 103 103 91 108 98 105 102 103 118 114 93 97 96 85 86 90 101 120 113 121 112 101 138 103 88 83 84 88 95 89 76 96 107 86 95 107 83 79 70 88 85 65 65 76 77 73 72 66 86 80 77 82 66 78 69 80 81 76 85 80 72 77 85 83 68 68 61 62 85 81 54 51 67 51 60 54 58 70 66 62 68 78 60 59 56 85 79 78 55 63 83 69 72 81 50 85 58 71 61 70 70 71 74 65 79 73 66 55 65 57 73 61 70 50 60 64 53 69 45 38 71 50 60 59 66 55 53 49 63 50 66 57 57 47 61 59 67 49 48 59 59 47 57 54 56 57 60 72 45 47 71 61 55 63 67 60 67 71 64 66 73 78 58 71 64 52 59 58 65 55 59 55 64 43 63 45 57 61 49 54 45 59 53 46 46 45 42 25 40 57 50 50 35 50 47 39 51 59 50 47 35 41 38 40 49 37 42 35 48 44 39 42 37 34 38 38 42 34 35 35 31 53 46 39 44 42 47 49 33 34 42 42 45 35 56 41 40 37 41 34 50 54 33 56 49 46 45 36 41 45 32 34 41 39 31 40 42 33 48 40 37 32 44 44 38 45 39 53 56 37 54 42 61 49 60 39 36 29 43 48 41 35 43 40 45 50 43 47 52 48 42 44 44 38 28 38 44 43 29 34 31 38 41 41 34 40 35 22 24 40 28 29 33 25 26 16 28 25 24 31 28 31 22 30 31 17 23 25 24 34 26 25 33 24 19 16 27 27 16 19 15 26 29 24 23 28 20 18 23 24 24 17 26 15 20 24 26 36 16 26 25 37 19 24 21 24 22 22 10 16 25 22 28 25 23 16 21 23 25 23 22 24 21 25 26 23 36 17 19 22 36 27 23 28 28 23 19 28 29 26 20 29 36 28 25 24 28 38 28 26 25 28 22 17 14 29 21 17 28 18 17 18 27 13 20 14 18 18 22 18 12 16 13 14 21 19 13 16 14 23 21 15 15 22 20 15 12 19 11 17 14 14 8 17 14 7 16 11 13 13 11 18 9 8 10 15 10 19 10 13 14 11 15 18 15 10 11 16 22 23 13 16 21 15 11 13 11 13 25 22 17 16 19 11 18 19 20 14 17 24 17 17 16 14 21 12 17 19 17 24 28 21 37 29 20 23 29 37 30 32 28 25 30 29 23 36 25 18 24 21 24 22 25 22 27 25 26 21 17 17 28 8 12 16 18 13 16 12 23 15 17 29 13 13 7 12 12 14 14 16 15 14 17 23 15 15 19 20 15 8 13 10 15 9 9 12 10 11 10 12 11 10 5 7 9 12 10 13 5 6 9 9 11 9 5 18 12 12 7 10 16 8 9 15 14 12 6 8 10 13 14 8 10 13 7 8 14 15 10 11 8 16 11 11 12 11 4 16 16 12 8 5 6 9 17 18 14 12 12 9 6 17 13 9 15 8 11 11 5 9 7 15 8 7 11 12 7 10 10 5 12 13 7 7 9 6 16 1 1 9 8 7 8 12 9 9 4 8 4 9 7 5 11 11 6 6 6 11 5 7 7 6 7 14 13 13 6 8 10 11 10 6 9 13 8 7 16 15 16 13 11 8 8 11 10 11 13 10 6 7 12 11 14 10 11 12 13 10 6 11 11 16 8 11 6 7 9 11 9 5 6 15 8 13 4 12 9 6 4 6 11 7 12 8 8 13 9 11 12 6 2 8 3 7 12 6 4 4 11 9 11 11 11 10 14 5 19 25 42 33 33 32 52 49 37 34 53 23 13 4 7 6 4 10 9 23 16 14 23 21 22 18 14 19 12 10 4 11 10 6 8 4 9 10 3 9 13 11 7 9 9 14 5 7 6 7 7 10 7 7 6 10 8 2 10 9 10 5 5 4 7 4 6 3 7 7 9 6 9 5 8 12 9 10 10 8 9 8 4 10 8 7 11 4 5 2 7 6 7 7 2 3 7 9 6 4 8 5 8 7 6 5 7 6 7 2 2 5 9 6 3 7 7 11 5 3 8 5 6 4 6 9 6 3 3 6 6 6 6 5 9 7 4 2 5 4 8 6 5 3 5 4 6 9 4 4 3 7 6 2 2 4 4 4 3 3 6 5 3 7 8 3 6 3 5 5 6 6 4 5 9 6 7 3 2 4 10 3 7 6 7 11 7 3 5 6 9 9 5 6 5 10 7 5 4 3 6 4 2 8 4 2 3 1 4 13 3 5 7 8 6 2 8 7 5 4 6 7 7 4 6 6 8 5 5 3 3 4 8 6 4 5 9 5 3 5 4 4 6 4 4 4 2 3 4 9 7 2 6 6 4 2 8 7 6 5 7 4 5 3 9 6 5 3 7 3 7 2 2 2 6 1 4 4 4 3 2 7 6 7 6 4 5 7 6 8 4 9 7 5 7 9 3 6 4 6 6 5 2 3 2 2 6 6 3 4 5 3 3 2 5 6 6 9 4 1 5 6 2 8 8 1 
];
B = [
0 0 0
 53199 9131 44068
 32247 5408 26839
 94248 18659 75589
 28717 4398 24319
 29913 4767 25146
 40978 6879 34099
 47469 8824 38645
 35369 6068 29301
 92721 18343 74378
 27416 4638 22778
 30755 5269 25486
 33990 6106 27884
 63938 12067 51871
 25974 4615 21359
 92215 19387 72828
 32697 5452 27245
 35505 6347 29158
 37046 7084 29962
 73766 14425 59341
 44004 7734 36270
 109420 23056 86364
 75726 13776 61950
 59607 10708 48899
 143256 26141 117115
 179935 35323 144612
 25851 4828 21023
 535994 111879 424115
 10274 2367 7907
 24918 5293 19625
 16440 3811 12629
 30046 6982 23064
 13874 2931 10943
 104075 24995 79080
 7375 1767 5608
 24203 5360 18843
 11409 2735 8674
 26924 6483 20441
 3402 651 2751
 120559 29340 91219
 483 125 358
 11356 2803 8553
 3046 647 2399
 26806 5957 20849
 3872 881 2991
 3260 722 2538
 18334 4467 13867
 7716 1734 5982
 188429 45995 142434
 28301 6758 21543
 3719 904 2815
 25756 6653 19103
 8067 1937 6130
 10602 2310 8292
 225325 55856 169469
 11170 2677 8493
 143389 37592 105797
 8831 2286 6545
 11086 2572 8514
 36744 8249 28495
 12254816 3614219 8640597
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
15 32 0 0
18 1 0 0
26 10 1 0
33 13 0 1
21 12 0 1
18 11 9 0
222 12 23 1
1826 16 26 5
8125 30 41 19
22971 44 59 26
42812 48 61 38
86594 67 111 60
153482 142 158 98
235016 213 185 114
275870 443 239 195
283395 860 302 309
244628 1363 380 425
178499 1971 585 576
103771 2505 663 714
41819 3035 850 826
10992 3499 986 1035
2905 4403 1239 1232
1995 5074 1359 1208
1892 4477 1485 1357
1930 3614 1532 1574
2091 2982 1646 1622
2150 2501 1744 1687
2220 2216 1782 1788
2198 2306 1970 1961
2200 2368 2147 2144
2454 2484 2353 2441
2838 2771 2644 2554
3126 2852 2784 2778
3503 3388 3169 3109
3799 3623 3414 3570
4084 4059 3950 4028
4712 4506 4581 4435
5300 5154 5061 5088
5971 5880 5827 5738
6500 6640 6536 6472
7472 7394 7531 7417
8375 8339 8555 8333
9403 9537 9362 9587
10635 10627 10838 10586
12107 12003 12210 11912
13727 13958 13647 14111
15547 15504 15475 15475
17369 17089 17237 17326
19183 19233 19117 19308
20972 21249 21069 21486
22684 22698 22813 22647
24283 24222 24266 24316
25657 25633 25334 25249
26602 26540 26688 26704
27735 27458 27650 27435
28002 27956 28384 28446
29434 29006 29158 28992
29792 29635 29873 29480
30192 30068 30293 29838
30391 30484 30716 30409
31305 31299 31091 31022
30881 30769 30930 30509
29708 29257 29626 29526
26348 26521 26310 26329
20730 20702 21004 20521
12985 13038 13007 12657
6701 7025 7158 6773
5072 4874 5153 4744
4434 4009 3974 4161
4004 3839 4141 3806
2879 2794 2647 3060
2008 1705 1519 2034
142 145 110 140
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
