A = [
59010 93198 566841 69811 99972 92998 88405 98628 100366 98351 101875 106298 104587 101259 104779 103396 100412 102971 102269 101138 101882 99200 97269 96732 93041 94166 95927 93379 92237 94358 92039 90623 91570 88909 87620 88687 87819 86501 88910 87764 86464 86081 84687 82269 82731 81930 80745 81844 80529 78882 79804 77888 75508 75757 73302 71797 73607 71975 69559 69947 68558 66564 65676 64107 61978 61490 60180 58495 58485 56511 54619 54870 52836 50486 49717 48297 46823 46544 44812 43299 42940 40919 39516 38435 37189 36057 35539 33994 33279 32350 31122 30292 29456 28415 27031 26586 25911 24271 24219 22938 22507 21851 21206 19988 19547 19163 18082 17754 17298 16552 16063 15655 14991 14663 14183 13575 13291 12704 12288 12148 11676 11141 11028 10607 10265 10182 9655 9302 9225 8593 8728 8327 8034 7965 7552 7378 7229 7093 6772 6628 6644 6353 6091 6037 5807 5640 5668 5592 5316 5127 5042 5003 4739 4759 4455 4474 4355 4284 4312 4146 4081 3937 3926 3788 3798 3758 3587 3642 3455 3445 3472 3282 3218 3206 3144 3078 3064 3032 2873 2940 2819 2838 2798 2721 2666 2629 2718 2679 2586 2514 2445 2468 2428 2463 2439 2384 2369 2276 2308 2215 2227 2244 2258 2308 2196 2114 2154 2107 2033 2115 2013 2023 2001 2035 1971 1996 2007 1966 1859 1885 1864 1809 1788 1833 1788 1862 1781 1818 1753 1713 1862 1684 1867 1699 1704 1655 1698 1695 1681 1654 1758 1717 1603 1628 1528 1579 1471 1639 1473 1565 1508 1477 1460 1443 1466 1588 1384 1414 1366 1404 1518 1476 1504 1440 1475 1425 1372 1328 1393 1432 1337 1369 1330 1318 1266 1320 1250 1329 1287 1211 1338 1333 1191 1246 1274 1249 1192 1207 1317 1140 1192 1150 1099 1109 1118 1200 1180 1126 1129 1160 1125 1188 1045 1133 1064 1076 1077 1112 1085 1025 1092 1052 1072 1010 1042 1100 1064 1034 990 960 1018 970 982 1033 964 926 925 923 951 912 986 902 879 879 908 926 940 890 919 920 960 973 917 823 900 870 908 855 821 875 819 896 846 866 836 825 828 792 811 901 778 786 789 829 808 828 756 831 793 784 787 805 813 763 756 785 776 741 740 752 741 754 741 740 738 742 746 703 725 716 705 668 688 666 644 633 716 664 672 680 681 659 694 614 640 670 666 624 682 638 600 608 619 621 570 612 616 608 542 547 591 569 947 576 579 576 563 555 544 641 538 565 560 524 591 591 581 555 550 522 552 490 477 516 520 473 509 499 528 543 550 482 517 492 505 485 489 494 493 519 503 470 515 464 490 454 454 453 482 426 481 474 482 451 471 462 471 456 466 502 421 465 417 491 442 433 396 456 420 440 451 403 390 460 444 439 431 422 393 369 441 410 357 397 448 423 454 379 412 356 384 366 422 385 401 415 408 413 399 391 352 340 398 377 368 398 354 374 366 333 391 335 335 368 344 345 381 336 359 339 339 354 350 344 323 311 352 349 368 296 365 352 338 312 347 371 350 361 339 374 311 302 328 335 338 337 317 336 301 308 332 307 316 285 298 287 291 269 293 314 308 304 271 306 310 354 266 288 305 281 264 253 254 293 290 265 271 277 295 253 273 286 271 249 253 216 262 255 250 263 246 251 268 220 261 269 210 254 249 242 238 206 222 255 252 247 257 236 226 235 224 223 232 213 231 207 231 175 207 234 230 185 227 211 225 188 209 225 214 217 181 199 191 204 204 192 174 198 197 189 209 197 182 204 188 209 195 196 193 165 214 202 206 220 200 183 192 209 191 220 198 170 188 207 167 195 183 182 179 158 179 194 187 180 191 201 184 210 196 176 178 181 199 201 163 186 188 198 176 196 203 174 180 188 168 185 170 162 160 168 175 170 167 170 175 180 155 162 176 163 169 160 148 162 141 154 177 143 191 153 151 168 151 169 139 154 150 152 166 118 123 142 122 122 130 147 134 120 143 130 130 132 128 127 113 124 132 158 133 136 122 138 124 147 121 118 123 123 157 107 115 121 118 136 128 102 127 127 128 125 139 116 104 117 119 118 134 118 113 124 120 103 98 125 115 120 122 102 114 114 96 122 110 105 85 102 122 113 86 131 114 114 100 106 95 103 112 91 78 106 102 107 108 94 87 109 96 99 83 97 114 80 126 109 94 84 112 89 107 103 95 103 93 121 78 90 91 112 98 94 93 86 91 87 83 81 81 89 112 117 78 101 95 90 103 84 106 115 91 105 83 93 96 99 104 98 82 95 80 104 95 91 86 89 94 79 79 98 79 95 102 71 92 80 68 71 83 95 76 62 77 98 70 75 78 84 74 68 65 71 68 89 74 57 84 76 73 75 76 78 82 68 76 68 83 74 74 75 56 58 75 74 77 78 75 56 83 77 60 60 83 56 74 60 61 49 58 51 55 83 66 62 50 66 41 68 52 59 57 68 70 75 73 53 54 48 66 40 57 57 53 55 48 67 49 71 56 52 60 47 77 49 51 70 56 71 42 53 59 58 67 47 44 46 57 72 56 57 53 82 51 59 50 51 58 42 54 60 48 55 38 58 40 59 50 52 67 56 43 66 42 40 53 45 42 55 42 38 60 44 47 45 57 60 37 40 52 50 59 53 37 46 34 45 32 48 41 51 48 76 51 44 46 51 40 30 51 48 40 33 46 47 37 47 61 54 43 37 37 39 36 35 50 49 31 36 48 24 45 25 43 41 49 36 42 39 37 42 35 43 41 43 43 31 40 30 35 43 30 33 30 39 34 29 34 24 26 34 40 24 28 28 48 34 27 29 36 34 40 37 36 32 41 36 29 33 35 34 37 38 42 21 29 26 37 28 28 34 42 31 33 34 38 44 31 23 25 29 26 36 25 31 26 34 23 30 28 27 25 21 32 29 30 32 26 36 24 31 29 34 28 21 27 32 41 19 38 25 32 37 15 36 16 24 27 33 31 26 28 23 28 19 32 12 28 23 27 24 23 22 29 28 21 24 28 31 30 24 15 27 23 26 26 22 32 26 24 24 22 26 24 21 22 21 24 19 23 25 28 9 23 27 24 21 20 21 17 21 24 13 26 24 20 29 26 25 29 14 25 21 27 24 17 15 33 24 29 16 24 30 17 21 11 20 12 20 24 19 17 16 22 12 22 20 13 19 17 20 20 14 14 23 23 17 23 17 14 17 20 18 15 15 7 23 15 17 15 9 23 14 19 16 22 12 17 19 13 18 13 19 21 10 18 13 19 28 20 13 23 14 19 17 16 20 17 13 21 14 22 19 12 9 15 22 12 9 12 15 9 18 19 14 8 13 14 7 12 14 16 7 10 11 16 11 10 13 12 8 14 10 15 8 11 6 10 16 13 7 13 17 10 11 9 10 16 15 9 7 13 9 23 7 6 10 15 10 9 18 8 15 12 13 4 14 11 12 11 9 10 13 6 15 13 11 9 7 14 5 6 13 14 11 18 16 9 11 12 12 8 11 8 13 17 7 12 11 11 8 15 14 8 8 9 8 6 13 9 14 11 12 7 11 15 13 8 11 9 13 15 16 9 15 7 12 12 5 11 13 10 9 10 4 21 6 11 8 15 14 6 6 9 9 9 10 5 8 19 15 13 7 6 11 7 15 12 11 5 8 6 9 11 11 8 13 8 6 6 9 9 7 6 4 4 1 8 9 6 8 11 4 7 6 5 18 11 6 6 6 8 8 8 3 10 7 8 10 7 7 9 8 7 11 5 12 8 7 10 10 5 11 8 7 7 8 6 13 11 11 2 6 16 10 3 3 8 8 7 10 12 6 11 10 4 9 10 7 8 4 4 9 7 6 13 10 13 11 9 9 8 5 7 7 6 4 5 5 4 9 6 4 4 0 5 7 7 3 8 7 6 6 10 3 6 7 8 8 7 10 4 5 6 8 9 6 10 7 6 10 6 6 5 2 12 11 6 7 4 2 9 10 5 7 7 8 4 8 12 4 6 10 8 5 12 3 4 10 5 5 6 7 7 4 7 18 7 4 5 7 6 13 4 7 3 1 13 10 10 7 4 4 4 5 11 5 3 4 7 5 10 9 4 11 6 7 3 3 7 7 3 7 4 1 6 6 12 4 2 2 3 11 4 8 2 4 2 6 9 5 3 9 3 7 3 1 15 8 11 8 10 7 4 6 5 3 6 3 6 9 2 0 2 6 1 4 8 3 2 3 9 5 3 3 3 4 2 3 4 5 8 7 2 5 6 2 1 1 5 6 4 3 4 4 3 2 3 6 1 3 3 5 4 2 4 2 3 7 3 1 3 3 5 3 2 2 4 4 2 7 1 1 3 3 2 7 1 3 3 3 2 2 2 3 0 2 2 2 5 1 0 2 9 4 3 1 2 1 2 5 2 1 5 3 3 3 2 1 9 5 2 5 2 2 5 0 4 3 1 1 2 3 3 4 1 3 3 0 2 1 2 3 2 6 4 4 4 3 4 0 2 3 2 4 6 2 5 4 6 3 3 2 2 3 4 5 2 2 1 8 7 2 9 3 7 4 4 5 6 5 2 2 3 5 4 7 8 4 3 2 2 2 8 2 5 0 3 3 3 2 6 4 0 2 4 2 3 4 4 5 3 1 0 0 2 4 1 3 3 2 3 0 4 1 3 2 3 5 5 3 0 3 0 1 3 0 2 6 1 3 1 1 3 4 3 3 2 3 3 3 2 1 4 0 2 4 4 3 4 2 2 2 1 1 1 2 2 3 6 5 5 6 2 1 1 2 7 4 1 0 5 1 
];
B = [
0 0 0
 24380 9709 14671
 13301 5110 8191
 47590 25090 22500
 10044 3543 6501
 10746 3864 6882
 15669 6098 9571
 17652 8656 8996
 16007 6442 9565
 37303 22203 15100
 9602 4072 5530
 11425 4893 6532
 11824 5532 6292
 23439 12398 11041
 11877 5348 6529
 37580 24378 13202
 9902 5419 4483
 10923 6087 4836
 12467 7065 5402
 25741 15266 10475
 11183 7273 3910
 43152 28263 14889
 17585 11346 6239
 13566 8852 4714
 38084 23309 14775
 50913 35645 15268
 7127 4030 3097
 180771 129144 51627
 2190 1766 424
 6102 4365 1737
 3990 3106 884
 7542 6174 1368
 2493 1736 757
 29632 24713 4919
 1960 1443 517
 5667 4196 1471
 3692 2913 779
 6663 5556 1107
 755 438 317
 32649 27307 5342
 1 1 0
 53 47 6
 580 332 248
 6092 4744 1348
 685 488 197
 583 430 153
 1089 673 416
 1744 1060 684
 53376 45092 8284
 41 29 12
 672 530 142
 639 471 168
 769 545 224
 2336 1585 751
 54075 46689 7386
 965 797 168
 974 794 180
 1285 1179 106
 33566 28620 4946
 18125 16250 1875
 3435029 3303940 131089
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
17 26 0 1
9 13 0 0
26 9 0 0
33 19 0 1
39 22 0 0
63 29 1 0
498 21 1 2
5764 40 1 1
67263 58 2 4
386881 104 9 11
814728 117 8 17
971439 122 11 18
781666 87 11 19
499974 94 16 19
233046 160 14 13
84519 141 22 26
34532 120 17 26
16261 163 21 23
6967 231 14 36
2466 279 47 39
1184 206 19 34
935 164 51 60
961 350 29 40
989 377 52 67
862 308 51 53
1046 566 48 24
1268 802 59 57
1478 843 82 62
1458 1003 82 91
1571 1184 137 155
1624 1261 178 178
1804 1502 156 135
1744 1343 171 206
1694 1388 202 211
1514 1508 176 174
1433 1281 195 200
1655 1503 219 241
1357 1169 227 296
871 926 197 194
910 1029 146 124
754 742 145 114
690 686 229 202
454 432 123 119
269 274 149 96
162 176 82 84
40 39 104 93
73 74 72 64
94 85 91 110
95 115 68 59
33 27 109 127
86 75 75 99
26 22 33 44
32 17 39 34
12 9 37 32
26 34 14 13
10 3 16 20
6 3 2 5
3 1 8 3
1 1 0 1
0 0 1 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
