A = [
1029602 1403702 1453264 884239 1786691 1085276 1080365 1561962 1317303 1585297 1117081 1132352 1500775 1205488 1206945 1113984 1225048 1197598 1178312 1169274 1108200 1225788 1165190 1140433 1182836 1098651 1096013 1120823 1194906 1124385 1122423 1186537 1127317 1065561 1031827 1118480 1188034 1073501 1143829 1176730 1055798 1025100 992307 1073544 1003933 1022743 1041036 994375 1030722 962439 950964 1002463 963896 986580 959323 936988 963988 905497 918846 898385 894446 910335 886125 899128 879966 864521 882749 860844 878805 849177 871784 868586 829929 841702 820327 839468 874891 858905 856322 859648 843356 829657 814503 820642 798681 806061 797160 768053 760690 754854 753964 753728 741423 741736 738241 734545 724694 715672 707257 699627 697739 694675 694484 689490 682023 685349 676363 671345 667036 658773 661988 651262 647848 645282 638545 637789 633994 633381 635113 624590 623770 618698 616575 611534 605600 602133 598672 599056 592381 586282 583343 575894 577266 572672 569227 567743 560985 559308 555565 555175 552618 545931 541744 536515 534794 532610 527771 525128 521964 520812 516364 510740 509166 505235 504564 501557 498768 493515 491103 488229 481405 481842 480226 475728 474779 472717 471457 468192 463607 460994 456748 456619 452673 451263 448452 444266 444267 438972 438199 434742 432718 433427 427209 425232 422102 419730 417299 413007 410428 410028 400252 399993 394623 393940 390166 386226 385421 378813 376504 372514 367640 367513 362447 365267 360218 357286 355239 347925 346279 343443 341877 340679 338038 333405 332939 327373 324074 319830 318273 315404 314936 309594 307009 309837 300581 299150 297232 294577 295933 290812 289309 287076 285733 283032 280556 277681 277783 274795 273104 272354 269643 267264 265668 262632 260902 261444 258322 256572 254119 253468 252161 249545 247786 248536 244597 242841 241884 240701 240344 236884 235014 233784 232119 232093 229652 227994 227819 224843 224641 222471 221432 219720 218561 217052 216044 212832 213300 211333 210287 208314 207447 205293 205617 203221 202755 201899 199587 197736 197153 198033 194539 193904 193213 191004 188833 188353 190347 186535 186031 183771 183757 182075 181173 180159 178814 180769 176608 174599 174148 173646 172927 171620 172543 172299 168012 167108 166709 165255 164950 163729 163501 161689 160337 161314 157616 158291 157115 156018 154691 153192 153532 153009 152554 151027 148712 148365 147178 146564 145749 144105 144097 142963 142860 140021 141969 140491 139816 138761 138321 137029 135883 134835 135523 133704 134038 132456 132376 132004 130350 130342 129289 127966 127939 127185 126306 125553 124536 125205 122887 123376 122385 122346 122685 120264 120394 119575 118449 117794 117592 116693 116121 115005 115570 114372 112971 113330 112376 111635 110953 111010 110157 108931 108483 107419 107827 106834 106333 105815 105706 104313 104057 103923 102458 102517 101998 101419 101298 100347 99760 100780 99432 99102 98100 97751 97315 96142 96523 95355 95906 94755 94405 93666 92884 92775 91979 91869 91625 92845 90851 95715 89948 88989 88923 88559 87760 91576 88508 93494 85358 86366 85986 84496 85188 84516 83164 83755 82558 85221 81264 82908 81880 80652 80575 79675 80378 78621 78673 79974 78168 77754 76925 76535 78162 77027 76040 76654 74967 74916 74433 73905 75999 75453 72902 72188 73259 72553 72234 71466 73351 71275 71692 69797 71713 69059 68740 69715 68528 67740 67178 69937 67949 66268 65754 69788 65791 65478 64341 65367 64036 64439 64175 63551 63023 63953 62342 64217 64102 62201 61143 61029 61091 61298 61216 59881 61764 59315 61075 59820 59138 58262 59894 57670 58095 56819 57316 56262 56360 57514 55631 55594 54807 54656 54858 54115 53669 53924 53919 53850 53564 52773 52507 52932 51153 51455 51136 51266 50558 50827 51272 51119 49218 49791 49897 49148 50657 52472 48092 52944 47826 47852 48063 46914 47739 46506 46774 47642 46601 46782 45753 45360 46093 44676 44927 45563 44431 44324 44125 44040 43956 44565 44465 42934 43080 42888 43419 42573 42586 42284 43514 41546 41052 41494 40637 41083 41117 40818 42590 39440 39704 40375 40052 40534 40411 40129 38906 40338 41227 37833 37577 46116 38342 39680 37326 39031 36903 37087 36238 39908 36245 36895 35602 36055 35123 36356 35964 34969 35248 34472 34702 34529 34252 34140 33809 36788 33460 34488 33087 33307 33845 32872 32683 32536 32487 33075 32191 32195 31830 31982 33450 31092 30920 31217 30929 31444 32164 30584 30075 29864 30160 29681 30529 29084 29261 29351 29369 28993 28574 28462 28369 28491 29682 28212 28242 27975 27711 27766 27534 27553 27290 27126 26948 27095 26757 26425 26155 26413 26146 27106 25898 26622 26152 25864 26912 26714 26160 25355 25336 24736 25713 24912 25264 24281 24947 24464 25596 24306 28078 24210 23637 23690 23486 23701 24356 24691 23488 23384 22872 22536 23585 23800 23680 22370 22455 23635 22751 21794 23731 22074 21833 21403 20882 21259 21207 21076 21433 21069 21106 20738 20667 21009 20153 20537 20560 20144 19995 20278 20359 20054 19596 19708 19713 19365 19718 19250 19428 18767 18889 18676 19124 19772 18655 19003 18503 18407 18615 18233 18480 18474 18258 18314 17805 17929 18058 17587 17812 17421 17184 17427 16817 17378 17756 17079 17268 16787 17079 16567 16929 16495 16452 16859 16263 16175 16268 16025 16581 16155 15994 15732 15808 17246 16094 15795 15891 15741 16250 15348 14928 15195 15043 15076 14861 14678 14566 14603 14716 14568 14627 15005 13843 14578 13900 14030 14110 13946 13848 13645 13644 14198 13453 13499 13726 13722 13094 13365 13285 13018 13168 12877 13104 12883 12588 12646 12772 12817 12582 12582 12370 12119 12381 12585 12164 12132 12064 12212 11830 11849 11942 12058 11776 11634 11638 11647 11454 11513 11426 11493 11495 11126 11371 11061 11244 11023 10925 10927 10872 11003 10570 10775 11087 10793 10495 10611 10413 10689 10434 10310 10425 10351 10309 10356 10115 10201 9986 10064 9958 9934 9999 9873 9850 9781 9699 9922 9545 9521 9576 9396 9458 9415 9449 9274 9523 9153 9047 9048 8974 9079 8866 9124 8992 8760 8823 8746 8884 8566 8614 8696 8764 8653 8608 8519 8462 8155 8428 8192 8459 8267 8034 8109 8199 8041 7905 7892 8008 7857 7861 7920 7805 7621 7648 7642 7647 7625 7699 7516 7768 7278 7285 7404 7374 7372 7509 7439 7333 7215 7262 7152 7170 7187 7196 7038 6885 7007 7041 6837 6982 6787 6960 6938 6762 6733 6544 6681 6866 6616 6623 6535 6660 6531 6374 6512 6336 6301 6385 6343 6317 6325 6179 6198 6239 6210 6201 6135 6012 6171 5963 6049 5914 5878 5927 5971 5681 5836 5754 5725 5734 5679 5585 5887 5467 5603 5639 5528 5333 5669 5354 5576 5391 5281 5288 5261 5212 5553 5298 5344 5172 5280 5180 5159 5023 5269 5044 5072 5237 5072 5201 4984 5009 4868 4973 4920 4960 4892 4856 4778 4717 4694 4639 4598 4742 4675 4664 4840 4471 4656 4568 4578 4683 4558 4451 4485 4286 4497 4529 4330 4494 4367 4405 4401 4357 4309 4165 4174 4384 4096 4234 4118 4100 4294 4090 4133 4099 3985 4203 4066 3982 4000 3887 4033 3867 3816 3882 3967 3902 3932 3848 3962 3807 3869 3734 3658 3672 4005 3601 3807 3737 3767 3634 3581 3949 3725 3431 3541 3478 3680 3499 3802 3460 3460 3262 3455 3733 3488 3224 3332 3328 3284 3124 3181 3220 3289 3520 3165 3906 3160 3126 3321 3182 3132 3035 3337 3124 3127 2962 2944 3074 3072 3104 2978 2965 3122 3037 2973 3071 2876 3002 2943 2879 2811 2819 2862 2893 2752 2773 2909 2968 2764 2738 2685 2913 2947 2598 2755 2611 2660 2755 2789 2679 2604 2659 2943 2788 2948 2735 2603 2803 2590 3687 2607 2449 2398 2498 2362 3096 2475 2644 2355 2426 2556 2711 2361 2396 2348 2468 2288 2413 2314 2274 2211 3261 2206 2327 2321 2281 2301 3424 2221 2195 2213 2210 2288 2693 2110 2294 2157 2254 2080 2106 2207 2107 2125 2083 2196 2185 2126 2061 2030 1993 2051 2049 1993 2029 2007 2072 1925 2007 2003 1942 1907 2037 1899 1917 1881 1783 1876 1847 1913 1869 1874 1987 1872 1867 1826 1919 1874 1745 1780 1809 1857 1757 1781 1840 1727 1684 1724 1823 1685 1805 1659 1734 1634 1706 1702 1634 1684 1647 1563 1632 1627 1618 1574 1717 1568 1556 1582 1530 1574 1561 1564 1504 1581 1493 1566 1462 1549 1450 1538 1458 1447 1428 1482 1372 1449 1353 1433 1404 1406 1425 1442 1354 1528 1370 1390 1329 1457 1335 1340 1319 1342 1331 1326 1309 1333 1648 1557 1324 1254 1246 1309 1378 1237 1176 1225 1209 1273 1320 1241 1257 1243 1296 1202 1271 1294 1267 1251 1238 1180 1174 1156 1244 1258 1199 1151 1209 1145 1156 1138 1113 1276 1186 1068 1167 1063 1196 1071 1108 1103 1102 1061 1050 1097 1047 1041 1081 1062 1079 1070 977 1062 1062 1072 1003 1039 1041 1049 982 1031 952 950 968 1000 986 989 938 973 959 960 1025 965 1003 896 918 882 941 921 951 911 937 940 885 911 971 893 918 936 871 896 909 853 799 848 854 920 871 861 876 844 867 851 778 798 849 818 853 774 727 787 816 886 776 781 796 754 788 755 726 809 713 825 755 802 756 747 681 670 770 686 806 778 721 758 672 707 645 730 663 766 728 698 742 651 705 720 740 700 739 711 686 682 689 668 683 678 729 628 653 625 605 664 711 631 581 618 610 609 675 653 660 635 593 649 630 581 601 565 580 629 599 619 641 546 619 585 603 597 599 557 664 565 585 551 546 555 564 554 562 517 560 543 506 468 528 479 529 493 488 476 522 494 476 571 492 493 454 525 520 473 551 473 490 518 457 521 439 517 449 419 464 458 428 501 434 444 483 445 452 454 448 443 437 434 461 463 509 445 416 469 411 454 402 427 429 437 447 395 479 405 401 433 433 420 411 413 391 435 413 393 412 415 410 390 384 400 424 358 381 441 369 369 377 392 349 335 389 409 378 330 383 355 364 366 385 365 328 344 348 360 386 286 368 275 340 342 333 347 362 315 363 328 344 349 333 312 365 317 350 301 323 326 350 309 312 291 334 290 324 319 288 305 281 274 314 285 271 300 275 267 282 281 324 259 273 282 276 300 268 286 263 291 292 251 261 272 279 249 271 233 267 287 252 271 249 271 275 238 274 210 225 249 249 266 232 250 224 277 218 200 228 241 243 247 220 269 229 215 235 201 195 210 215 212 217 221 236 207 203 211 229 206 226 196 193 219 226 223 208 205 200 200 249 186 217 192 208 219 186 197 210 195 210 203 197 197 190 176 195 189 189 193 192 186 200 184 170 202 187 193 196 161 170 151 181 177 164 159 172 183 204 179 181 177 151 152 154 160 162 174 160 148 177 160 171 153 153 156 147 148 152 134 155 159 130 149 152 131 155 155 142 134 165 137 175 163 110 140 155 136 156 118 143 132 131 142 150 117 131 115 156 141 145 128 148 130 161 154 137 124 130 132 139 130 133 121 121 149 174 120 115 142 147 138 109 141 137 118 124 138 120 135 127 113 111 100 146 137 115 137 124 140 132 121 135 133 136 107 133 140 124 116 97 115 108 97 147 111 109 105 112 133 100 91 135 120 117 92 92 110 110 89 89 103 106 97 112 100 101 95 97 114 88 103 93 92 103 97 108 92 109 96 78 105 84 92 89 99 78 101 85 85 104 93 90 100 78 83 77 74 107 91 87 98 92 106 77 88 84 82 112 62 83 86 83 71 73 84 72 93 87 67 73 64 88 73 75 79 76 70 76 76 76 71 72 83 66 71 72 75 65 67 86 67 
];
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
 490768 406649 84119
 498650 417306 81344
 506948 423557 83391
 470402 401619 68783
 629432 526915 102517
 484831 414152 70679
 510203 431658 78545
 1305937 1095584 210353
 493712 426849 66863
 624294 533648 90646
 1145023 966453 178570
 620421 530231 90190
 1032046 876289 155757
 510150 441799 68351
 629011 538755 90256
 1073395 909620 163775
 632672 544689 87983
 1040469 885507 154962
 624260 538449 85811
 1007262 860738 146524
 630945 541570 89375
 989476 844944 144532
 664373 572164 92209
 997923 855560 142363
 649578 563396 86182
 1071951 914498 157453
 945464 814121 131343
 610079 532038 78041
 938724 808822 129902
 477998 420843 57155
 85644734 77608213 8036521
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
62 5 1 1
1 27 1 0
2 41 0 1
3 58 3 4
2 58 0 1
5 244 4 5
196 211 22 18
4327 368 38 46
45870 508 83 82
215546 839 146 149
580202 1275 264 282
1092268 1813 635 651
1484891 2795 1526 1472
1848969 4466 3842 4049
3040246 6719 8619 8519
8885319 18308 20260 20016
8028434 32942 44848 44883
5759683 56198 72007 71525
3779664 92022 99241 99618
818705 132713 138569 138775
220823 176935 176178 177503
236167 217007 218780 219379
258125 274593 261778 262930
292294 320343 304329 305387
318942 369066 340936 341179
347113 403658 369323 370249
366320 424230 387321 389064
378614 427824 393782 394266
378631 415361 387332 389774
371973 390284 373345 375684
353945 358043 350715 352196
330435 327338 326079 327364
308498 303794 304744 305130
290271 286293 287467 288692
280282 275460 276375 277450
275026 269959 272100 273210
276478 269782 272874 273429
278819 274055 276721 277252
286632 281810 282278 285170
297027 290970 293423 293477
308707 303975 306320 306228
325931 320422 322073 323837
345402 339523 341905 342053
362674 358370 359192 360445
381645 375226 377528 377768
396988 391214 394565 394177
409086 404418 406722 408192
417402 415038 415102 416101
419783 417313 417993 418846
416771 413939 414036 416123
403900 404800 404555 404734
386395 386384 384761 385814
361527 362276 360673 361489
333591 332825 332655 334255
300886 301616 299294 300424
267741 268780 267919 267911
236237 235161 235170 236127
204451 206351 205149 205271
180715 179558 179746 181377
159112 158720 158863 158575
142442 142819 143144 143345
131122 130453 131712 131051
122441 122807 122604 123223
117673 117047 116545 117410
114294 114164 114153 114361
114883 114048 113491 114125
115894 115945 115152 115638
119523 119204 119123 119168
124133 123598 123477 124487
129957 130309 129762 130477
135884 135369 135118 135409
139051 139394 138492 138950
137723 137215 137737 137650
126460 126369 126090 126073
110142 110489 109855 109796
91722 90705 90540 91154
70262 70367 70516 70293
50705 50369 50081 50324
38825 38703 39048 39375
26053 25971 26020 25990
15437 15646 15607 15670
6272 6108 6201 6113
301 269 319 283
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
