A = [
1137144 1122934 6060961 1004629 974314 919702 907000 893348 896119 898282 920549 954410 999626 1054471 1115005 1185305 1256102 1332368 1408816 1485210 1559892 1631513 1700652 1761467 1826222 2069057 2133271 2173882 2396886 2236565 2302075 2331547 2154917 2208570 2193690 2194079 2176944 2122102 2097277 2062951 2027990 1999738 1966629 1941375 1921262 1893772 1885589 1868556 1849428 1842898 1833096 1820525 1809169 1800484 1788941 1779997 1772283 1761552 1750787 1735268 1732147 1717281 1717989 1704090 1699080 1698232 1689940 1793171 1790708 1782036 1888180 1876575 1870094 1861947 1841242 1827729 1813222 1803473 1786211 1769891 1754042 1739575 1721322 1705800 1691929 1674691 1658529 1645196 1626331 1609986 1594753 1578598 1562821 1545197 1531940 1512610 1496124 1478275 1462922 1447047 1430655 1413388 1398055 1380077 1363335 1349188 1332400 1316590 1301672 1285550 1267954 1254003 1236696 1223632 1210643 1193505 1178083 1167126 1151514 1137040 1123473 1106662 1095203 1082067 1067126 1053266 1040952 1027545 1014533 1001062 987782 976976 963508 950077 937467 927156 915035 901155 890739 878334 867190 854238 844174 831650 818750 808975 795958 788326 777317 766413 755904 747075 736000 726557 716713 708349 697985 687625 678413 666175 657845 649425 641888 629061 623050 614968 606759 598795 588012 581508 573812 563601 555712 548042 541797 532675 525837 517990 510233 503553 496021 488783 482773 475745 468815 463501 455639 448415 442844 436477 430587 423964 417970 412314 406245 400595 394064 388659 383756 377040 371408 366935 362094 355394 351135 345932 341325 337289 330485 327119 320837 316453 312593 307915 303470 299872 294604 289802 285240 281342 277507 272696 268951 266312 261348 257626 254464 250839 246975 243186 239289 236190 232204 229279 225623 222036 219719 216390 212120 209572 205405 203757 199926 197577 194205 191232 188072 185198 182287 180564 178107 174875 171942 169353 167171 165248 162035 159212 157230 154918 152308 150770 148593 145964 143953 141515 139958 138234 134880 133500 131279 129341 126958 125445 124158 121627 119954 118182 116011 114601 112677 111427 109103 108254 106485 104565 103339 102071 99490 98403 96402 95019 93491 91950 91406 89704 88391 86728 85228 84399 82888 81537 80825 79475 78263 77306 75815 74407 73514 72477 70869 70658 69140 68529 67331 65940 64829 64321 63419 62237 61483 60668 59154 58420 57917 56536 56386 55587 54349 53960 52907 51849 50935 50232 49485 49395 48439 47323 46907 46199 45471 44938 44016 43615 43002 42240 41537 41231 40327 39823 39067 38675 37933 37701 36972 36538 35774 35660 34922 34368 33741 33262 32676 32437 31773 31558 30957 30634 30170 29443 29731 28721 28513 28092 27833 27186 27302 26454 26249 25831 25504 25081 24739 24291 24023 23697 23531 23217 22763 22707 22013 21927 21588 21327 21175 20988 20702 20163 19997 19739 19737 19011 18975 18769 18417 18165 18078 18037 17531 17361 17042 16906 17037 16581 15996 16093 15883 15606 15437 15411 15177 15025 14883 14743 14626 14160 14080 14000 13765 13764 13494 13127 13195 13093 12976 12807 12711 12251 12327 12635 12131 12082 11732 11684 11638 11513 11395 11246 11090 11011 10873 10646 10643 10805 10546 10405 10319 10134 10050 10104 9980 9725 9664 9711 9584 9507 9383 9298 9306 9029 9063 8951 8947 8979 8871 8629 8527 8492 8382 8271 8283 8173 8204 8024 8064 7956 7921 7679 7700 7550 7654 7603 7579 7525 7581 7397 7291 7210 7134 7130 7082 6936 6853 6868 6916 6641 6715 6799 6658 6656 6497 6386 6577 6507 6464 6244 6213 6177 6195 6181 6046 5890 6080 6042 5934 5947 5779 5870 5710 5763 5847 5608 5674 5649 5749 5559 5579 5452 5563 5456 5359 5108 5285 5315 5243 5200 5215 5176 5132 5109 5071 5159 4986 5025 4913 4919 5111 4956 4879 4782 4864 4725 4834 4725 4639 4679 4582 4703 4554 4624 4581 4628 4556 4500 4468 4512 4485 4429 4368 4267 4373 4359 4294 4301 4293 4283 4224 4214 4232 4103 4021 4009 4095 4100 4105 4102 3992 3959 4028 3877 4004 3865 3897 3907 3936 3792 3800 3825 3844 3749 3660 3666 3599 3734 3616 3829 3719 3636 3615 3576 3544 3496 3537 3453 3443 3367 3370 3345 3275 3383 3435 3428 3332 3283 3374 3255 3239 3238 3195 3207 3234 3141 3153 3131 3190 3182 3204 3105 3096 3119 2987 3073 2952 2970 3058 2990 2964 3030 2925 2952 2927 2904 2882 2807 2811 2901 2820 2795 2818 2877 2816 2905 2761 2657 2735 2734 2719 2691 2604 2728 2709 2605 2670 2600 2653 2594 2614 2614 2408 2398 2533 2458 2502 2469 2441 2534 2367 2398 2418 2453 2400 2402 2322 2376 2300 2369 2329 2283 2256 2275 2301 2281 2228 2175 2308 2198 2181 2305 2212 2163 2120 2189 2144 2174 2215 2040 2062 2098 2241 2083 2051 2128 2039 2051 2069 1973 2092 2046 2108 1946 1982 2034 1977 2062 2009 1956 1929 1950 1919 1930 1895 1877 1906 1761 1870 1855 1816 1850 1788 1752 1814 1721 1779 1740 1722 1779 1791 1663 1661 1713 1708 1707 1692 1672 1734 1678 1621 1688 1703 1711 1637 1610 1715 1611 1586 1695 1614 1599 1583 1675 1629 1631 1542 1617 1503 1626 1558 1517 1531 1528 1512 1513 1511 1438 1497 1482 1482 1470 1464 1435 1437 1464 1500 1372 1382 1433 1401 1401 1425 1363 1397 1392 1356 1380 1388 1340 1339 1359 1398 1326 1334 1354 1324 1285 1265 1315 1265 1257 1339 1265 1265 1262 1226 1211 1246 1223 1214 1200 1211 1193 1262 1251 1226 1154 1240 1209 1221 1136 1159 1228 1147 1152 1158 1137 1155 1103 1149 1087 1097 1119 1125 1107 1088 1143 1102 1097 1078 1094 1084 1133 1151 1111 1070 1081 1103 985 1050 1061 1003 1068 1057 1039 1026 1002 1043 1031 1012 1024 1002 979 982 977 980 999 1019 915 961 891 910 911 955 970 950 992 871 932 947 936 929 860 923 925 842 861 884 852 923 882 861 860 844 889 839 814 863 866 816 825 811 811 816 797 805 854 769 816 778 766 774 793 802 767 718 734 853 752 753 742 732 763 730 720 790 746 750 743 703 748 711 683 757 680 725 712 693 638 689 696 712 726 741 668 661 688 706 670 639 652 711 664 644 642 645 632 613 662 648 592 683 650 695 629 660 625 622 634 577 667 649 621 589 599 614 629 577 587 613 585 564 564 574 592 532 593 588 604 592 603 526 549 591 561 531 558 576 578 577 557 565 544 599 548 543 527 592 519 548 544 542 492 530 510 483 471 517 468 493 457 501 486 505 493 495 468 473 453 482 471 480 472 421 470 488 440 501 453 421 455 452 444 466 476 478 419 440 427 415 479 428 420 382 404 417 400 440 451 401 404 422 407 403 383 407 395 361 371 377 385 386 388 367 352 373 405 361 389 332 344 360 341 353 379 374 384 345 333 366 350 393 370 344 347 379 323 324 299 316 316 290 320 327 328 339 328 309 332 330 298 330 320 366 342 300 304 318 319 342 324 316 290 308 305 290 310 287 273 278 294 327 300 270 266 296 279 273 291 261 275 276 291 283 294 267 288 260 239 288 300 274 279 257 304 246 267 263 269 271 259 249 264 235 251 269 268 250 243 263 248 260 255 247 252 261 243 231 220 272 235 225 249 248 227 222 250 232 251 208 213 210 235 223 206 223 242 213 226 239 224 194 217 214 217 225 205 204 202 215 225 166 216 213 191 217 231 193 181 214 179 202 186 203 193 209 204 204 195 195 170 168 205 189 173 196 190 200 191 192 198 209 189 199 171 181 191 176 204 178 175 154 172 145 160 172 167 188 165 151 171 167 168 198 182 158 182 165 145 161 160 149 180 170 163 157 178 163 160 182 173 173 155 149 157 128 168 160 161 161 168 125 133 135 147 138 150 171 141 151 145 139 151 142 141 141 125 137 126 128 126 145 144 130 154 120 123 114 116 137 122 126 137 125 125 115 118 132 131 139 135 129 141 135 123 127 135 126 105 122 100 118 139 134 110 123 103 112 122 110 103 115 126 120 96 123 107 103 106 100 121 112 110 97 126 106 114 99 103 118 93 89 112 91 108 94 102 96 104 112 90 90 95 85 89 82 108 96 106 101 99 99 80 100 80 99 95 89 92 87 92 95 102 90 102 90 90 82 64 91 77 76 99 77 85 87 89 92 100 87 96 92 84 72 82 87 90 86 98 80 89 84 88 81 73 59 87 90 83 78 85 72 86 75 78 68 82 63 77 74 71 83 68 92 82 79 77 61 81 73 76 65 72 67 69 79 81 68 78 51 76 82 67 71 65 77 72 74 67 68 56 67 80 68 61 41 57 62 54 66 77 60 56 61 55 59 69 62 60 57 57 60 62 78 70 73 71 61 61 60 58 60 60 60 56 52 51 63 50 42 63 58 60 56 57 64 47 42 48 53 54 53 51 52 58 47 43 35 56 55 58 64 46 55 53 52 51 50 55 44 53 47 58 35 53 54 54 54 45 47 50 40 40 41 47 54 44 43 43 45 43 46 44 45 51 45 35 47 45 47 55 39 54 37 55 35 45 38 46 52 47 51 50 39 50 52 39 49 39 43 37 31 28 40 39 34 43 33 48 32 42 35 34 37 51 39 33 32 43 29 32 34 38 44 40 51 38 34 25 38 34 47 49 38 40 36 32 35 36 40 37 40 35 35 31 30 37 31 27 36 34 29 33 31 25 28 23 28 26 34 24 38 18 26 39 28 25 37 24 18 26 27 32 25 26 29 27 20 19 27 32 23 21 27 31 24 27 22 24 29 34 28 23 25 29 27 23 43 31 23 31 24 24 26 28 21 24 24 24 26 15 21 22 13 19 23 24 28 28 21 26 22 24 19 26 28 36 26 21 18 11 27 25 27 27 22 18 18 28 18 22 22 23 12 21 17 20 28 25 24 17 20 14 26 24 13 17 22 15 14 21 19 19 22 18 16 14 18 22 14 19 16 22 15 14 20 12 17 21 19 21 16 17 23 12 22 15 20 23 24 15 13 12 13 23 15 20 15 13 11 21 16 25 16 15 17 9 13 15 20 15 13 13 19 17 16 14 14 18 18 23 12 17 16 18 15 15 19 13 16 12 12 15 12 16 13 10 22 16 14 14 12 17 8 9 13 18 13 10 5 16 13 8 10 11 6 14 14 15 12 11 9 9 7 6 9 7 11 10 8 13 16 9 9 12 11 9 13 13 9 15 8 13 13 7 13 14 9 12 15 13 7 8 13 8 14 7 9 8 9 4 10 9 14 14 20 10 8 17 9 12 9 12 12 4 13 7 6 12 9 9 14 10 7 14 8 15 5 7 6 6 6 7 7 13 7 4 19 12 6 12 5 7 6 5 6 7 6 7 6 7 14 11 7 7 8 6 6 7 8 6 11 8 
];
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
 726934 558120 168814
 699306 537962 161344
 774682 597242 177440
 769252 592894 176358
 985289 759331 225958
 768132 594364 173768
 874047 676053 197994
 1853913 1431247 422666
 840316 651118 189198
 1007334 782313 225021
 1670865 1293347 377518
 1040656 808051 232605
 1586341 1230566 355775
 865072 674524 190548
 1060381 826717 233664
 1645288 1278421 366867
 1050144 820922 229222
 1604913 1249584 355329
 1097053 857124 239929
 1599202 1247375 351827
 1047549 821980 225569
 1579991 1235109 344882
 1185483 927936 257547
 1585308 1241502 343806
 1087981 855703 232278
 1708548 1339211 369337
 1586640 1244695 341945
 1085347 856300 229047
 1603833 1261065 342768
 946804 748388 198416
 106913892 86805515 20108377
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
73 128 63 8
11 25 2 1
16 41 2 2
7 44 4 5
13 54 3 4
16 63 10 4
173 75 17 15
1394 71 25 21
25707 102 34 23
235414 142 209 64
752478 172 1503 318
1784428 241 2307 957
3311166 331 3008 1674
4837548 537 4281 3034
5416155 960 6388 5200
5247518 1799 9597 8820
4230467 3141 13775 13312
2865372 5268 19160 19071
1532341 8756 26600 26724
528975 13462 35833 35677
125479 20302 45510 45865
66842 29668 57011 56900
73302 42902 70539 70060
86260 60079 85131 85899
102216 81533 102982 102674
122168 105819 124134 124404
145728 133215 148686 149067
172633 161873 176197 176021
200954 192410 204671 205195
230994 223631 234848 234928
260744 252499 264067 263813
288427 279489 289489 290955
314422 303852 313362 315449
329514 323965 334171 334982
343717 342192 351273 351252
356671 355942 364881 364202
366493 367812 374467 376407
379101 378978 385935 388009
390656 390401 396873 397770
403531 403930 408596 410283
417370 417571 424134 423306
434035 434156 440191 441401
451637 453570 459813 460124
474449 475555 479156 480799
497022 498451 502269 503316
519006 520290 524092 525581
542457 541341 545826 545386
557817 559030 562425 562548
570671 570896 573619 571876
575332 576503 576883 577189
574742 573614 574019 576704
563433 564861 563805 565159
546904 547741 547599 547243
519669 521828 520057 522270
491000 491621 490405 491152
455704 457017 457094 455738
419132 420432 418419 419973
383483 383632 383224 383793
347548 347691 348237 348175
318196 318209 317702 317116
291471 291691 290822 291331
273581 272528 272988 273392
259239 258587 259195 260258
249433 249390 248624 248977
250313 249980 249827 250228
262703 262691 261610 263035
280485 279917 280341 280802
304748 303372 303518 304533
338987 338886 339862 339594
380852 379854 380061 380369
434630 434489 434200 434818
463116 462382 463917 463489
493239 491396 490540 493424
510480 507667 507114 509166
499897 500904 499680 501989
453251 454879 453619 453375
376686 377856 376663 377452
264775 265488 264677 264500
137098 137019 137100 137103
48858 49056 49386 48784
7678 7781 7812 7789
42 60 45 60
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
