A = [
249569 742320 878383 417404 896073 582018 559737 556298 590338 545678 544042 571174 548921 534485 546248 543060 534451 547623 543550 527729 532875 519735 510749 490495 479580 490656 499525 482851 481933 495260 478377 465747 466858 449143 442240 456964 450793 440928 448598 445070 432909 433660 428967 408598 409264 407806 407484 406137 404861 398393 399683 391566 377446 373916 364250 357518 367212 356348 347069 351591 346298 332849 334610 320336 310958 312707 307598 301534 299443 293774 285447 284780 275074 267099 268921 261015 254010 256146 253157 243896 240112 234679 224327 224326 218490 213392 211933 210731 203816 200167 195004 190774 188759 187646 177933 177402 176148 169562 169307 165118 160777 160004 157167 151248 149906 145797 141773 142094 145691 135283 135186 131703 127237 126557 125975 122966 125974 117509 113715 114172 111091 109412 108733 106181 101789 103470 99755 97749 96794 94191 91905 92417 89403 87114 89491 84987 83395 83500 81630 87729 80219 76599 73746 74162 71752 71370 69306 68828 66159 67060 63553 61942 62167 60851 60008 60130 57637 55915 55088 54439 52532 51883 51043 48778 48412 48061 47161 46983 46467 45354 44659 43623 42562 42050 41084 40183 40197 38756 38175 37647 37045 36583 36325 35373 35096 35207 33500 33140 32349 31598 31381 31162 30909 29475 29427 28472 28448 28726 27733 27120 27837 27291 26442 26727 25905 24980 25184 24984 24534 24750 23933 23899 23378 23463 22668 22644 22218 22574 21579 21662 21041 21249 20851 20310 20271 20107 19952 19429 19521 18481 19592 18945 18669 18955 18423 18169 18339 17389 17833 17357 17687 17238 16562 17880 16683 17026 16208 17351 17273 16767 16333 16513 15806 15932 15291 15844 15759 15667 14931 15211 15372 14471 14654 16143 14496 14509 14174 13810 14411 15157 14254 14440 13882 13669 13295 13315 13140 12871 12984 12641 13828 12777 12370 12715 12868 12555 11966 12260 12274 13254 12765 12430 11367 11720 11240 11511 11529 11185 11403 11178 11056 10814 12723 10945 11711 10609 10853 10880 10844 10613 10901 11411 10236 9932 9910 10152 9840 9953 9879 9908 9905 9673 9839 9667 9940 9462 9443 9612 9331 9642 9001 9240 9134 9218 9356 9159 9308 8721 9037 9042 9105 9072 8576 8646 8793 8614 8659 9079 8184 8993 8402 8299 8334 8180 8600 8468 8080 8229 7658 8061 8103 8127 7975 7755 7809 7650 7708 8046 7560 7254 7729 7452 7619 7737 7384 7187 7442 7114 7245 7184 7228 6984 7060 6807 6834 6971 7046 6737 6878 7755 6788 6819 6679 6550 6809 6426 6685 6662 6532 6778 6377 6532 6526 6334 6417 6826 6014 6371 6112 6471 6010 6203 6085 6152 6128 5884 5774 5851 5594 5663 5762 5611 5769 5642 5816 5678 5556 5658 5540 5980 5492 5684 5571 5510 6072 5482 5978 5422 5486 5384 5121 5222 5283 5544 5104 5069 5294 5307 4932 4914 4827 4996 4736 4815 5018 4748 4755 4899 4721 4722 4691 4642 4773 4554 4548 4707 4481 4479 4649 4399 4549 4543 4224 5141 4294 4611 4569 4432 4310 4441 4214 4291 4150 4028 4135 4287 4194 4062 4347 4201 3986 4138 4127 4292 4151 3933 4008 3981 3944 4489 3995 4079 3880 3829 4166 3685 3862 3607 3893 3592 3792 3640 3753 3765 3685 3923 3683 3700 3602 3528 3502 3547 3739 3631 3470 3437 3494 3523 3542 3394 3405 3262 3443 3496 3484 3203 3454 3653 3493 3454 3205 3284 3313 3423 3431 3130 3191 3509 3388 3127 3164 3149 3074 3215 3117 3061 3063 2993 3138 3163 2976 3051 3049 3332 2984 3043 2954 2978 2893 2937 2878 2809 2765 2871 2776 2735 2601 2738 2677 2776 2622 2695 2671 2828 2689 2838 2541 2621 2592 2590 2619 2572 2527 2500 2705 2491 2567 2665 2524 2781 2446 2318 2345 2351 2207 2268 2463 2401 2368 2353 2398 2339 2355 2312 2336 2351 2251 2305 2251 2178 2152 2262 2182 2243 2143 2224 2243 2243 2189 2228 2211 2209 2297 2109 2125 2107 2110 2016 2023 2098 2000 2072 2143 1957 1946 1917 1850 2177 1893 1763 1979 1924 1773 1862 1737 1828 1890 1851 1863 1934 1873 1919 1842 1904 1782 1862 1789 2052 1809 1832 1855 1766 1754 1793 1750 1927 1848 1580 1759 1788 1864 1642 1816 1806 1827 1591 1664 1656 1762 1652 1607 1663 1677 1633 1706 1756 1615 1901 1712 1656 1642 1656 1762 1647 1639 1591 1818 1535 1569 1683 1608 1753 1559 1478 1520 1697 1609 1562 1446 1482 1378 1554 1408 1510 1522 1514 1470 1499 1463 1451 1442 1408 1357 1457 1402 1522 1376 1398 1351 1347 1291 1287 1304 1190 1255 1228 1277 1289 1349 1257 1255 1253 1312 1227 1364 1211 1247 1205 1278 1171 1162 1383 1094 1114 1088 1123 1138 1158 1256 1227 1151 1196 1108 1135 1186 1141 1121 1007 1198 1101 1078 1096 1020 1043 1042 1001 1022 1072 1070 1083 1008 1107 1095 971 1154 993 961 1026 968 945 949 974 1006 996 1001 979 986 1016 1000 970 986 923 950 965 879 898 989 911 910 1083 1040 952 1035 955 841 914 917 868 927 916 944 901 925 908 884 1052 919 852 857 867 825 861 974 801 764 860 805 879 900 866 809 888 856 810 746 849 897 834 754 877 939 865 750 892 889 781 906 865 823 939 754 838 855 819 844 814 781 728 749 789 696 751 831 701 769 779 661 868 769 688 860 754 769 618 678 687 664 785 695 810 954 642 936 629 793 658 762 785 668 887 693 790 631 675 716 653 709 646 664 601 641 849 634 595 738 692 622 1058 683 817 761 657 773 758 654 617 633 625 558 568 622 615 594 638 679 586 665 634 593 555 623 560 533 504 539 500 542 576 529 591 2281 790 598 720 509 836 542 633 655 515 554 832 615 511 474 460 443 474 460 502 548 539 480 547 486 505 508 445 479 452 693 410 456 423 417 446 439 463 494 463 482 439 502 546 430 491 503 542 770 714 425 543 476 451 490 465 976 475 702 617 467 596 400 495 454 477 397 512 372 778 390 436 629 428 400 448 424 339 355 350 398 387 392 486 327 369 373 364 355 347 368 350 312 311 346 348 337 350 344 366 316 358 385 371 325 313 332 366 350 408 358 322 411 414 323 319 308 324 313 310 407 358 319 340 298 377 325 303 336 311 340 295 298 323 285 368 358 319 323 303 314 262 276 268 256 262 307 391 295 295 336 282 279 278 312 296 238 249 262 263 265 255 279 298 267 274 250 229 247 285 277 273 282 266 253 274 290 327 243 289 284 258 232 276 329 237 284 254 257 290 299 272 262 279 231 242 330 242 226 212 221 209 245 224 228 265 218 253 212 253 286 268 233 229 239 254 205 225 217 235 230 178 200 214 260 267 278 239 260 225 200 312 181 230 228 219 195 204 212 228 206 245 189 186 224 193 255 184 190 171 285 143 174 199 201 188 194 223 194 221 213 215 252 220 318 199 174 183 144 213 176 162 189 173 170 191 181 178 167 154 164 185 176 163 173 145 180 223 180 177 177 158 158 181 151 151 205 134 155 158 278 133 187 149 179 138 181 151 159 205 162 175 167 122 136 153 136 165 145 136 156 126 153 156 164 151 139 130 140 139 150 120 129 165 138 160 150 115 135 146 121 166 131 183 196 135 141 113 140 132 141 125 130 112 112 139 144 127 131 136 138 114 124 134 126 150 94 114 134 103 132 115 140 119 130 129 106 152 136 136 127 115 103 152 121 112 109 119 95 112 117 105 102 90 91 130 99 125 120 122 108 74 91 99 103 86 99 88 72 96 114 90 117 100 92 85 91 106 103 96 84 107 86 96 88 95 97 98 104 89 98 90 105 95 100 102 91 93 99 106 92 86 95 84 101 88 98 109 97 76 90 84 102 83 82 60 107 74 95 98 77 69 88 71 73 108 97 68 87 93 82 75 82 111 85 93 102 84 98 89 89 95 81 76 94 115 94 89 94 113 79 98 76 80 78 85 66 106 83 78 79 148 72 73 63 48 77 63 82 91 135 72 114 75 93 77 84 85 54 80 65 59 70 55 69 61 82 127 92 85 124 81 79 119 61 57 65 43 58 72 43 82 218 90 51 54 49 66 60 63 48 57 90 62 74 64 67 43 50 59 52 39 72 92 63 64 51 56 49 52 56 38 58 87 74 106 82 63 55 70 36 96 48 75 64 82 48 62 49 52 82 51 61 87 62 52 48 65 69 83 56 64 80 57 54 58 47 43 52 68 53 47 45 42 56 69 57 54 51 47 66 67 69 56 63 39 70 45 65 66 47 46 53 71 38 56 49 42 38 44 40 33 47 70 40 49 38 44 59 48 52 62 57 58 45 45 38 51 43 41 37 71 53 41 55 39 45 44 35 52 40 43 44 49 42 41 41 41 46 59 54 54 44 44 46 59 63 45 46 117 77 51 111 44 109 49 34 46 41 40 40 38 38 60 54 39 50 49 33 59 49 42 53 56 51 39 37 37 54 37 25 40 33 30 29 58 42 27 37 50 36 25 51 39 29 38 29 32 32 36 41 22 46 19 42 47 32 39 27 32 35 58 22 25 29 44 35 39 29 38 39 28 36 22 55 34 42 32 29 43 37 32 35 34 45 35 28 43 34 23 40 33 32 33 38 42 29 21 30 26 19 29 32 31 20 29 36 23 49 24 31 29 31 34 23 37 27 21 24 24 16 19 23 22 27 22 24 25 25 20 18 23 22 30 24 26 31 33 15 17 26 22 33 31 18 44 18 28 27 26 34 21 18 27 23 25 23 27 17 19 16 13 26 28 25 22 15 17 16 25 30 13 25 30 31 19 37 17 26 13 18 24 27 25 33 21 22 22 26 15 26 22 18 15 23 17 21 15 12 15 8 27 22 27 20 14 19 18 27 17 16 22 28 25 12 28 22 9 19 14 21 13 16 26 14 20 28 20 18 20 22 18 18 24 22 27 21 9 23 28 24 21 24 9 19 23 20 20 24 15 33 33 17 27 29 15 6 11 19 16 22 25 27 22 23 18 19 22 38 22 18 24 19 44 42 16 10 16 15 12 22 6 13 16 16 14 26 12 15 24 16 10 17 24 12 19 18 8 30 14 15 26 16 25 19 20 15 23 11 22 12 24 17 15 18 14 9 14 15 12 16 20 22 11 13 13 20 9 17 18 15 16 10 19 18 19 24 38 16 18 25 18 33 18 27 19 9 19 12 14 
];
B = [
0 0 0
 162767 88906 73861
 72971 37658 35313
 291777 168531 123246
 154987 86181 68806
 81444 48904 32540
 277909 169761 108148
 180919 108718 72201
 91786 55388 36398
 331524 215989 115535
 307174 197711 109463
 54567 30555 24012
 1056447 713641 342806
 116908 73145 43763
 35103 20499 14604
 183562 147287 36275
 55819 40942 14877
 16423 10244 6179
 192997 154820 38177
 16640 10168 6472
 15202 9840 5362
 3074 1800 1274
 251 198 53
 3142 2198 944
 273163 223464 49699
 16273 10669 5604
 20314 15103 5211
 272222 225054 47168
 13822 10537 3285
 30410 22840 7570
 445173 369030 76143
 27727 20803 6924
 48489 39390 9099
 273415 234799 38616
 281897 251675 30222
 506871 461027 45844
 769995 689440 80555
 744744 634726 110018
 480553 436667 43886
 924228 845768 78460
 412401 344214 68187
 17901 14263 3638
 698031 606638 91393
 9068 7122 1946
 17514 14268 3246
 869441 770419 99022
 17780 14637 3143
 353837 302652 51185
 969751 896268 73483
 362710 315189 47521
 4 4 0
 12633213 11996260 636953
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
167 184 20 0
117 44 3 1
278 95 1 0
315 137 4 0
352 112 7 6
830 156 4 8
7246 280 49 43
62938 325 161 147
353450 439 338 309
1142288 669 704 699
2496440 1111 1184 1055
2993436 1605 1886 1815
3160154 2034 2822 2711
3380674 2964 4088 4050
3212673 4229 5717 5577
1868860 6550 7042 7000
815556 9073 8861 8699
291428 15346 9590 9924
85304 20533 10644 10649
37608 15101 14786 14898
39134 16661 17913 18184
30868 18600 20401 19924
32795 21404 23053 23217
33207 25043 24961 25112
34939 24432 26651 27017
36131 27389 27418 27416
35263 27881 27234 26996
34376 27047 26207 26582
32242 26557 24059 24143
30163 27484 22010 21925
26357 21988 19687 19394
24751 22449 17359 17281
21691 19094 15314 16052
21204 18870 14445 14466
18800 17422 13482 13548
17926 16462 13203 12861
17985 16359 12644 12745
15755 15086 12476 12465
13668 13678 11484 11370
13300 13499 10806 10920
12214 11953 10406 10110
13763 13684 9962 9883
9934 9494 8896 9103
8776 8340 7987 7972
7261 7341 7224 7093
6309 6376 6499 6290
5609 5602 5651 5640
4945 5099 5112 4980
4560 4475 4145 4213
3489 3543 3653 3841
3024 2879 2952 3091
2190 2291 2202 2204
1506 1613 1584 1616
1061 1130 1110 1153
854 965 658 687
373 378 419 401
228 199 200 204
83 70 75 75
22 14 22 26
9 13 8 6
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
