A = [
67059 145462 192125 89425 169601 120999 117428 120501 123190 117642 117416 121289 117395 113058 115309 114330 111976 114682 114063 112006 113097 109769 107515 105440 101506 105003 104973 102254 102918 104838 101927 99409 100705 96365 95815 96660 96064 94374 96090 96139 93776 94067 92626 89098 90068 88710 88101 87809 87428 86622 87053 85456 83517 82684 80109 79700 81464 79164 77520 78487 77816 75818 76121 73797 71599 72198 71374 70085 70161 69181 67606 67555 66053 64604 64716 63322 62154 62245 61784 60287 60341 59037 57495 57895 56151 55718 55392 54189 53665 53130 52271 51390 51554 50409 49215 49408 48153 47670 47417 46439 46238 45647 45114 44333 43647 42820 42512 42351 41332 40997 40715 40085 39487 39438 38855 38157 38165 37187 36626 36719 35907 35477 35163 34530 33886 33924 33298 32927 32730 32306 31790 31648 31087 30695 30792 30146 30251 29410 29162 28771 28460 27946 27554 27680 26908 26874 26536 25965 25987 25669 24977 24786 24550 24240 24096 23926 23701 23116 23095 22162 22351 22207 21901 21213 21404 20987 20805 20872 20584 20103 20164 19906 19509 19205 18894 18779 18599 18374 18146 18048 17940 17613 17789 17282 17281 17187 16944 16364 16487 16181 16198 16067 15805 15263 15390 15138 15278 14978 14796 14567 14878 14591 14384 14336 14036 13841 13667 13528 13473 13487 13467 13345 13123 12979 12864 12673 12606 12627 12405 12318 12317 12022 11913 11950 11849 11647 11585 11611 11538 11204 11393 10870 10910 10927 10756 10794 10844 10715 10604 10422 10552 10469 10092 10241 10108 9970 10058 9904 9803 9796 9541 9736 9493 9416 9333 9469 9361 9251 9110 9032 9030 8940 8877 8803 8846 8733 8679 8453 8583 8542 8323 8318 8344 8337 8153 8238 7925 8015 8002 7852 7803 7657 7562 7711 7794 7604 7539 7651 7443 7366 7420 7402 7215 7301 7230 7080 7031 6981 6995 6952 7010 6851 7006 6893 6674 6873 6720 6765 6506 6524 6465 6533 6320 6254 6266 6380 6192 6230 6206 6234 6184 6082 6142 6116 6076 6066 6029 5969 5807 5865 5647 5694 5712 5638 5824 5686 5744 5619 5578 5374 5498 5594 5354 5497 5313 5241 5432 5338 5271 5269 5239 5074 5056 5224 5172 5083 5070 5122 4988 4900 4976 4841 5032 4905 4645 4742 4717 4901 4839 4732 4646 4653 4717 4568 4690 4535 4730 4569 4542 4452 4506 4332 4527 4365 4336 4324 4263 4245 4348 4405 4254 4311 4281 4125 4234 4166 4082 4100 4224 4052 4158 4002 4068 3950 4011 4010 3919 4025 3920 3798 3789 3851 3794 3832 3703 3682 3740 3794 3657 3698 3580 3583 3635 3730 3539 3582 3538 3435 3493 3517 3412 3427 3402 3506 3490 3349 3345 3364 3351 3323 3274 3321 3326 3191 3333 3214 3215 3100 3172 3173 3186 3133 3133 3095 3112 3048 3061 3121 3044 3117 2976 3078 2952 2839 2853 2971 2782 2976 2867 2851 2861 2808 2690 2880 2817 2852 2740 2790 2739 2809 2682 2747 2655 2649 2726 2689 2650 2651 2545 2648 2545 2635 2622 2553 2553 2476 2448 2554 2558 2521 2431 2485 2432 2372 2489 2412 2461 2368 2371 2390 2322 2362 2403 2322 2313 2376 2409 2234 2293 2210 2234 2319 2269 2253 2193 2199 2204 2270 2171 2159 2191 2152 2091 2199 2025 2086 2055 2206 2100 2061 2001 2018 2058 2055 2016 2067 1994 2054 1962 1987 1975 1937 2011 2005 1943 1906 1895 1886 1905 1914 1917 1854 1885 1971 1864 1903 1828 1758 1785 1777 1714 1718 1749 1766 1790 1785 1665 1711 1696 1693 1697 1676 1688 1675 1674 1647 1653 1631 1662 1614 1597 1630 1561 1566 1634 1603 1571 1583 1604 1578 1605 1570 1582 1554 1544 1520 1505 1522 1539 1555 1606 1486 1427 1477 1462 1386 1390 1432 1418 1462 1466 1420 1452 1431 1386 1384 1353 1407 1377 1398 1273 1299 1378 1294 1421 1343 1315 1302 1271 1320 1333 1301 1282 1210 1273 1252 1228 1317 1282 1189 1243 1245 1199 1267 1204 1231 1246 1192 1238 1262 1185 1202 1174 1165 1196 1187 1160 1179 1166 1183 1097 1121 1204 1205 1147 1059 1135 1043 1073 1084 1073 1093 1057 1094 1061 1015 1065 1002 1043 1047 1027 979 1035 1014 976 1052 1036 1070 1029 1056 1028 1006 1000 967 1030 1008 1015 989 956 968 948 1006 900 908 962 962 899 891 910 913 887 890 862 857 878 874 932 897 914 946 895 846 834 869 871 862 899 811 846 908 797 802 839 843 807 818 804 807 819 766 777 801 756 696 792 757 733 734 758 735 740 813 732 776 725 718 716 695 761 748 730 759 723 728 743 726 704 731 713 696 681 698 687 634 650 657 659 645 625 650 653 657 657 647 673 640 619 617 620 592 620 613 634 640 656 642 607 642 620 652 642 579 635 627 583 580 577 604 618 610 608 576 608 558 537 594 570 565 604 565 551 574 580 567 546 604 569 535 559 527 571 525 575 543 528 554 519 522 551 565 509 508 549 540 532 494 517 490 524 531 529 507 527 502 485 471 493 507 481 557 475 471 542 501 481 516 471 491 447 520 469 433 459 421 443 410 459 439 488 424 471 416 468 436 435 407 405 426 411 484 438 426 458 426 427 440 419 410 402 430 429 403 433 386 403 452 396 397 381 355 412 419 406 375 402 423 381 412 388 394 386 415 404 370 361 371 370 360 351 356 368 361 315 355 378 326 374 341 315 370 361 325 326 312 349 342 304 340 300 347 328 342 307 378 347 325 326 329 350 332 331 327 318 334 291 276 295 318 299 278 314 300 276 308 313 338 289 264 300 280 295 260 304 273 264 257 259 299 286 284 253 309 256 313 274 272 323 265 266 278 249 263 267 243 269 279 312 247 263 247 263 253 251 259 256 260 248 247 248 273 258 253 228 244 250 232 248 240 266 235 246 247 255 241 222 211 229 223 236 248 220 224 217 219 215 229 215 210 250 208 206 223 218 214 177 224 221 204 213 243 226 187 205 229 216 220 216 209 208 175 167 222 193 206 189 212 219 153 210 187 187 172 179 183 170 185 211 180 191 183 176 175 204 152 188 185 186 199 171 162 155 157 177 181 172 205 181 192 167 165 183 158 157 162 175 175 132 139 156 162 169 167 178 157 174 175 164 161 164 182 148 153 145 161 163 144 146 147 160 140 156 152 171 157 150 153 163 159 158 148 155 143 152 150 131 159 136 146 126 146 149 140 130 149 150 154 105 129 138 153 142 129 124 108 155 135 163 147 128 121 140 126 118 134 123 116 123 133 140 112 119 127 114 109 142 108 122 98 131 119 118 115 117 122 107 107 119 108 135 109 116 104 103 97 129 115 99 107 112 115 100 127 115 113 119 103 116 104 92 114 93 101 114 101 96 95 105 106 119 112 109 97 97 100 95 93 118 94 100 89 120 115 115 95 100 90 110 99 86 96 114 91 75 92 76 98 91 104 81 71 83 90 87 86 100 98 84 81 86 88 93 94 94 98 82 97 75 105 84 99 99 79 104 82 96 75 78 86 85 92 88 87 79 69 88 79 96 74 88 87 79 82 80 86 75 85 65 85 68 76 68 84 75 67 60 80 70 80 67 78 71 77 65 77 66 65 78 68 62 73 76 86 67 54 77 69 48 90 80 67 73 63 46 75 72 50 69 53 60 59 62 67 81 71 67 69 60 70 78 62 63 62 62 64 60 49 50 49 68 69 66 64 47 59 65 51 62 74 55 55 58 55 49 45 68 54 59 57 63 65 58 61 57 63 65 58 54 43 57 74 45 54 52 56 51 59 61 50 53 47 73 54 54 69 52 50 57 50 67 62 56 55 65 46 59 73 41 52 62 57 55 53 41 54 50 47 54 58 46 45 45 71 40 56 47 29 46 52 51 55 49 43 54 43 43 44 41 52 51 47 32 50 31 46 36 47 46 40 39 48 52 33 43 38 35 39 35 41 26 38 37 35 53 32 44 28 42 45 31 35 43 50 33 38 48 43 34 26 45 41 34 44 35 32 37 48 41 40 39 39 45 33 47 45 43 43 60 36 36 34 34 44 32 42 38 55 30 42 29 36 32 38 22 36 37 43 26 30 29 31 42 34 41 31 32 35 28 37 33 44 31 34 31 29 30 41 43 41 45 38 29 35 28 44 32 35 36 27 26 39 30 31 34 39 33 25 38 25 30 29 22 23 28 26 27 32 27 25 30 32 41 46 29 29 22 18 26 27 30 19 23 33 22 40 31 25 33 21 28 28 26 25 25 40 33 30 39 25 32 32 34 37 28 29 28 18 28 31 23 33 37 23 33 16 27 27 28 37 19 18 17 28 22 25 35 33 25 22 23 27 24 31 24 24 21 27 25 28 24 21 14 35 33 22 29 24 29 31 20 29 23 16 26 17 21 17 18 23 18 26 17 18 22 18 20 28 25 28 17 22 25 28 22 25 22 19 13 18 17 23 22 16 25 12 27 29 25 36 22 17 16 11 15 21 20 26 19 23 24 16 23 15 15 19 14 17 26 20 24 17 14 12 12 18 14 19 25 19 13 12 16 19 14 10 12 23 19 14 13 15 17 15 11 17 17 12 12 18 12 23 14 12 15 21 11 14 13 25 14 15 14 16 16 20 7 19 11 11 19 11 19 23 16 18 14 13 17 18 10 18 10 10 19 17 24 8 13 10 8 19 19 16 19 23 19 29 17 19 14 16 14 16 14 13 15 15 17 13 12 9 18 15 17 8 17 12 7 13 15 12 10 10 14 13 8 10 16 13 14 10 13 14 16 12 9 16 10 15 6 14 12 9 9 14 14 15 14 17 15 11 13 13 11 20 16 8 17 11 13 16 21 16 9 5 11 13 19 15 11 9 14 16 10 8 16 12 13 17 8 11 9 6 23 14 14 12 12 6 13 9 4 10 9 7 12 12 9 12 5 8 14 12 8 13 15 9 11 15 6 10 16 12 10 12 12 10 13 5 13 11 11 11 10 10 7 9 13 9 19 17 15 7 11 12 11 12 11 7 7 6 5 11 15 7 6 8 11 6 13 9 10 11 8 9 15 13 5 11 5 12 11 10 13 15 7 15 11 11 14 8 
];
B = [
0 0 0
 29604 11565 18039
 14859 5662 9197
 58275 28391 29884
 12698 4775 7923
 13190 5212 7978
 18997 7564 11433
 23547 10913 12634
 18202 7296 10906
 50500 26971 23529
 13221 5560 7661
 15393 6610 8783
 17005 7723 9282
 31859 15564 16295
 15737 6945 8792
 53199 29718 23481
 15704 7769 7935
 17352 8768 8584
 18431 9475 8956
 36560 19135 17425
 18936 10384 8552
 60380 34333 26047
 28296 15452 12844
 22483 12290 10193
 52298 27404 24894
 76608 43778 32830
 11263 5375 5888
 259817 152566 107251
 4005 2733 1272
 9054 5345 3709
 6599 4242 2357
 13048 8819 4229
 4308 2441 1867
 47873 32109 15764
 3602 2249 1353
 8690 5295 3395
 6080 3912 2168
 11809 7922 3887
 1471 692 779
 55959 37494 18465
 10 9 1
 107 79 28
 982 558 424
 8585 5551 3034
 980 624 356
 822 497 325
 1693 922 771
 3634 2006 1628
 95287 64568 30719
 99 72 27
 1098 716 382
 882 548 334
 1252 776 476
 4892 2885 2007
 96304 67045 29259
 1849 1331 518
 1624 1102 522
 2494 1910 584
 49848 35267 14581
 32291 23546 8745
 5423241 4410528 1012713
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
38 53 2 0
27 12 0 0
51 19 1 0
50 36 0 0
32 38 3 1
120 49 1 4
1590 97 28 25
10322 128 118 102
50659 154 240 197
154146 299 459 447
315189 400 757 700
420747 678 1218 1259
493323 1015 1797 1792
595743 1556 2744 2717
649873 2469 3908 3843
507547 3798 4814 4883
318630 5252 5986 6038
161485 5653 6851 7041
63503 5749 7539 7416
27276 7872 10323 10463
20359 11047 12739 13067
17486 12530 14482 14398
21039 13986 16725 16588
21505 16333 18049 17862
23238 17171 19261 19090
23124 18301 19764 19664
22929 18330 19856 19538
21909 17956 18993 18999
20427 16806 17592 17600
18223 15560 15809 16049
16146 14126 13941 13948
14413 12933 12534 12503
12927 11568 11104 11200
11781 10729 10385 10185
10890 10474 9694 9741
10587 10013 9235 9447
10318 9701 9114 9080
9535 9221 8666 8817
8683 8707 8390 8160
8274 8430 7823 7712
7858 7867 7251 7348
7115 7207 6807 6956
6581 6356 6348 6353
5942 5703 5590 5718
5194 5105 5275 5244
4645 4596 4574 4613
4030 4095 4114 4087
3606 3562 3684 3533
3106 3100 3046 3013
2481 2597 2585 2690
2085 2071 2076 2125
1595 1603 1632 1611
1136 1162 1103 1174
756 764 814 777
541 521 494 498
267 272 281 255
161 136 136 144
53 53 61 62
14 19 17 17
4 4 5 3
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
