A = [
33700 51605 440835 42766 55191 57513 54708 50603 52981 51969 54836 58358 57874 56803 58629 57430 57113 57423 56866 56191 56078 54576 55880 53225 53617 51891 53316 51484 51009 52700 51208 49731 50530 49523 48994 49985 49247 47948 49118 48623 47972 48229 47508 45908 45343 45150 45475 45708 45204 44154 44698 43763 42686 43062 42332 41692 42111 42016 39835 40820 40602 38731 39676 38199 37170 37229 35442 35397 34590 32876 31973 32686 30570 29912 29197 28382 26916 27356 26929 26807 24532 23295 22195 21484 20797 20391 19210 23315 19121 17848 16516 16560 15759 15747 13853 13784 13462 12597 12387 12068 11787 11845 10611 10355 9768 9614 8788 8942 8874 8209 7908 7641 7062 7287 7523 7059 7719 6511 5919 5809 5528 5371 5769 5223 4851 4910 4580 4318 4372 4130 4112 3931 3781 3701 3684 5028 3648 3967 4568 6232 6254 3246 2990 2836 2967 2617 2690 2787 2548 2478 2456 2266 2258 2357 2383 2126 2046 2112 2204 1971 1811 1791 1868 1648 1653 1742 1624 1754 1747 1576 1626 1660 1585 1691 1576 1665 1685 1452 1410 1373 1304 1336 1421 1322 1226 1387 1447 1384 1215 1219 1222 1219 1072 1439 1389 1223 1131 1112 1392 1288 1356 1482 1342 1476 1162 1214 1096 981 1029 1167 1005 1087 983 1030 1028 998 1021 1178 934 1010 933 893 947 903 896 894 897 911 929 830 931 800 976 891 891 874 903 896 833 929 923 870 774 1094 780 914 714 960 968 858 829 764 863 788 758 840 846 895 727 834 898 742 913 1497 806 908 771 779 902 1442 898 1338 751 739 794 746 1072 693 673 760 967 754 607 737 700 786 712 625 821 1131 870 1042 584 709 560 733 692 654 601 628 616 640 1299 566 849 565 631 543 613 539 735 775 519 531 574 654 588 542 501 518 568 482 535 530 571 522 458 419 436 512 441 460 482 500 446 477 529 427 532 547 494 514 451 460 502 426 488 538 394 513 433 545 421 382 482 455 430 372 376 474 476 499 392 421 400 437 432 475 407 386 395 468 422 425 356 355 423 336 378 368 400 418 490 389 337 336 368 400 333 403 364 337 406 343 400 296 330 390 383 448 341 395 421 284 370 425 339 345 333 424 319 304 322 425 327 408 248 363 253 278 258 269 280 217 254 271 277 299 246 358 261 220 241 232 342 290 315 277 237 253 287 259 224 298 276 224 334 249 248 361 246 218 233 228 266 246 254 266 237 255 245 203 257 195 242 183 195 216 202 192 209 222 196 266 232 273 235 227 226 244 192 196 207 254 192 243 176 203 294 200 217 192 265 197 247 207 206 163 169 466 174 254 209 189 260 241 322 254 182 163 184 199 227 209 204 444 200 361 170 200 226 284 240 185 205 216 199 206 213 172 229 179 169 197 178 153 224 197 175 204 201 191 227 174 198 177 182 192 174 164 225 183 186 226 192 172 166 182 157 189 147 167 178 204 180 204 155 219 161 172 178 160 153 144 142 124 151 116 143 161 123 136 131 171 170 170 111 125 143 174 122 117 117 124 128 123 126 108 126 148 111 121 148 118 117 101 129 137 99 143 107 112 117 119 133 120 99 122 101 121 91 75 139 126 129 103 106 116 112 104 108 124 104 81 105 77 93 89 129 123 101 81 95 90 88 98 77 101 71 80 66 73 86 87 81 76 100 79 98 68 119 70 86 89 70 99 74 131 100 83 80 63 94 114 118 80 85 93 97 125 100 101 87 80 89 81 74 121 82 75 85 72 93 80 93 122 78 128 110 90 78 100 132 86 96 112 144 86 93 81 89 118 82 99 78 90 97 69 86 83 103 110 99 107 125 120 120 75 100 76 118 74 62 68 53 55 61 63 76 68 71 96 76 106 76 84 50 73 63 51 42 75 54 63 101 57 81 46 64 51 59 66 53 40 27 39 78 71 73 74 36 70 44 49 62 63 41 64 112 66 44 66 54 63 42 48 50 45 55 48 72 46 61 54 45 64 37 43 39 40 51 40 44 56 46 61 45 58 45 39 44 43 52 55 35 42 64 44 67 51 66 61 77 60 37 29 39 36 33 65 53 47 53 41 41 56 40 60 38 49 49 30 58 43 40 37 37 32 61 40 48 55 53 47 41 37 48 34 61 43 42 29 31 42 43 20 43 52 48 68 37 44 39 41 46 39 68 42 37 60 36 41 59 43 37 44 30 62 39 39 49 104 46 45 31 36 42 69 37 67 67 31 89 22 38 29 44 71 34 39 46 52 24 39 30 47 74 40 51 43 30 87 38 24 75 79 49 211 82 109 97 53 46 40 43 63 48 39 45 26 73 48 52 43 71 45 48 52 41 39 54 33 30 22 17 30 53 26 32 38 223 42 24 45 24 71 37 34 82 55 49 106 44 37 23 27 36 24 28 32 32 21 29 44 21 38 37 31 45 24 43 17 21 25 22 33 24 31 48 26 28 27 42 34 41 26 108 26 67 62 28 35 31 29 30 38 75 29 31 55 18 47 20 35 50 50 31 119 52 106 38 47 70 19 22 35 19 17 18 21 18 38 25 37 18 21 31 29 22 33 15 10 11 17 18 30 15 34 21 24 23 19 29 27 15 16 10 19 23 20 25 25 49 29 30 23 18 14 14 29 22 20 20 29 30 21 23 13 19 13 25 19 17 29 13 31 27 12 18 9 13 15 22 12 13 22 22 22 10 20 19 24 14 11 11 11 5 16 13 9 20 14 21 15 15 10 11 12 10 16 20 24 19 21 26 16 21 27 27 14 30 30 14 19 22 20 12 20 19 13 16 15 28 43 16 9 54 14 9 26 11 12 14 16 9 10 11 13 9 11 16 13 18 12 12 12 12 17 14 10 8 6 11 19 24 6 17 12 34 15 8 47 4 8 6 12 9 10 4 9 18 19 11 7 19 13 12 5 10 8 21 15 8 18 20 18 10 7 15 5 9 22 15 14 27 10 10 18 8 6 4 9 6 13 9 13 4 11 9 4 12 23 10 17 19 9 11 14 10 6 11 7 5 9 12 9 29 8 13 11 16 7 7 7 16 29 18 6 16 17 10 8 7 6 6 9 16 14 7 6 8 8 9 11 2 14 11 11 8 8 3 3 16 8 16 15 12 4 11 8 24 28 4 41 34 3 17 2 11 1 8 5 26 9 5 16 6 7 11 8 7 4 11 3 7 19 10 7 7 1 7 11 9 7 11 5 14 29 27 21 1 21 5 25 8 4 5 6 5 15 2 3 4 2 3 1 6 5 3 4 3 2 5 3 5 7 4 2 4 8 0 2 4 1 0 7 3 9 3 8 3 3 0 3 6 4 8 5 4 4 6 0 9 3 5 5 1 15 8 7 8 13 6 4 5 4 7 4 13 4 10 4 7 4 10 3 3 2 2 0 3 4 7 12 9 8 4 3 5 15 4 8 4 15 8 8 32 8 30 12 10 12 7 4 8 5 4 4 14 24 23 3 8 7 3 31 8 76 21 14 10 32 5 4 7 6 5 2 4 1 7 0 35 1 15 12 9 10 4 6 3 1 4 13 5 2 7 61 10 3 29 10 12 70 3 5 3 2 4 14 1 5 43 17 10 0 1 1 1 2 2 3 7 2 7 7 3 3 4 3 4 2 2 9 8 5 1 4 3 2 10 7 6 4 5 6 4 0 6 1 2 8 1 7 5 3 1 7 1 2 1 8 4 6 7 1 4 8 10 4 5 9 1 0 0 5 1 13 8 1 6 2 1 3 1 8 1 3 1 2 1 1 9 2 11 10 6 4 9 5 2 5 1 2 3 4 7 6 0 2 3 0 4 0 1 4 3 3 2 2 6 3 1 1 5 5 3 5 1 2 6 3 3 10 3 5 0 7 3 3 0 1 5 5 3 1 4 1 6 5 3 4 4 4 6 7 5 0 2 18 13 4 24 3 6 5 0 3 4 3 3 0 0 7 3 1 2 3 0 9 2 7 7 2 8 5 9 5 1 4 1 2 7 8 1 3 5 0 4 5 2 2 2 2 1 8 1 4 3 1 3 3 1 2 10 14 1 0 6 1 1 1 1 7 0 1 2 2 3 2 3 2 2 0 10 2 3 1 1 0 5 2 1 0 3 2 2 8 1 0 1 0 0 0 1 0 0 3 3 0 1 1 0 0 0 4 3 1 6 3 1 4 3 1 1 1 1 2 2 2 0 1 1 5 0 0 0 1 1 1 0 2 0 1 4 2 1 1 0 3 1 0 0 0 1 3 0 0 0 0 2 2 0 1 1 1 1 3 1 2 1 1 0 2 0 0 0 1 0 0 0 2 1 0 1 0 1 2 0 0 6 0 1 0 0 0 4 2 1 2 0 1 3 0 0 2 1 1 0 0 4 0 2 0 3 0 0 0 1 1 0 2 0 3 2 2 2 0 0 0 1 3 2 0 2 4 2 0 0 3 2 0 1 0 3 2 0 5 1 4 0 0 1 4 3 2 1 2 3 0 2 2 0 3 5 2 1 0 0 4 4 1 1 0 1 1 1 2 2 4 0 1 3 1 1 5 0 5 2 0 0 0 7 2 5 2 1 0 0 0 3 1 1 0 1 0 8 2 0 0 0 0 0 0 1 4 1 0 0 0 1 1 2 0 3 3 0 1 3 0 0 0 0 1 0 0 2 0 1 0 1 0 0 1 0 2 7 0 2 6 6 1 0 1 0 3 0 0 0 0 
];
B = [
0 0 0
 19413 9585 9828
 9359 3781 5578
 32869 15928 16941
 5294 2024 3270
 5888 2256 3632
 10815 3945 6870
 13586 7463 6123
 11817 4614 7203
 25316 13809 11507
 5288 2230 3058
 6411 2774 3637
 6763 3075 3688
 16936 8511 8425
 8117 3240 4877
 25515 14899 10616
 5523 2962 2561
 5814 3292 2522
 6852 3886 2966
 16768 8980 7788
 6367 3910 2457
 29327 17731 11596
 10672 6336 4336
 9588 5115 4473
 25519 14194 11325
 32379 21381 10998
 4394 2261 2133
 125139 82124 43015
 1073 900 173
 3439 2453 986
 2017 1572 445
 3992 3393 599
 1386 943 443
 17158 14462 2696
 942 720 222
 3272 2397 875
 1927 1516 411
 3505 3054 451
 360 203 157
 18861 15727 3134
 2 2 0
 11 9 2
 214 124 90
 3385 2455 930
 333 239 94
 258 185 73
 565 322 243
 903 552 351
 28864 24939 3925
 19 13 6
 287 236 51
 273 181 92
 366 247 119
 1102 718 384
 30009 26133 3876
 493 410 83
 491 405 86
 513 458 55
 14589 12088 2501
 8273 7389 884
 1912504 1864112 48392
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
15 56 0 0
3 14 0 0
23 6 0 0
22 10 0 0
43 26 0 0
41 30 0 0
361 15 1 0
1786 44 0 0
31303 100 0 2
272244 235 2 6
570544 402 3 11
564111 251 2 8
384660 182 5 9
227769 136 4 5
99541 175 12 4
32811 99 15 9
12318 278 16 6
5498 838 12 16
2130 10723 13 14
999 1018 51 16
1262 185 10 26
589 93 33 23
574 508 10 22
540 730 18 29
346 243 32 22
584 426 23 10
674 483 22 30
876 438 51 42
782 601 48 55
1186 1050 117 92
899 716 133 88
1202 1145 100 63
1034 826 76 125
975 1148 109 117
846 850 112 111
772 729 84 112
1041 861 98 138
780 597 110 188
461 443 87 134
471 573 72 58
418 387 99 58
1462 921 136 195
361 308 65 108
149 116 80 59
68 101 41 36
18 9 49 42
36 23 48 25
56 39 42 55
50 80 19 27
7 12 54 55
81 48 29 109
5 11 11 20
13 7 16 27
3 2 16 10
13 22 9 5
4 1 1 4
0 0 0 2
4 0 3 0
0 0 0 0
0 0 2 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
