A = [
3244806 3396953 19835551 1638978 1626089 1519048 1317072 1324850 1285249 1351299 1560438 1842186 2154981 2422524 2680962 2868489 2841536 2806785 2816710 2687749 2651036 2719123 2684607 2648331 2660701 3004749 3039851 2975935 3227310 2734001 2687096 2589999 2037867 2039792 2021307 2007936 1997089 1947579 1956064 1960168 1957949 1955214 1948133 1949228 1940804 1921239 1952392 1976991 1953423 2013863 2035127 2020302 2045688 2037756 2020812 2005019 1993498 1980957 1955553 1927651 1940024 1927996 1918026 1904696 1890046 1882880 1851639 1923594 1954078 1954677 2062721 2120907 2143898 2160870 2176507 2172038 2162635 2155986 2137499 2125730 2110443 2103986 2094657 2081510 2075517 2047497 2017021 1975969 1936594 1924748 1905110 1893940 1887690 1879705 1863434 1854648 1831958 1818081 1791360 1771229 1758099 1744707 1727443 1726041 1717375 1699896 1688893 1666224 1647455 1632094 1613598 1599698 1589572 1582387 1570378 1564492 1551615 1534397 1518224 1498861 1485823 1469456 1456591 1444483 1439162 1428609 1416378 1400822 1383604 1362550 1352766 1335377 1319756 1312854 1306344 1296173 1285769 1274179 1255898 1242770 1228763 1212631 1201341 1189597 1179702 1169956 1161182 1149801 1135756 1123066 1107431 1092562 1083189 1069933 1059661 1048107 1041610 1028608 1018992 1006034 995527 980197 967817 956194 948587 936494 929993 920452 910504 899697 888425 876388 864597 853364 844964 836951 826489 821283 811972 801385 790117 779341 770959 759188 749004 741084 733601 725044 717018 709200 701393 692076 683273 672989 664265 654236 648212 640794 634433 627256 619442 610743 602003 592803 584213 576441 570859 563134 557777 550435 542539 536244 527655 520016 512598 507075 499880 493381 485439 480709 474172 465887 459690 452551 444140 437786 430544 423044 418393 412106 408171 400335 394609 387505 381010 374982 368962 364050 359276 353532 348970 343243 338569 331969 326699 321164 316123 312820 307120 302252 298492 294552 288829 283439 279655 275238 269799 266109 261332 259053 253565 250216 246245 242509 237699 233413 230495 225701 222302 218647 215618 212294 209024 205710 202374 198136 194600 191374 188736 184870 182446 179795 176785 173396 170824 167941 164763 161688 158579 156597 154315 151394 148621 146895 144220 141170 138805 136447 133893 131945 128907 127269 124908 122279 121065 118705 117110 114378 112699 111053 108328 106838 104919 103176 101538 99460 98049 96080 94265 92622 90744 89315 87821 85898 84170 83013 81514 80061 78673 77270 75750 74237 73237 72028 70322 69907 67926 66876 65475 64048 63121 62111 60443 59899 58365 58106 57027 55316 54536 53458 52318 51584 51008 49839 48570 48134 46955 46454 45567 44670 43869 43366 42117 41442 40456 39686 39229 38757 37701 37200 36665 35980 34828 34474 33946 33303 32669 32124 31471 31132 30387 29793 29274 28733 28364 27511 27367 26568 26282 25748 25301 24640 24142 23840 23612 23078 22726 22222 21746 21485 20959 20845 20205 20124 19588 19086 19003 18461 18203 17614 17601 17292 16822 16482 16472 16035 15628 15489 14951 14914 14423 14464 14035 14047 13530 13404 13199 12919 12662 12323 12243 12092 11894 11568 11222 11031 11030 10966 10687 10270 10086 10033 9799 9645 9621 9354 9121 8915 9024 8627 8526 8480 8312 8194 8028 7909 7675 7604 7486 7114 7232 6975 7067 6851 6691 6656 6548 6492 6161 6182 6190 6171 5889 5737 5731 5636 5547 5371 5373 5245 5175 5014 4955 4994 4890 4788 4714 4579 4505 4441 4334 4365 4337 4188 4125 4100 4016 3929 3865 3834 3753 3667 3632 3527 3589 3454 3372 3270 3377 3341 3158 3203 3231 2982 3038 2967 3053 2848 2894 2825 2690 2749 2700 2568 2473 2598 2575 2556 2469 2439 2398 2379 2274 2319 2227 2203 2187 2158 2166 2119 2083 1988 2042 2015 2029 1973 1976 1946 1894 1869 1819 1711 1813 1759 1713 1651 1641 1685 1675 1608 1574 1590 1615 1576 1592 1520 1480 1460 1434 1469 1393 1411 1383 1426 1287 1380 1367 1276 1302 1322 1291 1337 1281 1215 1200 1247 1231 1194 1223 1174 1157 1109 1120 1084 1133 1066 1015 1073 1055 1068 1013 1045 1017 1024 967 989 960 980 937 945 971 910 869 938 857 862 952 830 872 816 820 831 850 774 811 801 794 830 754 759 770 720 733 755 704 733 773 766 769 693 734 715 663 697 709 679 684 716 647 656 610 609 664 661 616 636 607 629 570 616 611 557 567 578 566 546 542 515 558 589 564 522 550 596 529 555 532 563 562 532 568 514 544 501 489 547 511 517 499 495 478 521 496 510 476 477 458 501 413 448 445 433 464 459 429 435 458 429 448 418 429 404 447 427 412 447 405 431 435 405 441 406 405 373 389 391 399 425 393 409 362 377 370 374 373 370 409 372 355 360 343 367 376 376 376 347 341 367 351 329 325 349 342 341 317 338 324 349 335 323 314 352 346 304 318 320 321 357 355 311 308 308 327 268 313 303 312 303 278 280 288 302 315 317 278 286 263 296 266 309 275 265 237 245 261 242 263 269 243 240 264 267 277 268 222 260 256 270 236 263 253 249 250 261 250 238 240 223 231 222 260 235 230 233 249 238 236 234 238 228 222 234 205 221 221 235 217 223 208 208 236 189 215 227 200 215 223 213 201 221 221 208 194 189 211 220 226 181 218 185 199 192 205 201 165 182 200 188 224 188 210 188 190 176 201 184 200 196 171 166 142 164 174 174 172 176 178 174 148 165 172 166 186 173 155 178 160 174 180 155 151 170 125 161 151 161 155 168 158 137 168 154 157 151 142 142 160 177 139 167 159 139 144 147 133 128 172 160 146 119 156 140 141 144 157 147 121 137 145 127 122 141 127 130 144 120 127 130 131 129 136 108 126 118 128 109 135 102 125 113 112 123 117 142 126 118 95 115 117 115 107 123 117 135 116 125 110 111 112 109 106 115 115 102 111 109 118 91 107 123 141 118 108 113 105 88 113 111 102 120 117 113 108 91 83 109 92 74 95 102 83 109 88 113 96 86 107 87 93 77 91 97 85 111 88 90 92 90 109 91 78 92 93 103 86 93 100 85 75 74 86 88 77 89 90 76 77 76 84 90 80 82 81 87 89 70 81 72 88 73 78 80 67 69 82 66 72 69 77 75 69 69 80 66 73 75 72 92 79 71 76 51 62 61 83 62 78 89 57 70 70 54 58 59 65 81 59 70 55 61 79 70 63 74 60 53 58 65 63 66 53 61 62 67 63 60 70 54 60 72 52 51 52 51 60 58 55 68 65 67 68 57 56 60 66 53 52 58 67 52 50 48 60 59 55 41 69 59 38 42 59 51 55 41 43 60 38 68 42 63 51 54 47 52 45 47 53 49 49 42 40 62 60 53 44 55 39 48 48 36 50 49 42 51 52 46 39 45 49 55 38 34 37 42 52 52 48 38 36 54 38 45 41 41 48 38 43 43 25 46 45 43 45 33 28 39 40 42 42 35 42 33 41 31 42 33 44 37 33 35 28 40 47 39 38 31 33 38 29 32 33 27 38 36 26 36 28 40 39 30 35 33 34 37 38 40 26 32 23 28 36 24 41 36 53 30 35 41 38 36 52 43 33 46 43 32 29 28 26 29 43 43 33 34 45 34 35 39 31 26 36 45 34 32 31 44 45 36 35 25 42 23 29 21 28 32 15 25 32 38 21 21 30 27 28 29 34 28 22 30 17 18 30 28 24 21 33 28 23 30 18 24 15 21 17 20 27 24 26 19 35 18 20 21 37 20 24 22 20 21 24 25 27 32 30 24 25 15 23 19 31 16 27 17 23 18 12 21 19 16 29 15 16 24 23 21 19 17 24 13 25 19 19 12 22 24 17 18 15 22 13 15 21 19 16 18 12 18 14 17 16 16 17 15 22 22 15 24 16 16 16 15 16 24 16 10 13 16 15 17 17 16 26 23 15 16 17 11 13 18 13 23 20 19 10 12 22 12 18 26 17 15 19 17 18 19 12 10 18 23 24 13 13 20 20 23 14 17 13 21 19 9 17 12 17 21 11 14 13 10 21 12 18 17 21 20 16 13 16 13 14 15 12 21 15 11 14 14 15 19 14 14 13 14 16 19 15 17 12 15 10 9 9 10 19 6 12 9 6 9 8 11 12 9 8 14 13 10 14 16 8 13 9 16 9 12 15 12 10 18 8 15 18 10 15 8 9 11 30 19 22 23 22 17 39 24 20 33 32 30 18 26 36 23 36 19 32 28 37 18 20 30 31 20 30 15 28 26 25 32 25 26 24 49 24 22 18 27 21 29 13 18 22 14 15 20 19 27 29 28 13 37 29 17 18 13 11 21 15 19 11 4 12 13 14 10 8 6 7 8 14 5 11 11 12 11 8 13 6 5 7 9 8 8 9 11 6 9 5 13 10 10 6 16 6 11 5 10 9 12 12 14 10 7 15 14 8 7 6 4 7 9 7 13 6 6 9 8 10 7 12 11 14 5 8 12 9 8 9 10 9 9 8 9 6 5 11 9 2 7 8 4 10 1 5 9 6 2 11 9 5 7 5 4 7 10 7 5 9 7 7 5 9 11 4 10 6 7 2 6 5 11 5 3 11 5 3 6 8 6 6 4 11 8 5 8 4 2 6 8 2 11 6 4 4 2 3 8 4 7 10 2 4 9 5 4 4 3 5 5 6 5 3 12 5 5 5 5 6 1 5 8 5 5 4 3 5 4 3 6 3 6 6 4 3 2 10 0 7 3 6 5 3 7 9 8 4 3 8 4 6 5 5 4 13 6 5 6 9 7 3 1 6 5 6 3 8 5 3 7 4 5 4 4 4 4 5 4 2 6 4 3 8 9 7 10 2 3 4 7 4 2 8 6 4 7 6 4 4 6 2 9 6 2 2 10 2 5 4 6 2 4 8 3 3 1 2 2 2 5 2 6 2 5 1 5 2 0 2 3 1 4 3 3 2 4 1 2 4 1 3 3 3 4 6 2 3 2 4 6 6 4 0 5 6 6 9 3 3 1 4 2 3 6 5 1 9 4 3 6 6 5 2 4 9 9 5 2 2 2 5 2 4 3 6 2 6 3 5 3 4 6 5 7 6 1 3 5 2 3 1 1 3 4 2 3 2 1 2 3 1 6 1 2 2 0 0 1 0 3 3 4 5 0 2 1 2 1 4 3 2 2 0 1 4 1 2 2 0 0 0 2 1 1 1 1 2 1 2 2 4 3 4 1 6 5 0 1 1 4 
];
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
 1404694 1149813 254881
 1058957 876135 182822
 1463260 1200962 262298
 1339908 1092530 247378
 1826416 1498875 327541
 1075559 891800 183759
 1437533 1179063 258470
 2612902 2174304 438598
 1366146 1124867 241279
 1259134 1049510 209624
 2330951 1941250 389701
 1665529 1370948 294581
 2185233 1818717 366516
 1027591 855629 171962
 1559746 1293549 266197
 2209235 1841617 367618
 1213326 1015414 197912
 2150243 1792838 357405
 1542566 1275385 267181
 2088608 1740435 348173
 1160031 971487 188544
 2039611 1699717 339894
 1571191 1300030 271161
 2051672 1707673 343999
 1086271 914863 171408
 2168927 1808566 360361
 1892903 1577390 315513
 1013270 848969 164301
 1928220 1602714 325506
 1191633 980856 210777
 152160269 130503640 21656629
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
50 654 2 0
8 69 0 1
31 132 0 1
37 146 1 1
28 139 0 7
64 117 9 11
1701 149 36 50
33584 211 100 106
353377 248 132 170
1123743 265 232 323
1703189 367 4307 1154
2595871 572 6865 2325
3625172 887 8146 3687
4865137 1638 10059 5543
6282440 3284 12276 8488
7878612 6166 15943 12969
8147292 10184 23601 21777
6148238 16184 36238 35346
3176951 25810 54932 54998
1136850 39110 77511 78266
347487 56624 102578 102557
172952 82146 126319 127825
161039 116626 153625 153862
182669 156602 182060 182677
212958 201556 214486 215458
249634 247573 249844 251431
287551 292814 290023 290512
329456 338174 332695 333408
374798 381671 376245 378378
418110 427394 423150 424187
463855 469523 465023 468336
501630 509859 503774 506074
539836 545416 540370 543177
570093 576285 571391 574547
592190 601632 594622 598589
610327 618891 613352 616898
626024 632695 628869 630627
637666 644448 640602 641673
647745 655713 650584 653472
662002 664670 661549 665937
673704 679676 674113 676483
690807 694069 690721 694478
713801 717833 712281 716082
739422 742022 740062 741711
770659 771764 769101 772536
802275 805622 802588 804452
836470 838580 835098 838369
864048 865454 863305 867763
888832 888822 886763 889281
898937 902288 900032 902613
896404 898978 896094 901080
880287 883081 879962 882179
846439 851651 848094 850862
805000 812207 806012 808791
751052 755898 750680 753875
687554 692898 689495 690622
624465 629830 627704 629778
563689 568329 566365 567860
508672 511681 510156 511485
462959 465241 462636 465134
429771 432983 429959 432005
405881 407657 407570 409060
387180 388851 386963 388571
384031 383652 381701 384658
394281 391727 391199 395278
411538 412464 410570 412414
439319 438597 438706 440301
477104 478296 476629 478027
517251 516722 516158 518167
542579 544025 540794 544527
548349 547328 545670 548984
534584 532016 530667 533391
484961 485578 486192 487896
408984 408169 406708 407988
331089 330315 330986 331856
258523 257521 257762 258577
192126 191368 191399 192479
135428 136086 134990 136222
104174 104454 104047 104143
75273 75095 75280 75434
52198 52259 51658 51804
32429 32342 32069 32459
2953 2913 2824 2844
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
