A = [
56614 54466 551012 50864 41368 39583 40693 25236 25642 24421 24263 23947 23132 22742 22483 22023 21645 21340 21090 20972 20496 18951 17869 16552 14807 12599 11657 10208 7432 7322 7547 7628 7300 7642 8232 8082 8682 8166 8332 7914 7748 7494 7574 7261 7636 7149 7315 6877 6958 6839 6651 6533 6735 6320 6950 6366 6309 6088 6178 6086 6158 6066 5563 5438 5701 5656 5546 5293 5364 5196 5415 5277 5393 5584 5606 5544 5671 5612 5541 5697 5423 5738 5665 5815 5850 5667 6017 5819 5957 5822 5881 5882 6060 6102 6152 6250 6249 6431 6502 6898 6985 7192 7476 7960 8328 8484 8671 9734 8831 8745 8597 8499 8414 8361 8642 8539 8577 8419 8418 8651 8572 8701 8301 8164 8478 8431 8752 9132 9256 9752 9774 9641 9956 9823 10052 9719 9328 9983 9557 9984 9057 9378 9612 10371 9677 9467 9124 8595 8404 8520 7662 6971 6442 6123 6537 5996 5937 5929 5761 5639 5729 5351 5375 5472 5076 4794 4761 4581 4465 4383 4591 4482 4504 4579 4819 4585 5342 5453 5687 5844 5724 6182 6003 6188 6571 5761 5552 5243 5377 5186 5222 5441 5366 5904 5904 5381 5631 5999 6207 6322 6664 6583 6982 7012 7120 6934 7189 7009 6944 6883 6883 6286 6520 6688 6388 7021 6602 6923 6602 6657 6532 6255 6359 6697 6503 6855 6187 6824 6545 7431 7265 6724 6871 6947 6774 6780 5733 5940 5856 5848 5758 5805 5724 6041 5618 5718 5300 5787 5628 5435 5164 5109 5178 5139 5275 5240 4857 5132 5340 5227 5067 5070 4852 4513 4348 4564 4468 4400 4527 4337 4461 4667 4623 4640 4627 4836 4795 4932 5725 5310 5214 5033 4915 4884 4546 4860 4574 4605 4744 4520 4721 4702 4584 4596 4535 4726 4325 4558 4525 4324 4504 4491 3911 3771 3783 3848 3838 3684 3520 3355 3486 3715 3699 3711 3835 3801 3743 3746 4020 3716 3962 3999 4132 3962 4397 4381 4373 4164 4245 3992 4292 4530 4130 4538 4347 4653 4674 4631 4880 5128 4957 5397 5183 5206 5260 5317 5352 5143 5394 5222 4959 5751 5189 5433 4784 4850 4925 4778 4861 5200 4471 4606 4262 4176 4126 4115 4239 4195 4291 4491 4022 4474 4431 4715 4763 4820 4879 4852 5000 5133 4513 4606 4665 4714 4752 4870 4806 4765 4785 4737 4324 4530 4502 4480 4341 4426 4892 5043 4726 5074 4417 4187 4189 4363 4170 4416 4251 4480 4253 4116 4038 4323 4590 4120 4340 4169 4280 4266 4361 4141 3602 3372 3283 3229 3373 3100 3317 3286 3237 3371 3465 3298 3269 3310 3270 3272 3422 3246 3175 3122 3201 3259 3240 3039 3119 3046 3153 2996 3126 2833 2943 2879 2809 3016 3142 3096 3015 3108 3108 3189 3422 3449 3352 3545 3320 3150 3189 3125 2819 3104 2997 2952 2985 2939 3274 3186 3191 2953 2984 3203 3130 3117 3215 3040 3090 3168 3237 3188 3238 3292 3305 3166 3367 3444 3505 3499 3662 3674 3764 4027 4102 4049 4335 4452 4709 4848 5003 5015 5090 5349 5079 4855 4933 5082 5264 4781 4757 4750 4830 5099 4719 4592 4559 4678 4668 4569 4607 4374 4840 5254 4846 4675 4439 4640 4300 3424 3109 2957 2797 2833 2991 2640 2646 2589 2654 2604 2569 2522 2374 2367 2370 2343 2342 2357 2282 2264 2268 2342 2437 2556 2677 2409 2686 2261 2204 2169 2063 2043 2027 2088 2096 2111 2219 2073 2103 2009 1971 2122 2007 2044 1960 1907 1919 1975 2055 1925 2050 2021 1798 1883 1878 1906 1857 1950 1998 1916 1934 2107 2015 2286 2265 2574 2763 2861 2990 3033 2983 3489 2593 2958 2832 2933 2581 2620 2696 2589 2641 2936 2254 2757 2615 2723 2567 2525 2527 2419 2477 2858 2203 2657 2641 2643 1806 1609 1170 1117 1042 980 920 962 992 897 916 848 838 870 844 796 851 786 812 752 726 761 725 710 658 674 718 692 644 640 690 601 615 641 598 614 548 543 519 543 524 546 501 519 531 488 482 503 486 501 484 465 455 475 480 445 421 390 384 425 437 392 453 415 407 370 390 418 376 412 405 412 395 383 385 345 323 347 360 374 320 321 324 288 316 292 312 248 272 218 255 228 229 202 237 211 214 220 215 196 172 194 200 207 192 178 185 192 171 160 169 157 181 179 174 156 159 167 162 169 132 146 129 169 137 172 149 148 132 127 128 139 116 101 130 113 107 106 105 102 101 106 85 86 94 97 77 96 99 103 86 91 68 82 70 69 72 89 87 61 64 78 80 78 70 63 75 63 76 62 75 73 73 80 70 86 69 64 80 63 80 80 61 82 63 105 70 57 62 68 56 69 56 71 61 52 78 45 50 62 50 53 51 48 54 42 45 38 39 45 38 39 41 53 39 49 47 48 33 40 32 35 32 33 36 21 33 39 33 35 21 36 47 37 29 28 44 19 25 39 29 34 34 38 34 33 35 27 24 30 27 25 20 21 20 23 28 16 23 23 26 26 29 23 26 27 18 21 25 21 18 20 17 26 28 32 22 25 19 27 21 16 22 14 14 26 17 25 30 25 21 27 15 27 22 18 20 18 29 17 16 16 23 17 23 15 16 20 14 16 9 8 11 14 12 16 10 9 11 12 13 14 12 23 18 13 11 12 14 16 11 18 12 18 16 14 9 17 9 9 13 14 13 15 8 15 9 10 13 13 12 15 9 6 16 13 9 9 15 11 8 11 15 9 16 9 10 14 7 7 8 18 14 13 12 11 9 7 11 8 11 18 12 13 14 10 24 8 16 16 13 8 11 13 10 10 8 7 9 6 6 11 14 10 3 9 6 9 4 10 11 5 10 10 8 10 14 6 13 13 11 6 14 10 7 7 5 9 8 4 7 11 5 5 9 7 11 4 11 25 17 11 17 14 20 11 13 7 9 11 12 8 10 5 8 11 11 13 6 5 7 13 3 10 6 6 7 7 9 4 7 6 11 6 7 2 6 6 9 7 4 6 4 5 11 3 10 5 10 11 8 10 5 12 8 1 3 10 9 8 5 7 4 1 5 4 6 11 4 3 4 7 8 4 4 7 14 9 9 4 7 4 9 7 4 6 4 9 7 6 2 5 5 3 5 4 6 8 10 4 6 13 6 3 8 4 7 5 8 2 2 3 7 2 4 4 1 4 1 4 6 2 11 12 3 5 7 5 5 6 5 5 5 3 7 4 5 3 4 3 6 7 6 6 4 1 3 2 2 3 3 9 7 7 12 14 9 13 11 7 16 7 9 6 8 12 7 11 12 16 18 12 9 13 14 8 10 9 7 8 12 10 11 5 7 11 9 9 6 8 9 11 11 8 12 8 3 7 4 3 3 7 2 11 10 6 5 4 6 4 1 6 6 8 8 12 1 5 5 6 0 3 2 1 2 2 2 3 3 0 6 4 3 3 5 2 3 3 3 0 5 4 5 2 2 3 5 6 1 7 4 4 3 2 2 3 4 5 5 7 2 5 4 4 4 6 3 6 4 9 5 4 5 7 7 2 11 6 7 2 4 8 14 5 4 7 5 3 5 8 4 6 6 1 3 10 7 0 6 9 3 3 11 5 4 7 7 8 1 3 3 4 8 7 7 4 5 5 9 9 4 9 6 12 9 7 5 2 6 5 5 7 5 5 14 8 16 15 17 14 13 16 6 3 3 6 9 4 7 1 5 2 5 1 2 1 0 4 4 4 2 3 1 1 4 4 0 3 0 2 1 3 1 3 1 3 3 2 3 3 3 2 1 5 3 5 3 1 0 3 2 2 3 1 3 2 4 2 0 1 2 3 2 0 1 3 1 4 3 4 2 2 3 1 3 1 3 3 3 0 2 4 2 0 2 1 1 1 2 4 2 2 0 1 2 0 4 1 0 3 1 1 1 2 3 5 3 1 2 1 0 0 1 3 1 1 1 3 2 1 1 3 1 1 1 1 2 4 1 2 1 2 4 0 4 4 9 2 3 4 0 4 2 5 6 3 5 4 4 4 2 2 3 4 3 1 1 4 2 6 2 3 7 1 4 4 4 3 4 1 6 2 0 3 2 2 5 2 1 4 4 4 2 0 5 3 4 3 2 3 8 3 3 1 6 4 3 3 7 3 8 3 4 4 4 4 5 7 1 3 6 5 6 6 3 8 1 4 4 0 3 1 6 1 4 3 2 1 0 4 3 3 4 7 7 9 3 1 5 6 4 3 4 5 1 6 6 5 7 4 3 5 3 5 3 6 4 2 1 2 4 4 3 0 6 3 3 3 3 4 0 2 3 6 4 4 1 3 1 1 0 0 1 1 3 1 4 8 2 6 2 7 18 2 3 5 0 4 2 3 3 6 1 0 0 3 2 3 2 3 2 1 2 3 3 2 1 1 0 1 2 2 2 2 5 3 1 1 1 1 2 1 2 1 0 2 0 3 1 1 1 1 2 2 0 2 1 0 1 1 0 3 0 0 0 1 1 0 0 1 1 0 2 2 2 0 5 1 3 0 3 0 0 0 0 0 1 0 2 1 2 1 6 4 7 4 12 4 7 11 2 0 3 1 2 0 1 0 1 0 3 0 1 2 1 2 2 0 3 1 6 4 6 1 3 3 1 3 1 2 2 1 1 2 2 3 0 0 0 1 1 0 1 0 1 1 0 0 0 2 0 1 0 0 2 3 0 0 0 0 1 0 1 0 0 0 2 0 2 0 1 1 1 3 1 1 1 2 1 1 1 1 1 1 0 2 1 2 2 2 1 2 1 2 0 0 0 1 2 0 0 2 1 0 0 0 2 1 1 0 0 0 1 1 2 1 0 1 0 1 1 0 3 0 3 0 0 0 2 1 0 0 1 0 2 0 3 0 2 0 1 0 1 0 0 0 1 1 1 0 0 0 2 1 0 1 2 0 0 2 3 0 2 0 0 2 1 0 1 0 2 1 3 0 2 0 0 1 0 1 1 1 1 1 2 1 1 0 1 0 0 1 0 0 1 0 2 0 
];
B = [
0 0 0
 57740 44336 13404
 62547 49792 12755
 45631 34833 10798
 53841 42815 11026
 49154 36751 12403
 47594 37631 9963
 50305 37873 12432
 47951 35882 12069
 38047 30719 7328
 45878 30148 15730
 16543 12722 3821
 13841 11022 2819
 8731 7338 1393
 6250 5259 991
 7337 5815 1522
 5241 3862 1379
 8885 6823 2062
 8962 7074 1888
 11032 8442 2590
 13989 11366 2623
 10462 7878 2584
 11303 8453 2850
 11019 8607 2412
 9409 7592 1817
 9253 7642 1611
 15394 11574 3820
 5353 4273 1080
 5455 4425 1030
 4143 3324 819
 3038 2409 629
 4804 3870 934
 3052 2528 524
 4221 3469 752
 3531 2769 762
 2603 2213 390
 3150 2591 559
 2678 2330 348
 5557 4906 651
 2447 2172 275
 1657 1505 152
 2318 2053 265
 1731 1613 118
 2008 1818 190
 2054 1889 165
 1375 1276 99
 2204 1985 219
 1755 1609 146
 1341 1230 111
 2701 2497 204
 1411 1308 103
 3488 3155 333
 2037 1918 119
 956 878 78
 2659 2438 221
 1225 1149 76
 2326 2163 163
 1488 1413 75
 1129 1059 70
 2979 2812 167
 1497930 1460422 37508
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 3 0 0
0 0 0 0
0 0 0 0
0 1 0 0
2 0 0 0
3 5 0 0
1 1 0 0
1 0 0 0
2 3 0 0
10 6 0 0
19 5 1 1
38 9 3 0
81 6 6 4
111 23 15 14
152 42 19 18
237 52 43 37
640 81 50 58
4114 76 93 88
51012 113 118 144
398627 108 171 191
623519 210 236 241
166081 274 331 339
12581 379 390 410
2054 454 534 507
1323 628 611 546
1814 680 686 698
1845 953 813 789
1734 1021 892 955
2036 1106 1144 1060
2072 1235 1201 1241
2875 1488 1405 1280
4640 1495 1459 1450
5683 1569 1713 1662
5482 1732 3059 2510
2033 1660 1882 1831
2003 1828 1848 1889
2110 1932 1987 2157
2300 2081 2078 2110
2203 2114 2279 2184
2178 2242 2224 2398
2369 2348 2322 2318
2512 2419 2530 2359
2312 2462 2428 2438
2387 2339 2560 2462
2442 2398 2344 2320
2412 2578 2741 2703
5666 6198 2379 2397
3518 3036 2231 2221
2291 2144 2063 2076
1850 1971 2043 1989
2364 2362 1662 1695
1640 1670 1735 1708
1347 1449 1354 1410
1500 1610 2311 2302
3585 3322 8340 5797
1266 1182 978 1019
1158 1112 1201 1110
2414 2606 1169 1288
12515 12580 2460 2058
1341 1412 2702 2636
1806 1972 2021 2347
8326 8525 1663 2013
3829 4134 17585 16324
6044 6914 6883 6635
11129 13269 13287 12878
10246 10248 9525 10390
13140 15004 21310 20666
7241 7090 19857 20979
16524 15558 14035 14291
11692 11190 6315 5566
3401 3238 14314 11525
10081 9872 794 760
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
