A = [
1224194 1290656 29960940 868630 835499 803949 823024 816676 825252 805276 819655 893870 965197 1013950 1114282 1186600 1226347 1258429 1245856 1176029 966617 906698 825759 680187 714140 1032268 1038826 1100606 1429170 1428446 1459806 1480880 1496112 1532368 1536702 1541319 1529987 1524569 1520447 1513070 1520252 1521353 1525437 1533427 1528527 1526538 1523032 1511257 1500921 1495708 1496157 1494137 1496938 1498365 1494531 1492594 1485757 1478654 1474643 1461654 1461640 1460402 1458651 1456944 1462104 1454036 1450615 1446865 1437179 1429982 1429911 1428371 1423815 1427416 1425073 1421068 1422528 1416815 1410141 1404107 1402854 1398899 1396091 1394930 1395251 1393147 1390086 1382849 1383159 1373268 1371525 1366580 1365810 1362083 1361707 1362080 1361326 1358670 1351452 1348986 1345212 1339555 1335583 1334999 1331629 1333417 1331797 1325826 1325914 1322612 1316975 1312585 1308419 1306522 1301658 1304910 1301369 1299723 1299837 1292884 1286750 1285610 1279831 1274659 1276064 1274787 1269104 1270171 1265557 1260317 1260791 1254810 1247993 1245735 1243189 1242970 1240923 1240428 1235565 1230855 1227981 1222564 1219310 1216948 1212389 1213121 1207523 1205325 1201010 1199856 1195106 1194412 1187364 1182794 1180899 1175087 1175288 1175554 1168564 1166916 1169239 1162016 1157710 1153489 1150034 1144188 1144300 1140890 1138309 1135544 1132530 1128803 1125173 1122079 1117193 1112821 1109116 1106645 1103642 1100084 1099277 1092191 1090120 1085563 1082729 1076700 1075838 1073174 1070578 1068889 1063413 1061087 1058677 1053825 1051669 1047355 1043935 1041781 1036314 1035255 1029524 1028188 1028853 1023514 1016200 1013202 1011046 1008410 1004953 1000352 998442 995457 990754 988693 986734 980805 976873 972878 971033 968370 965724 964586 957781 955531 952440 945826 945835 942909 938652 937354 929829 927315 923885 922666 919167 915998 911252 909994 905872 902045 900720 898280 891757 889908 884869 881488 879184 875215 872503 867148 864685 862917 857534 854957 850058 849352 844286 843910 839307 836609 833357 825080 823632 819722 816229 815955 811770 805857 804540 801003 798418 795074 791441 788129 783769 780474 779648 773679 770657 766549 763070 756085 753939 749528 746519 745494 740825 738552 731605 729567 728343 723027 719626 715092 712313 709069 703556 700964 698276 692181 691156 684821 683100 676926 673526 669020 666904 663549 659842 656514 653050 649338 643482 639896 634747 632670 626862 623142 620258 617397 613131 607201 606126 600094 596640 591716 588526 583969 581466 576256 573923 567582 564782 561356 555661 554575 550290 547463 542637 537625 534282 529790 527567 521660 517930 512940 509899 505667 501850 497985 494901 490714 486487 482536 478909 474157 472014 467735 461512 461464 455725 453652 450447 444416 441375 436854 433136 428841 425059 420736 417156 415099 412517 407822 405042 400600 398012 393996 389648 386953 383372 379937 376551 373529 367527 365266 363502 357982 354436 350840 346878 345864 340645 338194 336266 332046 328152 324546 319785 317561 314705 311418 309041 304821 301739 299896 295809 292308 288515 287205 283228 279890 276735 273040 270738 267273 264133 261488 258069 255092 251643 249403 247195 243100 242041 236843 234814 231986 230712 228238 224657 222087 219596 217855 214747 212055 209073 206951 203608 201479 199345 196082 193618 191902 188391 187512 184887 183025 180762 178692 175979 173692 172267 170260 167364 165844 163560 160384 158685 157049 154969 152555 151087 149142 147441 145798 142681 141939 139084 136260 134358 133778 131302 129860 127570 125073 125032 122731 120985 119410 117475 115781 114561 113082 111243 109714 108298 106644 105863 104309 102498 101140 99216 98569 96419 96255 94316 93067 91350 90172 89716 88053 85993 84440 84552 82934 81196 80460 79265 78065 77054 76102 74911 73540 73426 71659 71310 70019 68319 67780 67089 66051 64778 63397 62757 62332 61361 59955 59335 58558 57804 56567 56124 55291 54244 53788 53259 52811 51865 50470 49652 49476 48619 48176 46998 46392 46382 44904 44576 43803 43233 42518 42082 41241 40630 40091 39386 38787 38564 37721 37338 36919 36239 35740 35471 35082 33652 33934 33429 33056 32595 31925 31465 31204 30737 29966 29528 29428 28587 28517 28561 27646 27351 27035 27102 26048 25922 25706 25338 25023 24192 24310 23772 23752 23154 23032 22815 22198 22101 21575 21786 21117 21020 20538 20546 19980 19798 19363 19274 18900 18739 18352 18198 17840 17867 17654 17289 17154 17025 16712 16487 16195 15973 16016 15615 15411 15042 15066 14821 14834 14548 14440 14278 14075 14074 13708 13669 13487 13057 13342 13101 12895 12688 12351 12337 12242 12106 12065 11799 11706 11804 11503 11398 11422 11183 10852 10942 10694 10416 10841 10522 10204 10355 10162 9994 9815 9968 9668 9395 9303 9201 9255 9152 9020 8841 8842 8703 8824 8579 8521 8358 8345 8547 8178 7902 8033 8037 7860 7748 7739 7689 7741 7459 7620 7522 7492 7541 7424 7270 7181 6988 7177 6972 6845 6947 6724 6814 6874 6638 6505 6453 6340 6397 6344 6281 6181 6188 5931 6151 6098 5863 5918 5840 5822 5906 5834 5746 5655 5541 5647 5595 5697 5685 5520 5322 5298 5357 5289 5492 5367 5275 5245 5262 5062 4873 4944 4953 4942 4815 4937 4954 4859 4803 4774 4912 4753 4700 4833 4680 4671 4705 4604 4333 4398 4451 4332 4197 4319 4287 4194 4262 4090 4095 3978 4182 4063 4152 4110 4149 4130 4157 4016 4018 4020 4086 4046 3891 3862 3868 3910 4043 3718 3741 3849 3685 3801 3735 3877 3822 3692 3843 3642 3693 3672 3451 3492 3529 3433 3473 3570 3463 3498 3527 3381 3362 3514 3420 3549 3343 3468 3262 3482 3291 3258 3321 3183 3250 3128 3232 3246 3233 3129 3311 3265 3150 3147 3188 3145 3067 3047 3028 2997 2994 2949 3015 2935 3026 2976 2993 2880 3003 2895 2959 2895 2979 2935 3032 2823 2739 2886 2814 2840 2849 2955 2758 2947 2784 2891 2792 2762 2859 2662 2723 2733 2627 2804 2753 2686 2757 2638 2662 2604 2637 2584 2677 2642 2583 2581 2643 2693 2640 2615 2561 2613 2573 2524 2502 2518 2546 2473 2602 2465 2520 2495 2483 2500 2547 2564 2474 2558 2418 2390 2312 2456 2390 2342 2334 2372 2343 2360 2360 2380 2266 2339 2292 2207 2315 2240 2153 2170 2218 2115 2137 2168 2162 2213 2186 2093 2081 2149 2116 2109 2093 2094 2160 2068 2240 2110 2138 2130 2095 2021 2112 2037 2044 2063 2072 1968 1984 1971 1872 1866 2039 1910 1947 1922 1914 1947 1954 1891 1868 1919 1973 1933 1850 1718 1814 1838 1861 1825 1827 1891 1774 1939 1814 1903 1798 1760 1813 1758 1726 1811 1764 1770 1757 1716 1634 1694 1647 1712 1724 1715 1716 1651 1593 1908 1690 1664 1737 1669 1686 1608 1680 1666 1634 1619 1611 1675 1567 1651 1634 1554 1604 1595 1620 1555 1462 1566 1585 1534 1540 1468 1578 1446 1432 1515 1498 1651 1414 1450 1426 1535 1449 1451 1405 1494 1335 1300 1336 1342 1361 1329 1370 1332 1409 1355 1339 1394 1325 1314 1382 1379 1329 1382 1336 1313 1329 1304 1343 1301 1270 1308 1287 1327 1251 1335 1266 1314 1253 1306 1360 1361 1296 1328 1291 1349 1249 1301 1247 1238 1315 1321 1286 1201 1230 1208 1176 1299 1204 1196 1178 1194 1202 1215 1282 1197 1180 1178 1190 1151 1139 1243 1166 1142 1240 1192 1147 1099 1199 1125 1192 1109 1196 1177 1204 1153 1149 1180 1176 1143 1112 1116 1169 1113 1114 1145 1107 1100 1033 1054 1033 1103 1126 1132 1049 1077 1097 1013 1018 1084 992 1006 1019 1009 985 1006 1053 962 1005 1010 970 1015 977 1039 1087 1020 1046 950 1008 1032 985 1082 1093 1063 1023 1096 1013 998 950 1045 1018 917 978 984 952 1039 966 1033 1011 923 952 1002 1000 937 991 978 936 930 969 933 911 913 926 912 939 881 891 822 833 841 878 875 875 850 897 859 871 869 899 893 892 955 926 841 838 933 881 927 901 855 868 866 837 878 846 857 878 772 831 835 889 867 823 814 808 861 746 808 822 825 808 810 764 736 750 814 763 770 754 824 778 722 740 733 795 765 706 777 699 757 796 789 770 780 762 758 785 703 737 698 725 719 693 659 649 693 746 724 765 703 692 645 642 667 723 716 657 691 731 702 694 672 661 654 615 639 583 639 679 621 616 581 584 589 595 616 595 657 569 587 598 584 541 567 572 601 587 585 518 519 586 525 661 603 552 559 549 490 572 487 493 504 561 488 488 519 513 522 501 533 592 541 524 486 550 571 515 479 546 526 521 537 540 522 502 493 493 457 520 585 474 502 514 642 519 493 487 499 493 514 500 505 476 484 515 545 527 510 581 490 523 518 481 498 516 495 554 492 540 534 515 539 482 491 516 529 551 534 526 549 553 533 503 494 472 500 521 496 509 475 497 456 474 445 469 462 468 428 456 431 439 455 465 459 469 427 466 403 467 470 427 435 419 468 436 405 459 381 405 442 480 458 402 421 426 419 415 429 420 411 390 435 445 406 408 391 453 438 425 398 462 395 405 416 422 374 382 392 374 414 396 394 387 385 426 358 368 389 394 387 432 381 371 388 370 330 386 335 312 353 398 346 364 380 370 361 332 376 371 359 383 345 371 347 381 356 350 498 382 401 351 375 324 342 369 360 373 349 326 349 355 391 426 362 333 362 318 321 334 311 347 373 351 355 324 314 336 339 315 304 338 362 351 339 358 342 348 339 347 347 329 348 315 324 305 341 332 308 318 329 312 325 320 365 332 331 353 367 268 277 298 324 295 332 293 258 272 254 274 251 243 286 283 282 263 255 256 273 278 277 295 258 246 273 259 265 288 252 274 247 298 310 304 275 290 274 302 284 289 291 245 246 260 274 302 255 282 307 271 270 255 279 267 279 273 253 254 245 257 255 256 248 259 253 227 257 269 261 258 265 279 261 294 246 270 253 276 255 280 244 274 272 244 251 272 245 207 248 254 247 267 276 255 257 240 235 251 263 234 268 227 257 229 235 261 261 244 228 216 228 240 264 267 235 207 253 227 258 198 228 218 243 236 243 243 232 265 245 261 224 227 229 217 229 217 198 212 240 242 227 219 214 239 240 216 208 234 209 224 212 217 205 242 227 207 205 197 262 218 197 195 261 245 227 240 228 210 226 234 264 239 219 241 218 216 221 201 236 234 235 231 220 215 236 186 188 232 249 220 220 212 237 229 231 197 218 228 217 240 215 203 220 202 216 216 187 188 203 198 167 206 180 155 198 187 209 197 187 208 188 198 159 168 181 180 209 168 179 199 182 176 172 134 147 175 155 159 171 167 191 182 219 182 175 172 172 172 168 184 196 196 197 163 179 174 177 193 162 159 172 187 179 155 171 165 164 147 131 158 167 189 165 164 144 168 153 157 166 153 143 137 144 158 167 147 182 168 152 148 145 166 158 164 169 143 164 141 192 170 162 156 165 131 140 164 138 141 157 157 147 165 150 136 158 139 122 132 166 126 156 154 158 144 154 129 127 143 106 115 133 139 144 128 113 141 149 134 105 138 138 139 122 109 116 102 108 124 139 126 122 138 115 126 107 114 120 97 133 104 107 105 135 135 123 119 124 125 127 126 149 115 119 124 95 121 120 121 117 113 98 115 133 121 125 134 135 113 138 133 125 136 121 150 161 122 137 111 122 146 129 125 129 123 143 121 133 129 128 142 122 124 128 131 119 106 113 122 96 129 131 
];
B = [
0 0 0
 233284 125898 107386
 208141 100896 107245
 243411 124559 118852
 282446 135591 146855
 242332 110804 131528
 204167 111748 92419
 235298 125871 109427
 305824 178227 127597
 209157 123863 85294
 265038 153483 111555
 294171 179567 114604
 276980 168413 108567
 464648 296532 168116
 148262 84250 64012
 886152 604254 281898
 161979 81873 80106
 162347 83588 78759
 219148 142846 76302
 160602 95033 65569
 179409 115278 64131
 145703 99068 46635
 304887 204575 100312
 155017 105311 49706
 194040 133433 60607
 335866 235734 100132
 98637 79896 18741
 612701 447303 165398
 760172 624051 136121
 106076 87643 18433
 125196 105119 20077
 252413 219838 32575
 288848 209997 78851
 272184 218515 53669
 338046 302098 35948
 914599 636911 277688
 125457 104735 20722
 377589 336103 41486
 80535 71710 8825
 436433 336449 99984
 78901 70316 8585
 368185 333554 34631
 362172 278941 83231
 73663 65894 7769
 1745240 1585073 160167
 138249 123991 14258
 349548 271041 78507
 116304 103769 12535
 838995 722923 116072
 261639 232394 29245
 392613 312725 79888
 737860 670731 67129
 121746 106783 14963
 682619 540587 142032
 686167 586676 99491
 651868 583598 68270
 164933 145513 19420
 415761 343069 72692
 129490 116980 12510
 1058763 961871 96892
 214207282 194969180 19238102
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
232 1319 10 16
76 228 5 15
87 272 15 29
139 417 59 198
142 371 128 458
159 449 667 915
1094 686 1714 2532
1505 747 2412 4319
2104 963 3633 7590
2968 1277 5755 13389
3786 1696 8556 20779
5510 2290 14102 34389
8593 3324 22767 54236
17647 4884 39211 84774
52490 7318 64186 124783
228988 11893 105720 180693
990987 18395 157507 235693
3024873 28628 197280 265801
5877146 43605 194156 240645
6365687 63949 156343 176778
3244453 90534 145639 149687
770144 125447 173306 174598
265946 172021 215758 216246
280559 225531 265695 264216
337565 288225 320019 320375
405736 358513 385563 385520
480969 438573 460040 462761
570415 531357 548993 549627
668896 630019 645607 647531
779102 738381 755771 757794
902087 855360 871845 874813
1030986 975773 998218 997313
1167127 1100959 1120789 1121147
1282077 1225088 1245328 1249545
1388229 1349221 1366929 1370452
1503521 1465499 1477287 1484573
1595341 1563961 1579673 1582948
1671652 1651681 1660606 1660525
1733908 1717303 1722674 1729338
1776928 1765626 1769625 1772664
1799875 1793044 1790330 1797528
1802540 1799664 1799763 1804211
1785999 1786167 1781811 1788391
1752352 1755721 1752787 1754231
1707807 1708519 1703175 1708930
1635703 1637571 1633809 1641747
1530381 1532991 1528157 1533896
1406518 1409132 1403998 1407696
1280064 1280731 1278436 1282393
1153043 1154982 1152177 1155739
1044239 1044799 1045472 1042377
929941 930769 928657 933485
859286 860047 856588 860260
813917 815005 812872 816992
768461 768641 767000 769152
729158 730207 726909 731623
711642 711235 709208 713708
690256 691772 689147 692902
699262 698877 697848 700292
705106 706899 704081 707822
713340 716276 712051 713873
709683 708899 707053 709930
718666 715687 716169 717677
695932 692381 693946 695590
642320 640270 639542 644280
555714 556757 554561 556032
452399 452200 451781 453604
361460 363809 361953 363764
290049 291656 290962 290814
196962 197664 196389 197226
89871 91478 90796 90573
18184 17977 17651 17947
2 5 6 5
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
