A = [
3802622 3797170 15667132 3765722 3768819 3562068 3499320 3538234 3509329 3425965 3466884 3582448 3668790 3790892 4002935 4131186 4254154 4434824 4445061 4427609 4471667 4409069 4366773 4378146 4492690 6378158 6446450 6547721 8391616 7871370 8044859 8062835 7549489 7710964 7755018 7724009 7602808 7549695 7509289 7414842 7356889 7328196 7304129 7268761 7247343 7182412 7098631 7024381 6934980 6845982 6785360 6730855 6697095 6648285 6597618 6549537 6492590 6424362 6360932 6291945 6223616 6178516 6119881 6077680 6030286 5972743 5917482 5857521 5801658 5733633 5670494 5613305 5547997 5496189 5449764 5389996 5336617 5274907 5219373 5153103 5090461 5025229 4974402 4915834 4861631 4813195 4762956 4707429 4653029 4586408 4531696 4477809 4422188 4369456 4318916 4269924 4219784 4169481 4121989 4068328 4017418 3958753 3911483 3860438 3813719 3766617 3725476 3683116 3628824 3587078 3539795 3490640 3455050 3403725 3357109 3320380 3273569 3231480 3191429 3154727 3108869 3069903 3026054 2985020 2940923 2900849 2864227 2829072 2790277 2752090 2718474 2680150 2648105 2610443 2569129 2532534 2503560 2469734 2432782 2400586 2366359 2332016 2304981 2272680 2238132 2207005 2178884 2143659 2117258 2087112 2069144 2035496 2003237 1975525 1940535 1919430 1889091 1862015 1831923 1807168 1785614 1753747 1727025 1706494 1681787 1654486 1633255 1613001 1584780 1561355 1539913 1515751 1495414 1474998 1453498 1428595 1406146 1388097 1367342 1346881 1326235 1302710 1287608 1266262 1252748 1232867 1211677 1194137 1176909 1157535 1143511 1126927 1108693 1093023 1078712 1059439 1047202 1030601 1012631 996853 982256 969421 952658 941460 925624 912258 898825 884530 871334 859785 844468 832453 819855 803042 792806 781954 769827 756537 744189 734869 722905 712178 702810 691305 679367 668531 659721 650806 638623 626741 618067 609227 599519 589129 578585 570905 561778 555064 543628 533928 527409 523348 513565 504865 498504 491153 484444 475534 469371 462958 454776 447880 441839 435517 429421 420016 412967 410253 402159 394773 389947 381956 376601 372712 365344 359276 354520 348552 344656 340109 334753 328826 324831 320923 316281 308842 304654 300329 294206 293362 291732 283108 281162 274738 270376 266675 260837 257211 254139 248361 245150 241262 237212 234949 230456 228818 224322 221126 219547 221985 210745 206899 204734 202201 198842 195282 192335 190137 187518 183680 180147 179119 179205 178492 174311 171733 167466 163336 159206 156290 162431 153617 150910 146719 145214 144667 141981 135585 133593 130951 129555 128379 125075 124056 121467 119543 118594 116066 115150 113304 112474 111151 110043 108997 107340 106260 104856 102203 102029 101331 100140 101507 99581 96511 95323 94669 100085 91048 94627 89728 90540 87257 86421 84706 82243 81754 80754 80563 77450 77137 78135 74490 73956 71272 69592 69756 68416 67727 66768 65913 64291 63759 63069 61878 67889 68345 66714 66378 66293 66375 67078 65253 66635 63877 62822 60439 51218 50465 50652 50117 49404 49189 48055 48552 47556 47639 45969 46098 44979 44752 43873 43427 42953 43329 42577 41531 41162 41151 39740 39178 39908 38960 38604 37952 37702 37087 36779 36408 36104 35506 34856 34659 34102 33801 33129 32613 32304 32101 31335 31418 30818 30179 30415 29640 29714 29247 29338 28968 28318 27979 27788 27566 27323 26622 26349 26207 25630 25839 25325 24973 24721 24400 24202 24052 23974 23400 23700 23321 23060 22880 22569 22029 22550 21945 21811 21582 21482 21305 21502 20609 20757 20507 20324 20310 20626 20125 19723 19735 19686 19819 19829 19291 18905 18904 19516 19129 19009 19157 18250 18086 18193 17774 18021 17914 17529 17667 17574 17498 17421 17414 17029 17229 17170 17223 17284 17041 16877 17185 16210 15986 16081 16261 15941 15848 15698 15802 15682 15678 15694 15375 15384 15523 15625 14987 14822 14701 14771 14680 14322 14014 13877 13666 13929 13722 13942 13857 13725 14228 14020 13693 13538 13785 13339 13534 13681 13531 13426 13361 13758 13292 13120 13239 13316 13098 12966 13044 12907 12791 12964 12776 13329 12895 12390 12273 12572 11724 11794 11556 11378 11637 12228 11929 11452 11475 11442 11391 11117 11187 11030 10430 11008 11047 11105 11288 11000 10571 10564 10436 10667 10553 10395 10453 10034 10025 9852 9711 9835 10094 9732 9756 9617 9505 9775 9439 9212 9483 9120 9275 9158 9067 9020 9190 8653 8627 8854 8726 8550 8762 8341 8145 8342 8617 8778 8146 8075 8528 8007 8271 7745 7878 8019 7496 7689 7473 7582 7630 7373 7319 7053 7048 7053 7284 6861 7114 6904 7041 7000 6875 6642 6778 6642 6649 6629 6489 6596 6536 7138 6539 6521 6338 6143 6025 6019 6094 6081 6072 6108 6076 5856 6037 5876 5953 5867 5694 5874 5766 5674 5516 5634 5761 5562 5650 5766 5758 5952 6001 6039 5941 5960 5986 5961 6048 5798 5859 5985 5786 5832 5758 5606 5832 5940 6088 5913 5888 5897 5681 5556 5891 5944 5815 5783 5708 5638 5896 5938 5748 5893 5616 6254 6096 6234 6221 5753 6425 5550 5498 6005 5997 6095 6369 5771 5854 6385 6749 5607 5303 5340 5412 5066 5225 5318 5141 4951 4601 4533 4914 4687 4843 4693 4572 4473 4341 4575 4512 4294 4332 4390 4237 4217 4255 4443 4361 4374 4220 4387 4395 4285 4018 3942 4077 4133 4350 4262 4219 4222 4139 4179 4164 4058 4002 4096 4215 3928 4238 4273 3953 4115 3980 3808 3744 3844 3618 3744 3509 3455 3403 3514 3466 3512 3449 3473 3718 3451 3454 3456 3395 3411 3640 3642 3396 3645 3539 3463 3353 3442 3524 3615 3533 3407 3359 3391 3378 3394 3157 3308 3902 3168 3542 3439 3149 3176 3263 3176 3322 3091 3018 3159 3013 2942 3000 2939 3204 3218 2747 2804 3053 2821 2567 2501 2494 2607 2537 2507 2585 2599 2599 2572 2585 2660 2626 2639 2422 2554 2607 2597 2618 2747 2691 2915 2802 2814 3020 2638 2750 2709 2517 2468 2605 2696 2665 2216 2364 2335 2168 2195 2232 2471 2251 2333 2323 2145 2217 2117 2064 2113 2197 2445 2388 2264 2225 2191 2262 2132 2172 2333 2248 2317 2219 2327 2341 2245 2285 2172 2327 2101 2112 2198 2234 2029 2216 2071 1835 1913 1949 1955 1692 1698 1674 1842 1796 1856 1805 1941 2009 1912 1672 1826 1937 1812 1819 1747 1698 1665 1614 1850 1733 1782 1855 1743 1714 1838 1729 1871 1894 1755 1562 1646 1692 1543 1570 1517 1584 1514 1416 1392 1385 1342 1386 1397 1351 1362 1386 1313 1356 1344 1323 1215 1352 1315 1285 1364 1257 1415 1558 1226 1249 1383 1355 1378 1406 1438 1424 1368 1323 1242 1146 1191 1233 1283 1284 1297 1328 1282 1274 1260 1192 1204 1181 1207 1330 1246 1275 1329 1286 1224 1293 1283 1201 1490 1383 1488 1496 1471 1354 1426 1452 1288 1303 1291 1260 1430 1260 1421 1231 1192 1217 1359 1395 1385 1418 1077 1096 1064 1079 1126 1106 1105 1105 1142 1088 965 1019 1018 1006 967 1034 1085 1012 1012 1057 1030 1010 1000 982 938 924 980 958 933 976 935 973 996 927 973 911 876 920 912 837 948 970 955 1002 924 967 961 966 949 918 936 911 941 894 914 873 884 855 844 851 927 848 842 851 954 899 909 889 868 876 907 881 886 907 868 921 847 937 872 853 863 853 905 877 823 856 890 909 877 804 797 767 842 786 787 807 826 788 856 836 728 743 894 954 921 804 877 962 935 971 890 833 889 857 909 994 942 845 860 932 875 804 825 838 876 888 915 850 1070 857 889 1010 925 936 889 939 1233 1222 1268 1219 975 939 945 890 893 855 809 852 864 873 805 766 874 736 686 627 614 642 677 634 608 644 653 577 584 632 609 660 642 587 607 627 592 609 559 590 652 571 633 593 633 624 619 650 467 508 480 455 456 453 464 467 466 467 487 506 458 504 486 465 481 481 451 599 508 445 508 436 434 473 457 471 480 450 482 468 432 458 426 433 491 492 441 449 426 448 440 459 471 482 469 471 433 442 450 423 457 441 471 660 673 611 723 672 564 699 672 629 676 710 591 659 588 565 714 518 574 603 646 625 591 601 600 537 395 428 401 396 404 422 397 412 399 415 398 359 370 340 412 381 347 373 360 385 340 365 382 369 356 374 335 394 349 338 355 347 326 295 299 338 302 308 322 333 342 281 320 343 305 325 300 351 287 310 296 306 283 312 288 294 305 274 265 315 303 262 284 299 297 276 235 246 284 280 263 287 253 283 350 367 414 352 319 389 350 361 423 418 477 322 356 388 444 360 433 396 386 443 414 428 489 424 440 496 518 499 565 502 620 556 523 590 567 645 569 620 502 496 530 606 547 566 528 637 645 612 523 594 587 308 266 293 273 294 278 267 268 254 256 229 276 234 272 277 258 248 228 240 227 206 217 219 255 237 238 207 224 208 200 223 211 221 240 201 197 205 219 192 203 206 187 197 204 189 220 204 197 203 191 181 220 185 157 215 193 181 210 182 194 201 190 193 199 244 187 196 187 183 171 287 201 191 171 157 160 174 173 150 149 169 184 201 171 165 189 175 167 166 171 160 148 155 170 138 165 188 183 180 164 166 155 180 195 150 156 161 200 162 185 175 201 191 193 199 170 215 177 180 184 167 187 171 198 190 196 181 186 153 193 190 142 164 154 148 170 165 185 166 148 183 133 154 137 175 125 130 177 180 164 162 163 180 169 190 178 174 168 176 144 228 191 203 191 175 212 194 195 209 175 178 180 198 171 184 206 211 221 173 151 165 152 146 163 189 156 189 196 180 177 150 178 160 139 162 134 166 149 152 148 149 146 156 139 160 157 138 148 153 138 135 174 156 147 141 137 130 141 143 138 156 190 136 136 135 151 155 159 154 139 125 152 140 148 139 155 133 148 163 137 138 171 138 133 143 139 144 120 123 124 141 126 141 126 137 122 129 138 126 142 144 128 127 142 144 135 139 139 117 103 122 142 126 99 122 160 117 115 101 142 126 166 133 133 134 138 144 142 120 142 104 119 115 97 104 110 114 117 86 103 119 111 91 121 115 121 108 108 93 106 117 122 130 100 83 92 95 108 105 108 103 93 108 93 73 114 95 96 91 83 111 102 101 94 88 102 94 83 81 108 113 98 93 92 93 65 88 106 102 82 69 103 97 78 112 87 96 99 95 115 105 112 110 112 109 88 99 100 98 114 133 107 103 115 87 107 118 106 88 101 109 118 107 105 92 108 106 103 86 100 105 100 89 104 101 102 91 101 75 97 89 110 91 103 110 103 108 116 101 93 99 74 97 67 105 87 99 111 96 99 100 96 101 133 104 77 97 86 101 103 102 90 97 91 86 107 103 95 92 111 106 106 105 111 106 106 109 101 126 106 112 112 109 98 121 93 115 107 94 109 126 101 102 134 114 105 82 111 77 120 102 128 100 121 105 109 115 110 133 127 121 106 123 100 107 103 89 114 120 114 107 101 85 83 84 80 85 98 94 99 100 71 92 84 72 97 84 80 88 94 87 106 83 78 75 77 80 89 93 92 92 98 78 97 86 82 103 83 83 98 106 115 104 113 93 99 112 77 94 84 86 89 97 68 81 73 90 83 78 96 90 97 97 112 82 80 85 102 97 105 92 
];
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
 7572957 2516299 5056658
 1955320 694124 1261196
 2313979 839203 1474776
 5823315 2181781 3641534
 5083484 1899880 3183604
 7063382 2652984 4410398
 11345160 4271111 7074049
 13326900 4964686 8362214
 6826507 2554931 4271576
 13038210 5044981 7993229
 9283747 3495090 5788657
 2297100 896169 1400931
 14092253 5460253 8632000
 1963840 770794 1193046
 2344809 930255 1414554
 17246041 6788119 10457922
 2416695 962370 1454325
 7805701 2994658 4811043
 18729551 7720599 11008952
 7432733 2880073 4552660
 1943129 804249 1138880
 116732179 48365081 68367098
 1929569 817344 1112225
 3270959 1306015 1964944
 1794265 764637 1029628
 3491625 1420692 2070933
 3421705 1413744 2007961
 1880141 821391 1058750
 3371494 1397648 1973846
 1596334 715637 880697
 137559681 64023315 73536366
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
224 548 5 2
118 67 1 3
165 122 1 1
103 143 1 0
59 152 3 1
91 205 130 15
2051 324 350 70
16284 419 596 202
115419 557 1040 502
624459 864 1742 1044
2509483 1244 2393 1784
4201658 2435 3608 2830
5888117 4839 5284 4470
7985012 10849 7739 7171
9636945 21727 10878 10187
11036283 43451 15229 15043
10874834 75616 20509 20411
8944192 115944 26636 26352
5685060 158588 33389 32848
2325846 198264 40596 40119
528188 231494 46910 47338
117689 256318 54082 54074
87085 261111 61936 60931
84981 237694 68366 68148
84735 199621 75160 74357
87972 163141 80799 80512
91214 137057 86675 87422
96400 122936 94055 93481
105027 119333 102224 101800
112059 121082 111594 111534
121724 126573 121191 121071
133360 134811 131555 131871
149053 147523 143310 143500
163101 160995 157775 157555
178382 177027 174116 175132
195679 194699 194568 193602
218702 216939 214587 216073
243273 242866 241268 242968
271623 270192 270375 271210
302891 302101 301422 301672
339145 340912 338414 338495
381026 381204 381977 381563
427679 427740 428117 426249
478933 478588 479686 480535
539761 540425 541806 540369
608043 610127 608746 610405
678507 683907 682792 682655
751391 752597 753856 753518
830225 831884 831370 831456
910350 911914 911012 910340
984783 983277 984639 982772
1047313 1048956 1047723 1049122
1102888 1105334 1102653 1101861
1156641 1156541 1156150 1154409
1209305 1206368 1209137 1211010
1243071 1240871 1240076 1241566
1293018 1291757 1289676 1290519
1324588 1327226 1325262 1322225
1347472 1347241 1349612 1346935
1367970 1369633 1367622 1368691
1388300 1390323 1385459 1388344
1346965 1342062 1342890 1346624
1237983 1240845 1238748 1240143
1027857 1027965 1028432 1030377
734264 736729 737778 735392
403271 402387 403998 401708
171236 174499 170975 176394
104178 102790 101758 104891
94883 96087 88673 98967
77841 85885 85641 79606
57055 58628 55080 63034
43282 38318 35683 45075
1513 2261 1569 1019
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
