A = [
3907807 3816927 15683596 3783467 3786595 3579773 3515515 3554381 3524998 3441443 3482267 3598098 3683588 3806353 4017404 4145515 4268086 4448019 4457999 4439952 4484088 4421799 4379274 4390034 4504785 6389019 6457135 6557051 8402830 7883435 8056721 8074487 7561392 7723915 7768862 7737292 7616222 7562085 7521582 7426713 7368577 7338825 7314648 7279118 7257833 7193008 7108584 7033217 6944558 6855219 6793869 6739214 6704455 6656159 6605100 6557612 6499031 6429291 6365929 6297800 6228833 6183340 6124665 6082324 6034990 5977768 5921738 5861313 5805770 5737876 5674232 5615982 5550991 5499193 5452322 5392253 5339291 5276364 5220871 5154833 5092872 5027278 4976283 4917231 4862604 4814155 4764173 4708463 4653663 4586906 4532405 4477924 4421152 4368710 4317979 4269219 4219023 4168462 4120806 4066762 4015550 3957409 3909702 3858631 3811892 3764895 3724099 3681180 3627047 3585037 3537920 3488894 3452589 3401493 3354961 3318038 3271170 3228617 3188847 3152657 3106605 3067466 3023525 2984950 2938751 2899098 2862077 2826507 2788604 2750855 2717087 2678741 2646570 2608954 2567925 2531231 2502396 2468367 2431645 2399101 2365245 2330651 2303475 2271396 2236806 2205394 2176957 2142129 2115378 2085341 2067087 2033696 2001312 1973532 1938484 1917281 1886782 1859245 1829568 1805157 1783269 1751447 1724860 1703635 1679237 1651902 1630540 1610692 1582698 1558847 1537669 1512855 1492492 1472601 1451220 1426418 1403767 1385965 1365497 1344639 1324694 1301722 1285892 1264615 1251260 1230950 1210369 1192209 1174830 1155838 1141400 1124685 1106349 1091002 1076812 1057646 1045538 1028615 1011297 995286 980312 967462 949382 938324 922981 909529 896423 881872 868785 857983 842729 827596 815366 798936 789041 777980 765459 752728 740617 731255 719086 708024 698519 686596 674859 664096 655804 646511 635193 624423 615890 607191 597199 587015 576534 568770 559587 552161 541505 531817 525377 519299 511710 503001 496662 489158 482463 473502 467446 461047 452691 445988 439690 433666 427588 418115 411033 408559 400281 392926 388243 380154 374848 371023 363670 357561 353038 347161 343219 338337 333347 327850 323457 319880 315187 307841 303483 299228 293149 292375 290632 282028 280017 273668 269508 265746 259905 256515 253513 247720 244051 240233 236364 233743 229391 227712 223276 220006 218823 220979 209848 206209 203853 201668 197729 193997 191212 188986 186141 182374 178763 178155 178263 177474 173266 170993 166672 162444 158368 155448 161597 152983 150185 145918 144468 143726 141072 134500 132789 130074 128664 127126 124285 123176 120498 118689 117480 115288 114288 112347 111544 110183 109223 108167 106584 104995 103774 101176 101035 100324 99446 100687 98830 95619 94871 94010 99258 90390 94092 89370 90155 86862 85915 84450 81655 80770 80165 79419 76193 76228 77185 73503 72886 70401 68652 69092 67613 66469 65587 65034 63127 62249 61612 60638 66450 67021 65308 65044 64879 65173 65519 63685 65028 62205 61721 59484 50065 49229 49582 48848 48405 48215 46999 47398 46542 46747 44789 45103 44141 43797 43075 42562 42193 42415 41756 40565 40352 40251 38941 38398 38901 37938 37552 36699 36442 35715 35544 35181 34935 34412 33724 33383 33032 32703 32074 31609 31255 30921 30491 30523 30000 29441 29586 28861 28954 28486 28530 27974 27407 27090 26933 26641 26541 25752 25638 25348 24757 24927 24485 24150 23877 23632 23430 23156 23150 22566 22874 22344 22217 22011 21694 21213 21726 21112 21087 20869 20931 20366 20415 20184 20155 19897 19826 19658 19936 19507 19235 19152 19209 19157 19341 18721 18385 18198 18675 18387 18315 18453 17555 17467 17615 17209 17222 17162 16758 16874 16719 16529 16355 16229 16379 16494 16176 16520 16503 16403 15940 15895 15434 15334 15358 15554 15148 14849 14976 15366 14841 14828 14844 14628 14784 14514 14673 14356 14163 14224 14220 13911 13545 13700 13226 12948 13241 13310 13448 13396 13265 13837 13608 13595 13432 13285 12941 13338 13334 13105 12803 12744 12971 12476 11830 11751 11901 11795 11705 11754 11585 11596 11865 11507 11916 11731 11286 11235 11394 10497 10598 10312 10334 10521 11061 10909 10367 10330 10321 10340 10097 10165 10050 9685 10299 10082 9905 10138 9726 9390 9475 9162 9505 9357 9149 9194 8806 8771 8819 8755 8692 8927 8877 8878 8720 8587 8711 8472 8387 8607 8381 8402 8358 8335 8333 8199 8197 8055 8218 8322 8121 8231 7964 7678 7881 8196 8044 7644 7557 7627 7523 7714 7081 7187 7197 6858 7050 6856 6921 7120 6687 6775 6567 6430 6573 6670 6435 6638 6508 6593 6530 6486 6263 6427 6192 6190 6242 6073 6220 6179 6784 6171 6139 5997 5806 5769 5712 5756 5744 5694 5729 5719 5464 5592 5465 5551 5510 5322 5544 5415 5297 5167 5300 5378 5206 5244 5340 5351 5532 5525 5597 5499 5503 5555 5531 5609 5381 5379 5499 5333 5428 5316 5156 5405 5529 5635 5435 5452 5496 5181 5033 5328 5525 5436 5273 5333 5220 5493 5457 5243 5174 5084 5539 5408 5424 5445 5102 5502 4869 4775 4952 4927 5061 5032 4816 4857 5270 5597 4843 4702 4711 4773 4518 4582 4640 4531 4454 4255 4201 4353 4197 4332 4208 4139 4054 3858 4097 4137 3847 3922 3923 3806 3755 3773 3991 3889 3827 3790 3996 3815 3782 3526 3415 3507 3539 3493 3530 3639 3514 3412 3504 3545 3393 3468 3523 3462 3398 3628 3641 3526 3569 3504 3437 3335 3377 3278 3396 3113 3038 2953 3082 3034 3062 2968 3043 3247 3073 3033 2995 2985 2984 3171 3112 2961 3133 3033 2998 2844 2963 2926 2943 2977 2939 2986 2899 2872 2871 2696 2833 3473 2998 3073 3194 3077 3136 3206 3175 3346 3044 3173 3034 2972 2946 2984 2935 3184 3180 2615 2749 2996 2782 2437 2357 2437 2638 2461 2608 2567 2554 2581 2445 2438 2528 2725 2531 2426 2451 2525 2559 2496 2713 2561 2882 2840 2786 2884 2635 2746 2692 2529 2384 2405 2467 2445 2017 2139 2066 1979 2045 2040 2252 1964 2095 2068 1979 2055 1938 1908 1899 1983 2180 1956 2021 2002 2020 2045 1960 2020 1874 1900 1954 1832 1968 1951 1812 1822 1728 1723 1723 1781 1780 1730 1652 1741 1642 1520 1626 1596 1634 1423 1443 1419 1468 1541 1473 1526 1617 1646 1657 1462 1571 1508 1527 1485 1453 1389 1396 1361 1478 1451 1484 1464 1450 1452 1538 1404 1552 1574 1542 1458 1521 1580 1431 1471 1398 1417 1345 1295 1247 1255 1182 1229 1235 1203 1264 1267 1184 1226 1214 1176 1101 1261 1219 1174 1241 1129 1203 1162 1081 1102 1245 1189 1199 1291 1325 1275 1270 1186 1130 1054 1098 1147 1194 1148 1109 1175 1153 1152 1157 1099 1113 1075 1094 1202 1133 1164 1225 1158 1096 1164 1169 1092 1373 1274 1372 1382 1339 1220 1304 1279 1144 1171 1178 1154 1267 1154 1265 1126 1091 1101 1229 1259 1277 1304 969 977 959 945 1000 964 985 983 1000 973 860 946 895 892 869 933 985 904 933 947 925 903 910 893 849 822 877 876 845 836 840 856 892 823 845 822 791 828 819 747 835 887 863 908 842 850 841 875 867 815 825 826 851 810 820 799 792 785 767 757 846 762 764 758 840 802 845 806 789 806 856 802 808 792 781 744 733 846 789 785 793 770 817 812 742 779 805 793 771 706 711 684 735 682 730 746 733 707 760 747 674 680 819 854 849 745 805 896 880 902 811 790 837 811 863 924 888 783 799 879 815 717 772 777 825 834 863 785 1003 774 815 931 851 872 819 864 1170 1153 1197 1142 895 854 883 841 800 790 749 787 805 813 750 715 817 663 612 572 556 582 628 575 544 589 618 527 518 563 530 616 571 515 545 560 547 546 491 521 589 532 561 527 577 561 561 587 411 443 418 400 394 391 417 410 388 388 425 433 391 427 406 394 420 405 390 533 423 376 429 369 367 390 377 401 416 390 406 387 363 404 371 365 406 415 382 382 358 365 345 386 370 377 374 394 361 368 357 345 376 353 404 565 584 517 624 576 499 602 587 545 587 603 527 624 535 539 654 477 513 554 595 565 553 544 557 486 351 389 359 348 361 366 361 358 368 382 361 318 335 323 370 343 320 339 322 350 302 343 344 338 336 351 326 367 317 306 349 318 298 279 272 317 273 261 294 270 292 258 262 279 260 280 278 282 233 254 234 267 224 251 236 233 240 225 198 246 232 227 215 240 242 217 200 178 210 216 192 206 196 200 175 214 183 220 210 196 199 210 240 202 213 186 227 217 225 199 229 212 183 208 217 204 249 199 226 202 253 239 220 193 225 218 202 236 196 216 215 208 221 211 206 270 237 246 217 253 205 250 202 213 229 224 210 189 182 217 208 191 197 177 198 173 195 184 197 193 201 205 180 188 175 168 174 196 200 193 180 166 180 176 164 162 176 187 186 151 164 173 196 166 164 174 158 181 177 169 186 179 175 178 175 161 206 168 141 196 171 172 187 175 166 174 157 167 183 204 173 165 164 159 150 173 174 183 158 151 153 170 155 143 147 153 174 200 164 154 187 166 153 141 157 148 134 135 141 121 139 165 148 149 154 146 134 155 172 131 143 140 180 141 168 167 167 169 172 169 156 191 154 152 164 141 165 156 165 166 177 151 159 116 142 159 144 161 150 146 165 168 182 158 146 176 128 152 130 168 121 125 167 171 166 161 156 178 166 187 173 171 165 164 136 228 180 193 181 163 206 193 187 202 177 171 171 185 165 168 198 203 213 166 145 156 144 139 156 192 153 190 197 178 170 151 172 152 131 147 135 163 139 139 139 138 132 141 129 155 151 136 149 147 135 132 170 153 154 139 135 135 133 140 141 140 184 129 134 135 154 149 149 152 136 122 147 133 145 133 152 122 134 156 129 140 166 136 134 139 140 143 113 124 128 146 122 144 121 129 118 125 131 119 134 134 130 127 133 132 136 137 135 114 108 115 136 127 97 120 157 120 111 97 132 126 162 133 127 128 134 139 136 120 138 102 112 114 91 106 111 116 115 83 102 117 107 88 113 113 117 110 109 94 104 112 124 134 96 82 92 92 108 106 106 102 95 105 91 72 111 94 92 96 84 113 104 99 93 87 104 91 86 85 109 114 99 98 89 91 69 87 104 103 82 71 102 96 79 109 87 92 96 88 105 104 113 108 108 106 87 100 97 98 112 137 104 99 108 86 99 120 107 86 99 100 111 106 104 92 106 102 100 89 98 108 97 94 104 100 103 86 100 79 93 89 114 92 94 96 102 107 112 101 94 100 76 98 68 98 87 105 112 100 100 99 94 100 132 108 76 99 83 100 105 102 88 92 90 82 108 99 95 86 105 99 101 94 105 110 105 105 98 125 113 108 108 101 103 118 94 103 98 89 102 121 108 94 126 106 105 82 98 75 112 103 125 95 114 100 104 107 106 123 116 115 106 112 93 100 98 84 107 115 116 106 102 83 80 80 75 86 95 87 92 93 69 90 76 65 96 82 81 87 84 81 105 78 81 71 68 79 85 90 82 87 95 73 94 81 75 102 81 82 94 102 113 98 105 93 95 101 75 89 82 86 79 90 63 82 69 95 80 79 99 89 95 104 112 82 76 84 98 96 99 83 
];
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
 7574322 2375172 5199150
 1956936 659612 1297324
 2313718 801124 1512594
 5822307 2103914 3718393
 5083708 1820948 3262760
 7062777 2546043 4516734
 11345996 4117734 7228262
 13325747 4747109 8578638
 6827686 2459879 4367807
 13039461 4891839 8147622
 9284252 3364635 5919617
 2297306 865171 1432135
 14091778 5301833 8789945
 1964915 743738 1221177
 2345810 899932 1445878
 17245895 6623525 10622370
 2417129 931298 1485831
 7806712 2898778 4907934
 18735201 7595769 11139432
 7432531 2790142 4642389
 1942919 783540 1159379
 116724742 47590522 69134220
 1928586 796774 1131812
 3270649 1273587 1997062
 1793865 746295 1047570
 3493313 1384661 2108652
 3421996 1381870 2040126
 1880446 804940 1075506
 3371651 1368033 2003618
 1595879 700301 895578
 137547858 63364083 74183775
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 547 5 2
118 67 1 3
165 122 1 1
103 143 1 0
59 154 3 1
91 206 130 16
2057 326 350 71
16330 419 597 202
115581 557 1040 503
624895 864 1742 1043
2510083 1245 2393 1785
4202345 2435 3606 2832
5889010 4837 5284 4471
7986074 10847 7740 7173
9638010 21727 10878 10187
11037298 43448 15231 15042
10875606 75616 20504 20406
8944860 115941 26634 26350
5685336 158588 33389 32848
2325926 198264 40597 40114
528175 231485 46911 47337
117661 256302 54075 54067
87072 261111 61929 60934
84971 237689 68367 68125
84748 199615 75148 74347
87953 163140 80797 80501
91190 137058 86664 87417
96395 122928 94039 93457
104955 119335 102199 101776
112048 121053 111581 111514
121696 126555 121180 121027
133322 134791 131531 131835
149011 147456 143270 143398
163030 160604 157712 157494
178288 176897 173941 174850
195563 194583 194468 193476
218469 216800 214431 215781
242962 242430 240959 242610
271245 269837 269974 270842
302371 301546 301029 301220
338539 340314 337811 337971
380074 380330 381064 380749
426672 426873 427253 425461
478283 477891 479048 479864
538310 538651 540071 538895
602629 603800 603725 603326
672840 675647 675838 674832
748924 749347 751218 750614
828182 829920 829308 829535
906877 909304 908182 907377
981607 980147 981743 979782
1043833 1045453 1044345 1045559
1098103 1100711 1098517 1097676
1149333 1148823 1149423 1147301
1188771 1190389 1190564 1190600
1229095 1225741 1226667 1226533
1267888 1266831 1265218 1264659
1297146 1299297 1299885 1295512
1325519 1324676 1327267 1325434
1341530 1340022 1340816 1340500
1341650 1341658 1339577 1340092
1299656 1298342 1299358 1297724
1190636 1191757 1189964 1191417
982323 983067 983382 983715
684971 684839 685344 685478
348462 347217 348712 348842
103907 104913 104372 104347
12755 12529 12611 12466
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
