A = [
5582975 4194934 45005538 1793975 1935442 1748532 1569345 1650507 1504762 1422435 1388047 1330912 1323302 1291385 1249983 1226345 1211545 1213864 1206014 1167469 1157703 1167113 1146323 1122774 1115142 1161532 1154831 1139755 1162902 1034027 1029688 1015489 885795 891851 888713 885377 882789 867647 867455 873702 862313 871531 866936 861649 874762 856790 851372 883083 863446 861841 866916 840968 845332 842454 820710 808895 814759 825323 799295 790379 800699 788695 779331 769676 761385 763990 749535 738909 739683 726667 726270 728092 722815 723902 728636 722821 718327 718056 707335 699259 695523 694435 682170 675565 676674 661264 648765 629821 616386 613158 606278 599482 597456 590393 586043 580508 576573 573237 566777 559733 558063 554507 547685 543601 540100 536905 532530 527505 523493 519419 515766 514754 511158 507696 504223 502836 532747 533777 532017 565153 569260 570297 569884 570792 567503 566284 561365 556895 553925 548956 542765 539642 535169 530069 524552 519661 516478 511774 506610 502352 496556 491807 487654 485018 479638 475253 470036 465274 461314 455785 450569 444983 441468 437072 433099 427149 421987 417653 413935 409368 405026 400182 395445 392112 387753 381778 379107 375053 371664 367897 362772 358823 355790 350999 348196 343947 341410 336448 333288 330187 326316 321299 319591 314914 312470 309259 305308 302328 299098 296744 291538 288896 285702 282042 278604 275813 272671 269141 266628 262942 260020 256322 253541 250857 248553 245071 242186 238597 236485 232820 230008 226113 223954 220205 219110 216355 213824 210658 208502 206196 203628 199797 198872 195789 192972 189888 187366 183577 179694 178599 175685 173259 170870 168241 165955 163841 160615 158844 156893 154511 153066 150545 147589 146413 144983 143094 139979 138805 137093 134949 133244 130574 129575 127436 126476 123833 121934 120505 118495 116272 114765 114213 112609 110541 108761 107374 105972 104254 103248 101733 99948 98704 97366 96142 95084 93994 91879 90372 89094 88072 87163 85134 84237 83174 82024 80640 79082 77644 77122 75968 74754 73927 72654 71955 70400 69834 68766 67656 66976 65570 64581 63570 62318 61799 60766 60071 58728 58371 57253 56601 55525 54344 53711 53725 51889 51278 50788 49735 49004 48316 47442 46919 45929 45595 45034 43998 43797 42535 42042 41216 41022 40361 39438 38888 38506 37709 36808 36015 36022 35512 34730 34847 33894 33154 32884 31934 31529 31043 30743 30457 29763 29313 29188 28372 27963 27686 27048 26423 26059 25802 25300 24950 24377 23917 23686 23569 23314 22601 22108 21834 21711 21077 20777 20669 20417 20057 19506 19093 19108 18254 18188 18060 17789 17598 17040 17037 16627 16418 16184 15710 15553 15279 14972 14747 14788 14458 14065 13727 13616 13682 13139 12955 12846 12707 12407 12151 11981 11748 11679 11459 11301 11089 10799 10754 10565 10313 10232 10045 9864 9785 9463 9389 9227 8985 8850 8774 8691 8401 8188 8238 8192 7815 7805 7590 7548 7388 7431 7228 6987 6864 6785 6618 6690 6469 6373 6181 6207 6019 5953 5698 5846 5625 5693 5482 5216 5267 5210 5094 5142 4993 4824 4857 4711 4633 4472 4534 4418 4196 4218 4227 4086 3999 4008 3864 3883 3751 3675 3670 3661 3580 3487 3314 3342 3260 3293 3221 3154 3078 3093 2978 2991 3009 2876 2827 2767 2723 2675 2587 2597 2515 2517 2540 2432 2371 2356 2273 2297 2223 2251 2069 2228 2111 2118 2072 2022 1981 1886 1974 1943 1858 1768 1786 1738 1816 1810 1772 1705 1685 1580 1578 1509 1623 1554 1503 1454 1430 1446 1443 1408 1337 1362 1292 1332 1345 1285 1283 1210 1251 1230 1134 1175 1244 1199 1083 1076 1056 1075 1005 1053 1048 1034 976 1000 1037 975 947 947 956 934 887 850 898 869 861 851 885 819 821 764 807 768 763 769 787 764 716 703 770 727 718 691 718 665 707 658 641 666 598 627 605 590 615 554 586 558 574 564 511 548 546 562 546 538 538 573 515 518 510 497 512 507 485 486 452 454 452 454 478 490 442 457 443 435 445 387 430 437 468 406 432 360 416 421 385 389 399 374 405 395 374 347 385 370 356 377 351 375 350 332 323 333 333 317 352 356 313 334 299 324 328 313 306 342 311 307 323 288 276 304 329 264 288 301 281 273 259 248 269 291 254 265 246 260 301 288 275 297 255 284 258 269 277 243 243 236 226 252 227 266 223 253 242 223 215 236 220 237 237 234 229 208 222 247 202 211 191 218 204 207 223 190 200 223 223 245 211 187 204 207 223 209 184 188 196 200 183 208 187 207 184 187 201 176 205 193 207 180 182 171 211 201 167 183 186 164 159 187 162 198 151 173 185 161 171 155 189 172 153 155 153 150 164 160 162 161 152 174 149 160 165 177 156 161 168 159 151 148 173 129 169 168 136 149 150 156 160 140 154 134 156 132 135 160 132 121 139 142 151 137 137 115 158 124 131 136 122 133 147 138 120 132 147 113 126 145 117 124 119 120 129 135 135 116 117 132 118 138 105 133 116 108 98 129 113 111 118 107 116 98 111 105 95 92 119 109 104 103 117 93 94 108 112 107 114 111 95 90 101 122 93 104 110 95 94 101 96 98 107 98 77 103 91 92 98 106 90 91 110 82 104 96 89 103 101 74 95 70 78 99 77 76 82 89 68 105 60 88 97 82 76 81 82 86 96 58 96 82 88 87 86 96 98 95 73 92 82 81 70 100 86 83 76 72 84 72 59 82 81 75 70 86 79 71 74 73 84 65 59 84 65 79 86 66 62 75 79 61 69 69 75 68 54 78 76 72 62 51 49 73 55 60 70 64 76 70 58 69 54 55 57 63 58 62 50 65 69 64 67 65 65 65 54 54 72 53 71 69 62 61 73 53 54 56 64 57 52 46 49 55 46 58 55 58 54 60 49 42 62 53 45 50 58 67 41 50 47 43 38 62 52 51 40 51 40 51 46 45 52 58 53 52 49 43 55 40 47 51 64 74 46 70 63 64 61 72 56 67 54 43 64 55 63 64 65 71 64 60 64 79 81 75 74 62 82 82 72 69 81 63 68 74 85 72 91 77 65 81 79 61 65 58 74 75 64 79 52 68 65 74 70 50 64 54 62 73 420 64 66 55 72 58 48 61 51 50 46 46 55 47 55 44 55 53 48 35 55 52 33 53 47 35 43 42 62 44 49 50 44 38 39 34 37 45 27 36 51 31 44 46 39 43 43 44 47 38 38 39 29 39 40 41 34 31 33 34 45 33 34 45 35 30 32 42 51 288 23 23 25 39 33 32 23 26 21 32 30 23 28 15 24 23 24 28 28 25 30 27 29 28 32 24 29 23 23 25 25 22 15 15 20 23 34 25 21 30 37 27 30 27 26 24 26 30 25 25 39 21 27 30 16 29 23 27 23 30 26 34 29 37 27 22 28 29 25 40 21 26 27 28 17 24 29 30 37 31 42 37 39 30 29 25 27 30 32 34 34 29 42 30 26 35 25 34 31 41 35 37 44 43 29 27 29 45 42 27 36 41 33 35 40 41 46 35 35 34 47 46 43 31 41 51 38 37 36 49 36 34 33 36 33 35 22 29 29 33 34 29 18 18 21 19 17 15 26 10 12 12 22 15 11 14 17 11 13 16 15 15 17 16 14 16 12 9 6 18 11 9 13 13 13 16 15 13 14 13 15 15 8 12 23 19 17 11 19 16 16 6 20 17 15 14 16 17 17 14 18 14 11 17 19 13 21 18 19 14 14 17 28 12 16 14 9 10 14 11 13 16 10 17 10 6 14 14 13 12 13 12 14 15 12 16 10 10 10 18 16 11 9 13 11 8 10 14 7 10 8 10 12 9 7 11 9 15 8 6 7 8 8 6 9 4 5 6 5 13 8 10 10 14 6 7 8 4 8 8 6 5 11 7 5 2 5 13 9 7 7 6 9 5 7 7 8 4 11 9 10 7 17 6 11 6 3 11 10 7 4 4 9 5 6 7 9 6 12 11 5 7 9 3 14 7 6 6 8 6 6 13 11 8 4 3 7 8 7 9 8 9 8 8 8 6 12 12 9 7 8 10 9 7 10 11 5 4 6 5 7 11 7 1 9 13 2 10 11 19 8 9 12 5 10 12 5 11 7 5 11 8 4 7 5 11 9 7 13 14 11 14 9 5 18 13 7 19 8 10 8 9 10 8 9 5 8 11 8 6 7 10 7 4 13 8 13 12 12 8 13 4 15 10 8 4 5 8 9 11 6 9 8 7 7 5 7 7 5 8 6 6 9 10 11 1 7 8 8 9 4 9 7 6 10 7 10 8 7 7 10 4 3 4 5 3 5 6 6 6 3 6 8 2 2 1 4 2 8 8 5 6 1 7 0 4 4 6 1 7 2 4 2 1 6 5 6 4 3 6 5 3 6 6 3 2 3 4 3 7 1 2 2 6 3 2 4 3 4 4 5 5 5 5 5 3 1 1 4 3 5 3 2 5 5 1 0 3 2 4 1 1 2 5 5 6 3 3 3 4 3 3 7 2 3 4 3 2 3 5 3 3 3 3 5 3 3 6 5 1 1 2 5 3 7 1 1 1 3 6 2 5 2 3 1 4 5 3 3 3 5 4 3 2 5 3 3 2 1 3 3 1 2 2 2 4 4 1 1 1 2 4 3 1 1 2 1 3 0 4 3 3 2 0 2 2 1 2 3 6 2 3 1 2 4 5 5 1 3 3 1 3 3 1 4 1 1 3 2 1 0 1 4 3 2 2 1 2 3 2 2 3 2 2 2 1 0 3 2 0 0 2 2 1 1 1 4 0 5 1 1 2 0 0 2 0 2 2 1 1 0 3 2 2 2 5 0 4 1 1 4 3 3 2 2 1 1 3 1 3 0 2 1 5 2 3 2 1 2 3 1 2 3 2 2 4 2 2 5 2 3 1 2 1 3 2 5 1 0 2 1 2 0 2 1 2 4 2 3 1 4 5 1 2 1 0 4 1 1 2 4 7 0 1 0 2 1 1 1 1 2 2 1 3 6 1 2 3 1 2 1 0 4 2 1 4 1 1 0 4 0 2 0 2 0 3 2 1 0 2 1 2 0 1 0 2 2 1 0 0 0 1 1 2 3 
];
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
 418014 360597 57417
 365424 311910 53514
 365254 311631 53623
 351003 301146 49857
 387699 328966 58733
 398807 347806 51001
 369787 318014 51773
 594032 491675 102357
 356693 309014 47679
 397378 340152 57226
 571780 481443 90337
 392315 337471 54844
 522720 438873 83847
 360642 314217 46425
 385241 331618 53623
 547595 463652 83943
 394320 341308 53012
 527409 445642 81767
 392208 341465 50743
 508359 429922 78437
 402547 352183 50364
 506679 430101 76578
 409935 356886 53049
 505637 429446 76191
 387313 337955 49358
 533734 453794 79940
 485973 414361 71612
 378872 333705 45167
 493442 421746 71696
 343919 306734 37185
 100424986 96337010 4087976
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
43 203 0 0
9 15 0 0
15 62 0 0
14 45 0 0
6 37 0 0
9 36 0 1
17 33 3 3
106 51 5 3
101395 38 8 2
761444 56 23 6
1601923 78 64 11
3217983 89 115 45
5615919 147 1212 331
9405470 230 4842 1802
13633484 464 5042 2506
16762632 1193 5125 3539
15917048 2758 7475 6419
12399830 5456 11422 10943
7433249 8359 16721 16292
3086268 12019 21843 21808
810232 16110 26481 26689
136907 21891 31343 31358
43797 29323 36237 36674
43634 36945 42415 42775
48669 44994 48649 49116
55106 53634 55325 56170
62067 62273 63227 63629
70168 70993 70701 71843
77973 79745 78935 79653
84655 86555 86299 87398
91532 94710 92749 94720
97871 100990 99229 100248
101917 106068 103653 104686
104697 109306 107586 107680
107211 111077 108683 110273
107804 111132 109099 109832
106511 110813 108029 109540
105618 107941 106345 106231
103353 105854 104190 105622
102429 103673 102477 103951
102719 102804 102199 102816
102862 102929 102725 103158
103805 104590 103984 104982
105903 106383 105989 107046
109470 109824 108829 110280
112955 112922 112540 113188
116029 116068 114927 116384
116669 117564 116773 117757
116695 118035 117484 118407
115862 116582 116042 116740
112425 113273 112389 113694
106801 108019 106937 107906
100678 101917 100801 101446
93370 94852 93337 94343
84518 85605 85331 85358
76213 77705 76926 77323
68730 69571 68296 70024
61568 62567 61984 62212
55591 56312 55779 56525
50468 51147 51010 50839
46635 47236 47085 47454
44883 45236 45131 45387
40648 40992 41035 41252
38904 38900 38745 39403
37228 36712 37031 37545
36624 36253 36365 36895
36146 36377 36049 36523
36424 36602 36319 36831
35928 36157 35951 35927
35200 35167 35153 35779
33965 33759 33755 33847
33119 33186 32514 33287
31451 31601 31489 31873
29264 29670 29442 29305
25777 26043 26117 26270
23188 23336 23063 23392
19881 19450 19424 19704
14586 14296 14216 14384
11779 11775 11466 11772
8783 8758 8793 8831
5220 5284 5250 5308
3285 3291 3482 3374
175 208 172 199
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
