A = [
186451 182267 472291 131526 125843 121515 117794 120433 127306 125862 140478 199325 275626 312732 400518 495041 528524 558087 573227 569324 562391 537335 512549 523107 529910 598524 615573 610972 660567 586085 580446 564504 473933 478419 473365 473758 457397 459705 454793 438702 448815 446137 443173 459112 457150 449297 450684 441023 428691 425906 419920 412132 429473 430111 420525 436028 434906 422126 431579 430959 418559 429847 429870 419983 432859 432707 421687 437846 429236 418655 429695 424880 415769 431835 425429 414972 424617 424001 411427 419942 419335 404423 415309 409829 397471 410598 404237 394430 406710 398786 383190 388470 385274 375098 384271 377639 368173 379599 370461 358387 367103 361708 348869 355802 348176 339615 345211 341404 330376 335976 332635 319502 322552 318605 308730 312152 307788 299416 302565 297692 286934 295689 284701 277890 280911 274455 266853 269195 265788 258151 261193 256558 245881 252204 244701 235664 238138 235667 227542 230631 225094 218122 219863 217002 208272 210848 209192 201495 205705 199678 193233 197153 193810 187701 187879 184349 177675 179606 176630 170712 173298 170815 165827 166148 164363 156061 157625 155850 149474 152946 150105 144111 145549 144110 137450 138836 136882 131367 133665 132212 126421 128273 125986 122420 123822 119014 117668 115536 114424 109865 112148 110172 104704 106717 104674 100673 101742 99064 95903 97633 95276 92019 92943 91847 87784 89011 87209 83281 84758 82829 80069 81190 79835 77303 76736 75625 72933 73388 71672 69129 71090 68989 66567 66901 65831 63660 63786 62463 60701 60161 59198 57320 58765 56360 54880 55368 54612 52315 51653 52478 50263 50424 49056 47766 48809 47282 46018 47139 44961 42584 43380 42936 40885 41315 41184 39433 39979 38683 37098 37000 37157 36225 36388 35192 35495 33612 33290 32795 32250 31444 30634 30804 29998 29306 29008 28686 27760 27891 27087 26206 26741 26354 25126 25810 25243 23827 24269 23073 22654 22982 22555 21558 21871 21634 19954 20230 20061 19718 19606 19342 19048 18142 18418 17503 17810 17359 16868 17076 16652 16209 16104 15339 15928 15207 15049 14347 14328 14397 13948 13835 13372 13196 13490 13192 12536 12588 12464 11718 12216 12421 11445 11414 11388 11153 10967 10931 10551 10639 10530 9902 9918 10140 9964 9522 9321 9143 8957 8691 8744 8730 8602 7915 8050 8300 7819 8152 7901 7681 7543 7642 7547 7480 7263 6833 6949 7062 7002 6589 6498 6349 6541 6402 6028 6076 5969 5956 6120 5792 5934 5591 5538 5522 5640 5870 5385 5652 5385 5513 5482 5448 5077 5075 4999 4909 4953 4769 4951 4701 4869 4839 4393 4747 4427 4767 4463 4424 4447 4060 4249 4178 3864 4201 4168 4401 4032 4073 4198 3897 3782 3743 3596 3799 3710 3717 3587 3556 3635 3613 3530 3588 3619 3447 3520 3292 3628 3463 3470 3396 3635 3355 3053 3182 3255 3230 3106 3152 3062 3086 3227 3164 3066 2889 2887 2931 3112 2641 3184 2699 3051 2996 2840 2987 2745 2874 2717 2940 2549 2690 2517 2726 2793 2585 2576 2588 2480 2582 2587 2649 2667 2614 2486 2300 2365 2579 2451 2495 2528 2518 2459 2645 2643 2536 2325 2556 2395 2323 2526 2460 2410 2245 2462 2427 2284 2233 2379 2304 2247 2337 2289 2331 2337 2216 2144 2170 2199 2198 2289 2267 2038 2213 2165 2206 2055 2115 2078 1968 2053 2018 2116 2063 1912 1996 1898 2095 2057 1886 1998 1709 1895 2066 1936 2070 1938 1735 1967 1912 2090 1868 2148 1940 1883 1727 1935 1917 1763 1786 1914 1812 1991 1739 1780 1788 1919 1929 1921 2021 2056 1868 2133 1772 1905 1742 1916 2004 2004 1973 1804 1798 1740 1966 1887 1810 1767 1592 1631 1778 1637 1810 1828 1708 1711 1791 1794 1754 1928 1865 1935 1867 1673 1740 1681 1678 1620 1482 1627 1631 1696 1673 1779 1658 1826 1649 1718 1730 1765 1410 1643 1582 1537 1699 1658 1492 1628 1471 1594 1593 1546 1518 1498 1745 1600 1427 1490 1462 1563 1384 1340 1301 1387 1428 1301 1269 1411 1339 1388 1403 1378 1367 1398 1332 1409 1463 1378 1312 1359 1395 1351 1306 1450 1279 1438 1301 1392 1420 1425 1405 1474 1294 1323 1443 1273 1215 1058 1254 1130 1300 1174 1222 1230 1314 1212 1221 1235 1305 1291 1267 1249 1257 1248 1049 1226 1283 1054 1275 1154 1211 1231 1070 1049 1150 1124 1059 1172 1121 1039 1061 1212 1177 941 1191 1143 997 1026 1069 1033 1081 1182 1072 1033 1079 1101 1073 1038 1221 1202 1111 1125 1094 1077 1202 1073 1029 1163 1177 1290 1134 1290 1166 1159 1172 1291 1180 1270 1316 1092 1446 1296 1159 1294 1003 1156 1223 1149 1217 1254 1263 1179 1061 1224 1150 1002 1127 1276 1061 1061 1106 1168 1200 1120 1128 1042 1088 1042 1006 961 1039 1224 878 1013 857 1149 1138 1235 926 1112 1027 1118 898 888 922 875 839 898 850 930 879 974 851 980 1028 1127 956 938 925 955 996 988 746 815 796 910 891 989 964 823 835 908 909 835 959 822 943 801 824 853 773 842 771 831 856 829 834 733 828 848 886 734 989 858 802 919 792 852 894 820 751 892 852 778 899 739 854 801 725 830 950 686 930 785 957 742 729 797 769 678 830 760 726 727 744 966 627 747 725 874 684 739 731 720 765 645 650 747 682 799 842 760 724 766 757 745 802 670 698 781 609 799 701 699 824 795 720 785 757 787 790 743 832 711 701 621 557 735 679 801 673 734 718 691 844 864 754 714 887 737 747 725 839 678 596 697 604 672 697 720 740 698 721 678 751 620 719 580 621 614 725 799 702 792 554 832 680 558 629 688 510 691 618 539 582 636 613 841 550 543 593 712 642 642 634 726 607 556 676 666 654 666 688 947 678 619 821 888 876 900 713 734 861 650 558 661 605 497 617 495 528 624 570 563 546 526 526 685 584 614 466 520 538 610 431 483 569 571 495 479 585 520 622 578 547 510 416 536 480 524 599 517 640 638 561 496 445 552 473 501 429 377 401 427 511 487 424 416 425 375 402 434 386 389 391 374 351 435 405 320 355 430 416 476 343 391 380 395 374 433 393 365 342 316 409 291 393 378 412 357 357 474 388 403 377 387 433 420 452 400 391 400 457 377 521 525 435 480 669 415 492 495 755 470 514 563 406 421 472 433 417 329 362 482 373 373 418 545 604 480 546 486 363 470 275 330 553 408 406 435 404 425 419 432 328 387 381 414 445 271 336 389 328 376 346 319 430 274 255 320 265 180 246 252 260 227 232 168 255 241 199 268 220 255 257 185 309 232 274 279 278 290 235 227 284 263 263 285 205 173 317 232 307 204 243 222 272 220 175 241 228 262 296 273 250 201 236 239 255 192 183 184 211 193 212 208 218 189 211 185 236 132 188 181 181 215 218 216 212 267 167 230 132 203 256 272 252 290 214 284 211 185 258 197 175 186 210 220 209 219 182 144 184 205 205 218 185 135 246 200 153 127 138 140 145 154 146 159 230 168 207 196 122 158 205 187 184 177 189 171 139 183 103 178 190 195 236 160 148 124 161 234 223 165 223 227 183 154 127 171 182 221 231 154 195 201 126 235 191 177 193 170 184 215 208 150 182 117 174 191 266 242 211 198 149 156 196 162 205 250 182 165 188 253 213 192 183 156 203 180 204 223 154 159 225 210 285 156 148 172 130 177 144 199 149 198 198 148 248 190 127 161 170 152 185 186 140 133 170 113 128 176 142 187 163 202 193 140 128 201 169 290 165 310 141 226 206 227 189 178 206 226 102 136 186 172 164 131 108 184 209 108 136 156 139 128 101 160 90 158 186 144 130 122 172 103 180 148 143 116 120 112 90 133 57 138 132 69 100 136 157 95 107 85 80 102 144 128 129 133 158 96 137 150 211 235 159 168 124 119 157 108 110 126 148 122 130 119 155 197 131 143 129 119 111 184 131 133 96 99 106 75 68 79 118 125 126 115 122 159 121 78 93 98 93 97 73 76 136 108 87 88 66 116 133 155 104 49 120 115 68 90 97 120 64 81 103 83 64 80 106 83 56 69 85 102 94 84 52 110 70 68 109 61 83 100 68 35 53 93 90 84 43 61 68 36 99 69 54 82 86 53 48 69 53 39 79 88 50 68 57 68 83 67 72 63 73 62 94 85 58 75 65 69 86 71 76 76 58 94 118 129 66 79 74 99 81 55 91 68 69 96 57 73 64 53 72 53 90 75 68 90 87 48 109 117 70 78 64 70 86 83 84 65 84 86 52 66 106 57 69 54 45 70 66 59 59 43 56 68 54 46 80 71 54 76 53 83 41 44 63 57 57 51 80 52 37 89 78 76 42 63 57 79 61 79 68 47 69 44 80 38 54 71 57 53 74 40 26 62 59 52 108 44 66 74 35 45 52 77 30 63 38 58 77 41 51 60 106 43 71 43 43 86 108 61 46 53 70 57 88 89 71 79 90 123 81 65 84 62 82 96 54 90 160 198 134 60 139 152 105 107 101 138 140 110 104 95 69 83 107 122 84 79 104 136 85 100 108 157 115 142 149 118 91 106 103 102 60 79 76 97 74 64 90 117 81 52 77 70 90 74 122 67 68 88 65 34 74 79 70 68 52 41 52 40 84 45 41 56 49 29 43 22 49 41 67 46 86 48 55 72 38 61 69 73 52 52 43 45 14 67 83 51 40 59 49 44 26 42 35 53 81 43 55 67 27 73 29 61 33 81 72 66 63 71 68 77 60 74 58 85 49 102 59 106 71 80 89 78 91 57 40 79 63 56 64 35 50 35 70 40 63 55 69 30 59 47 32 47 92 44 32 24 25 33 47 31 34 69 34 74 39 38 31 49 41 18 55 26 37 47 52 53 39 37 32 34 34 25 33 22 24 31 23 24 47 32 29 36 27 34 43 31 35 34 31 30 25 40 18 32 17 24 30 30 42 50 48 44 15 41 65 17 42 15 33 29 30 44 61 20 50 30 36 21 21 41 53 38 30 55 36 48 36 31 20 79 52 49 31 54 16 28 23 33 28 32 35 37 22 24 13 25 26 28 26 15 15 17 11 14 14 25 29 20 11 35 31 15 41 30 18 17 35 28 32 45 19 13 12 10 32 30 49 24 16 17 40 27 24 21 16 31 34 27 37 21 11 40 42 26 49 56 61 19 35 21 45 20 32 45 34 27 29 
];
B = [
0 0 0
 94954 22975 71979
 112304 28411 83893
 124115 35094 89021
 104499 27384 77115
 119578 32438 87140
 143730 40203 103527
 161224 45462 115762
 185530 52389 133141
 252785 78447 174338
 141830 42706 99124
 424011 166111 257900
 110768 37776 72992
 92500 35293 57207
 66869 26799 40070
 46809 16555 30254
 31338 9460 21878
 37412 12074 25338
 24993 7233 17760
 34539 10297 24242
 33474 9435 24039
 57376 17389 39987
 55795 16060 39735
 67192 21623 45569
 55328 16077 39251
 76019 23784 52235
 68230 22574 45656
 144803 51815 92988
 43389 15612 27777
 137402 50176 87226
 53502 19747 33755
 52112 18450 33662
 46229 18943 27286
 55746 22903 32843
 40576 15644 24932
 47957 19373 28584
 42586 15940 26646
 36238 14797 21441
 52944 21407 31537
 45810 19095 26715
 40878 17433 23445
 54044 20612 33432
 37909 17038 20871
 97445 38038 59407
 48316 21909 26407
 34210 16094 18116
 47156 20757 26399
 50773 24952 25821
 56017 24922 31095
 61450 30453 30997
 38912 18159 20753
 43141 20699 22442
 63845 31020 32825
 42739 20392 22347
 74639 38583 36056
 59864 27707 32157
 79661 34760 44901
 46947 26545 20402
 67216 32008 35208
 116809 63804 53005
 30148950 20436502 9712448
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
2 11 0 0
0 1 0 2
4 0 0 0
3 3 1 0
13 9 3 2
42 5 13 8
59 3 47 26
80 7 34 56
1484 11 98 48
16148 16 149 69
92803 30 149 156
468734 36 310 231
1361058 64 397 347
2076430 172 637 675
1982598 345 1127 1113
1628782 593 1862 1756
1109535 1161 2725 2708
578219 1767 3769 3821
205262 2786 5457 5040
39902 3714 6649 6615
10471 5473 8197 8689
11619 7410 10489 10560
13258 9931 12355 12535
15252 12896 14930 15125
18635 15837 17492 17557
21388 19416 20551 20938
24803 24392 23825 24133
28796 30210 27833 28301
33461 32985 32771 32246
38550 38160 37616 37628
42587 42783 41846 42353
47675 47085 46729 46058
52169 51054 49331 51172
55120 55849 54734 55229
60277 59726 58963 58554
61690 62251 62608 62234
64697 66849 64679 65134
69057 70000 67785 68549
71257 73316 71527 70987
77601 78565 74960 74841
79330 78448 78398 78926
81976 83881 84254 83217
86836 87291 87630 86842
93605 92888 92476 91728
99558 97885 96995 97561
106178 106858 104058 104132
111750 109579 108889 110106
118054 117458 116223 115742
121608 121576 121858 119633
125294 126223 124966 124645
128102 128018 127430 128701
131611 131515 130273 130639
132680 132423 132215 133685
131946 133100 131939 132332
129844 130511 129626 129733
125960 126189 125230 124944
117527 119487 119581 120400
108339 108071 105519 107912
93010 94180 93138 94091
76942 77957 76908 78983
62935 64949 62886 64450
41327 43493 41588 43466
17594 19018 17931 18258
3568 3806 3752 3484
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
