A = [
74301 67511 268486 68957 64064 62435 60696 61445 62097 60707 61584 64166 64739 66777 68940 69900 71993 75504 75116 75161 77418 77018 77223 79293 84079 139564 139718 141829 194804 186970 193448 194367 184422 188432 191877 190780 184012 184242 182787 179329 177398 177253 176385 173958 174485 171237 168805 168221 164521 160985 158408 157538 156332 154921 152858 152122 147769 145636 143598 141758 139700 136969 134532 133478 131758 129490 128169 126354 124632 122833 120547 118201 116112 115049 112500 111144 109126 106720 105315 104005 102456 100025 97979 96396 95102 93729 92193 90528 88682 86983 85806 83587 81990 81037 79949 78306 76578 75592 74340 72433 70963 69905 68831 67459 66622 65588 64589 63179 61662 60591 59604 58413 57208 55327 54540 53991 52979 51355 50600 49931 49123 47780 46988 45916 44836 43586 43255 41774 40723 40779 39635 39555 38296 37527 36764 35948 35793 34482 34045 33114 32254 31436 31167 30787 29973 29241 28663 27969 27435 26530 26224 25866 25043 24683 24091 23607 23333 22855 22261 21759 21360 20780 20121 19775 19426 18970 18743 18135 17748 17644 17020 16527 16375 16089 16018 15352 14753 14760 14403 14118 13650 13528 13157 12863 12638 12164 12316 12066 11448 11474 11213 11099 10830 10641 10510 10060 10222 9958 9730 9313 9162 9011 8830 8672 8385 8319 8093 7957 7858 7752 7606 7419 7357 6903 6884 6830 6787 6425 6288 6381 6185 5982 5944 5547 5674 5454 5359 5476 5256 5073 5003 5032 4890 4645 4711 4661 4640 4541 4393 4149 4237 4233 4094 4052 3926 4100 4018 3785 3798 3771 3531 3525 3373 3630 3414 3326 3218 3281 3248 3244 3130 3124 2991 3045 2939 2938 2920 2810 2910 2912 2861 2823 2689 2746 2602 2620 2495 2481 2552 2649 2702 2658 2608 2627 2602 2466 2413 2476 2530 2413 2450 2374 2271 2319 2217 2191 2256 2134 2319 2367 2156 2162 2136 2266 2090 1991 1904 2085 2044 2001 1896 1927 2013 2043 1940 1839 1952 1755 1663 1735 1846 1518 1513 1441 1425 1545 1526 1253 1296 1351 1331 1229 1273 1222 1233 1191 1244 1161 1236 1264 1255 1262 1305 1224 1255 1267 1180 1094 1123 1104 1118 1187 1146 1136 1192 1188 1236 1137 1242 1162 1204 1126 1108 1094 1010 1015 1039 1078 979 991 1046 1039 932 967 996 974 951 948 949 960 873 878 855 841 1077 1034 947 1018 1015 1003 1072 1020 1070 1054 1022 1011 723 770 781 745 723 738 670 732 740 768 699 759 691 708 652 700 716 685 702 655 722 654 664 693 635 671 619 658 645 611 636 672 700 631 615 600 624 661 607 569 580 588 555 572 576 593 570 503 483 497 504 535 509 478 503 507 536 457 460 480 479 445 501 447 455 424 417 471 443 418 492 425 418 433 449 427 457 412 407 394 405 403 420 409 395 407 425 376 408 432 389 357 360 387 398 402 401 386 403 403 404 362 371 404 388 374 379 404 400 390 369 343 379 304 341 326 363 396 364 401 386 338 316 362 306 330 338 328 308 333 346 363 351 326 355 341 319 328 311 338 345 301 296 368 338 317 315 324 330 289 340 307 327 330 320 325 318 316 361 341 334 331 339 301 283 267 314 272 292 269 292 251 260 253 310 261 275 273 272 265 257 250 225 254 239 207 237 253 244 224 242 240 251 226 261 245 237 213 219 235 232 256 213 231 197 238 211 206 233 216 187 232 208 212 222 251 248 244 226 228 196 206 207 211 214 209 198 215 219 199 185 208 173 173 194 200 210 213 195 193 182 192 164 167 145 154 163 165 153 166 167 161 150 158 148 148 128 163 137 151 150 122 151 144 151 161 163 131 153 145 118 142 123 157 132 144 126 134 160 112 140 118 116 115 126 121 124 129 123 133 123 122 123 135 128 142 127 119 138 123 146 132 140 134 130 132 141 139 140 126 108 131 134 109 127 141 130 135 128 139 134 134 130 151 120 113 124 121 147 148 113 121 130 136 133 112 136 150 134 128 169 141 163 125 126 131 130 161 137 125 153 124 164 142 146 117 163 108 131 155 112 144 96 112 111 114 97 113 92 98 116 102 100 95 122 112 75 111 79 100 87 87 88 79 80 83 95 66 88 98 92 104 90 84 82 81 73 113 112 101 83 83 85 95 91 102 96 79 73 66 76 73 67 72 85 70 72 75 74 79 73 79 65 71 75 72 68 61 64 93 71 63 69 78 77 73 91 55 78 68 73 108 82 90 79 74 89 89 82 84 75 78 88 80 77 95 87 65 67 89 89 54 56 53 57 49 62 41 53 67 67 52 69 73 75 81 68 70 64 62 62 66 71 76 89 72 88 62 75 83 57 60 72 69 48 73 61 70 53 45 55 48 52 42 59 43 61 52 45 65 50 52 53 38 63 49 44 40 50 54 51 47 51 55 53 46 40 36 31 49 52 39 43 36 54 36 48 32 45 37 27 31 49 38 35 36 29 36 37 34 39 32 40 37 34 39 35 40 42 37 36 25 33 32 43 33 34 28 28 37 35 40 36 32 27 37 41 26 26 29 30 26 23 28 29 29 24 27 20 31 29 23 20 27 26 19 24 24 30 28 34 29 32 32 34 47 28 16 19 24 20 29 23 26 19 20 22 30 21 19 25 33 26 22 25 33 35 30 28 27 27 23 36 30 50 39 47 38 35 32 30 31 42 33 41 32 36 36 35 38 44 29 27 40 24 26 28 23 19 23 36 35 35 47 38 29 35 39 23 29 34 22 27 19 19 22 26 28 27 35 27 20 15 21 24 20 17 23 29 27 26 12 19 19 35 23 27 18 24 22 23 16 18 21 17 19 23 24 24 22 30 26 25 19 25 28 25 25 26 24 28 21 20 27 26 20 13 13 20 27 29 23 19 9 16 14 20 22 21 12 16 16 17 16 15 24 13 12 8 15 14 24 12 11 12 14 14 18 18 15 9 22 23 20 24 18 9 24 18 22 24 26 13 36 24 18 17 17 23 20 21 27 37 17 29 22 27 18 24 31 34 27 34 40 23 30 22 25 23 22 20 21 13 23 15 17 21 7 15 10 12 7 12 13 14 13 14 18 11 22 12 8 18 17 12 14 16 13 9 16 9 11 13 9 21 16 15 19 14 13 10 9 14 9 14 19 8 11 13 9 13 11 13 17 12 7 7 17 11 10 9 8 15 9 9 13 19 14 13 13 13 7 18 13 10 6 8 16 11 6 14 6 11 5 14 10 9 17 14 8 4 7 8 9 16 20 28 24 22 10 23 28 16 22 16 15 20 12 18 24 11 21 16 15 20 10 18 15 11 13 14 11 15 15 9 18 17 11 11 11 9 6 16 13 8 9 4 8 7 9 11 10 11 12 9 11 6 11 8 9 12 9 7 10 8 6 13 12 16 9 4 9 2 10 8 8 4 4 7 8 6 6 11 12 10 4 4 6 6 8 8 7 10 3 11 3 9 11 7 4 6 4 8 4 3 7 4 9 11 5 6 4 8 8 11 11 6 6 11 11 12 15 6 15 13 7 12 12 10 14 15 6 12 8 11 13 9 11 6 7 10 7 3 7 7 5 10 3 5 6 10 5 9 3 13 10 2 5 6 8 2 7 10 10 5 7 3 8 5 7 6 6 4 2 2 4 6 6 5 4 5 4 3 8 6 3 4 3 6 5 4 5 9 8 9 5 3 4 8 7 4 4 7 4 10 4 7 10 4 7 5 5 1 3 2 4 2 1 2 2 6 2 7 7 4 7 4 3 5 8 3 2 6 5 3 5 2 2 3 7 3 2 4 3 2 5 7 5 2 2 6 6 8 4 6 7 2 4 4 3 5 4 5 2 2 6 4 7 1 5 5 2 3 4 4 5 6 10 4 9 2 2 7 5 3 11 3 4 10 8 5 3 5 7 5 10 3 2 4 4 6 7 4 2 3 7 3 6 3 3 7 5 5 7 8 2 7 2 7 4 4 7 3 6 8 4 8 2 3 6 3 3 5 4 6 3 1 3 4 7 7 5 8 8 7 4 8 9 3 6 4 4 2 5 5 7 1 9 6 10 3 5 4 6 5 3 5 9 6 6 9 10 7 4 5 4 4 7 8 6 6 7 2 4 2 10 9 6 8 10 40 45 42 65 65 45 51 44 48 13 4 7 5 3 3 8 5 8 8 11 7 9 7 8 4 5 5 4 1 3 5 1 6 3 4 5 2 4 7 2 7 2 2 0 2 9 3 4 7 2 11 2 3 5 4 4 4 4 8 5 2 5 2 9 4 3 0 3 6 1 5 6 6 4 3 3 6 4 2 6 3 3 1 2 1 3 3 2 6 3 4 2 3 4 2 4 5 9 2 8 4 5 3 1 1 2 6 1 6 5 2 4 3 2 4 2 1 5 3 4 5 2 5 4 2 4 2 4 3 1 2 1 2 6 3 1 6 2 5 5 6 4 2 7 4 2 4 4 3 2 3 3 5 1 3 1 7 1 8 1 1 1 3 2 3 2 3 3 8 7 2 2 4 3 4 5 4 3 9 4 7 3 4 5 5 3 1 5 3 3 2 5 2 1 1 3 2 4 2 4 5 6 3 4 4 3 2 1 3 0 0 4 6 5 2 1 3 4 4 3 4 9 6 6 7 8 2 5 5 6 2 6 5 1 2 0 5 2 5 1 3 1 2 1 1 2 4 4 5 0 1 2 2 3 0 2 5 4 1 2 4 8 2 1 0 7 0 3 0 6 3 0 4 3 2 0 2 1 1 2 2 2 4 4 5 2 1 3 4 7 2 7 5 5 2 3 4 4 3 2 2 3 2 3 4 4 1 0 0 2 0 1 5 3 2 5 5 2 0 3 3 2 3 5 
];
B = [
0 0 0
 30629 7070 23559
 15993 3831 12162
 57678 15006 42672
 18329 4834 13495
 19380 4797 14583
 26256 6861 19395
 30647 8667 21980
 22880 6512 16368
 60255 17178 43077
 21434 8020 13414
 25440 10234 15206
 34556 15555 19001
 38639 12747 25892
 20329 8558 11771
 53445 15913 37532
 18095 5056 13039
 18188 5350 12838
 18931 5193 13738
 38078 9660 28418
 20245 5431 14814
 60098 16048 44050
 35391 8853 26538
 33914 10021 23893
 64263 14174 50089
 96736 24122 72614
 15800 5445 10355
 285413 73014 212399
 9421 4576 4845
 19330 8278 11052
 11930 4774 7156
 18124 6422 11702
 8943 4030 4913
 58551 19744 38807
 7220 3423 3797
 13586 5556 8030
 8914 3438 5476
 15182 5564 9618
 4727 2422 2305
 67338 22062 45276
 2263 1537 726
 3938 2443 1495
 3992 2093 1899
 11508 3738 7770
 8462 4906 3556
 3012 1640 1372
 4202 1923 2279
 8120 3840 4280
 108349 35090 73259
 3969 2580 1389
 4009 2236 1773
 3428 2008 1420
 6509 4037 2472
 8578 3545 5033
 116310 39156 77154
 5805 3148 2657
 3835 2002 1833
 5175 2741 2434
 50546 17610 32936
 39287 14377 24910
 6198786 2496332 3702454
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 13 0 0
4 5 1 0
4 4 0 0
7 0 0 0
20 5 0 0
28 5 12 0
206 2 29 3
699 4 40 4
2799 6 41 25
10705 10 50 44
115628 20 72 55
162913 49 155 80
180883 79 298 129
184761 135 344 184
153488 205 434 248
104212 393 497 424
56371 571 585 584
23135 920 954 810
8583 1177 1155 1652
3852 1698 1242 1305
2700 1962 2238 1985
2021 2334 3094 2534
2262 3594 2600 1752
2220 3143 3581 2454
2424 3463 3048 3086
2149 2841 1908 2057
2149 1882 1795 1849
2076 1914 1877 1891
2160 2100 2074 1982
2307 2408 2222 2340
2354 2405 2392 2504
2775 2616 2542 2596
2923 2818 2872 2772
3195 3109 3115 2978
3593 3528 3383 3504
3838 3873 3778 3735
4326 4310 4264 4304
4799 4810 4745 4800
5317 5241 5298 5370
5975 5968 5947 6029
6778 6775 6708 6662
7480 7374 7281 7576
8384 8535 8393 8492
9340 9382 9303 9209
10362 10308 10394 10281
11665 11839 11616 11488
12888 12683 12871 12748
14479 14309 14214 14413
15907 15970 15868 15980
17403 17283 17416 17421
18791 18652 19069 18804
20017 20363 20127 20151
21340 21195 21466 21466
22156 22185 22295 22100
22906 23077 23228 22871
23496 23464 23684 23225
24023 23849 23778 23788
24037 24041 24167 24000
24140 23992 24245 23986
23828 24064 23938 24236
23899 23666 23764 23586
23116 23110 23058 23191
21566 21550 21484 21462
17863 17931 17866 18190
12824 12802 12889 12969
6743 6802 6908 6796
2081 2202 2103 2039
272 222 244 271
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
