A = [
65383 68786 273162 62226 63554 58146 56063 57321 55985 51893 51679 51475 51159 50253 49411 48864 48458 48372 47813 47729 47370 46747 45940 45996 45889 53062 52770 53072 60360 60660 60357 60726 61318 61216 61414 61546 60779 59854 59924 58390 58361 57713 57601 57600 57630 57286 56055 56190 55352 54880 53923 53768 54095 53843 53226 52932 52880 52146 51485 50696 50363 50303 49883 49945 49011 49444 49250 48295 48141 47204 47424 46787 46444 45646 45676 45339 44820 44669 44067 44134 43299 43203 42883 42858 41811 41649 41383 41079 41115 39989 39725 40096 39455 39066 38700 38472 38231 37976 37646 37347 36678 37923 36813 36701 36116 35614 35739 36323 34497 34575 34458 34090 34056 33608 33461 32577 32074 32123 31780 31614 31501 31448 30766 30438 30200 30290 30087 29784 29011 28915 28398 28584 27921 27941 27660 27457 27303 26891 26653 26257 26205 25725 25470 25650 25498 25094 24554 24672 24306 24375 23745 23841 23570 23444 23023 22818 22286 22353 22188 22053 21859 21833 21156 20868 20596 20361 20714 20378 19647 19817 19282 19694 19110 18857 18839 18388 18281 17946 17879 17862 17423 17598 17133 17030 17031 16770 16419 16204 16407 16095 15826 15770 15479 15390 15157 14662 14839 14716 14564 14370 14213 13939 13865 13535 13220 13502 13152 12955 12700 12588 12899 12487 12163 11895 12068 11951 11527 11577 11554 11384 10970 11122 10825 10411 10463 10087 10096 10197 9962 9634 9675 9441 9329 9205 8985 9138 8748 8521 8631 8514 8506 8228 8167 7998 8161 7987 7774 7924 7644 7447 7277 7491 7207 7139 6993 6830 6867 6684 6471 6320 6597 6176 6186 6158 6027 5796 5855 5741 5890 5750 5626 5699 5771 5405 5284 5163 5023 5129 4977 5183 4937 5057 4878 4770 4779 4589 4406 4550 4260 4371 4154 4269 4023 4247 4151 3956 3897 3922 3919 3724 3616 3666 3619 3599 3491 3534 3536 3428 3238 3412 3392 3367 3155 3131 3285 3054 3140 2938 2834 2764 2726 2820 2673 2627 2495 2514 2503 2410 2386 2336 2323 2288 2280 2248 2290 2317 2182 2364 2223 2151 2223 2168 2197 2112 1976 1944 2003 1929 1844 1817 1855 2030 1766 1646 1818 1686 1996 1598 1771 1722 1662 1652 1622 1654 1556 1561 1548 1524 1409 1465 1449 1497 1420 1432 1383 1423 1454 1338 1266 1254 1281 1183 1139 1132 1212 1116 1040 1159 1151 1119 1112 1066 1143 1206 1064 1086 1083 986 959 958 985 970 920 946 975 976 841 883 865 864 844 884 789 858 919 801 914 881 767 786 745 755 728 674 709 720 684 695 742 811 766 629 711 635 762 641 697 685 712 569 511 531 546 541 565 498 497 479 514 471 487 517 488 514 484 462 458 449 424 426 438 396 373 416 652 523 556 436 508 501 813 475 457 531 396 354 370 343 334 337 367 345 344 341 347 415 374 366 411 342 388 398 348 375 403 351 329 358 350 327 369 343 342 395 309 349 315 345 337 324 280 316 284 320 292 306 335 339 270 291 286 283 288 319 341 261 268 252 282 306 330 331 257 263 301 378 271 341 315 342 346 315 317 424 361 576 502 756 534 408 517 444 478 465 465 531 296 348 309 355 318 357 331 415 374 187 182 196 195 220 240 243 287 272 298 387 312 328 282 250 329 251 258 269 223 201 259 270 226 218 220 229 270 269 250 216 220 221 231 210 174 195 179 191 203 164 156 170 174 164 160 184 150 156 158 171 187 164 158 178 146 189 165 180 161 144 187 187 173 175 186 203 210 165 156 166 164 138 139 147 179 160 154 119 131 105 116 122 124 133 139 110 113 135 101 140 131 106 119 137 101 91 126 76 122 132 119 99 101 101 110 106 100 114 116 111 130 111 112 113 116 107 128 110 96 113 105 128 102 96 116 140 120 125 114 106 107 88 112 94 88 89 84 87 93 77 105 99 89 87 80 76 104 90 87 57 98 59 92 111 101 100 106 87 82 108 83 115 89 100 114 123 112 132 188 261 293 168 192 145 156 145 136 181 117 126 187 168 165 153 155 155 142 116 102 118 125 121 78 92 93 85 92 109 76 110 105 119 97 138 133 120 118 149 99 140 104 155 127 110 97 109 153 122 141 127 167 179 75 73 87 90 70 95 74 84 95 91 77 90 105 71 66 79 135 95 79 70 192 74 72 56 72 67 49 65 61 62 58 72 77 71 62 66 56 77 74 64 66 106 88 92 74 70 80 76 89 79 84 99 109 96 78 91 57 61 64 98 72 71 72 74 64 46 49 50 59 35 48 50 48 40 42 28 33 43 34 43 49 36 35 48 67 80 46 56 53 56 54 54 45 53 52 48 61 65 48 50 52 57 44 35 48 46 56 39 69 43 66 80 64 66 41 33 43 42 41 54 45 48 39 40 46 34 48 41 67 63 69 61 77 47 53 40 30 33 52 49 38 29 33 30 37 38 27 20 37 30 42 34 45 55 31 33 30 28 43 47 39 29 35 33 39 28 37 27 26 34 31 26 52 26 28 54 33 24 58 23 29 28 28 42 26 30 27 27 26 23 14 24 27 43 36 26 37 41 36 43 24 39 32 27 18 32 26 33 30 23 35 31 30 27 46 38 35 28 31 24 40 33 38 23 21 20 30 24 19 22 40 44 33 42 32 30 39 31 19 30 14 22 31 28 37 26 32 28 47 46 29 29 36 31 18 22 21 24 30 19 44 25 32 38 26 37 34 44 34 57 49 44 45 43 32 39 30 30 34 24 40 30 42 23 32 38 27 26 20 31 16 30 22 45 35 21 19 37 22 19 30 20 16 31 26 22 28 31 26 31 16 20 23 28 24 27 30 18 20 32 26 21 20 22 17 18 19 17 13 22 26 20 24 28 10 15 26 12 24 27 13 20 16 26 32 17 15 29 24 15 29 20 16 14 23 30 12 14 18 24 15 15 15 18 15 15 15 19 20 28 29 19 15 18 27 18 38 24 28 28 26 39 26 28 39 32 40 20 49 38 30 43 27 23 45 20 24 36 28 42 37 27 21 34 32 17 15 20 28 12 32 24 17 34 20 11 25 24 17 16 20 18 27 27 29 22 23 23 35 35 21 16 25 23 33 22 10 17 27 20 20 29 15 34 21 12 9 7 9 9 10 10 13 16 11 9 14 7 27 13 13 12 11 14 9 16 21 16 12 11 12 10 24 19 9 17 16 13 11 13 10 15 4 17 9 9 9 11 10 9 14 15 17 26 16 11 20 10 15 8 10 11 11 11 24 19 17 29 10 19 18 16 10 15 9 7 9 12 7 18 9 10 17 13 10 14 5 8 9 5 6 4 10 9 6 7 7 5 6 5 8 5 7 7 7 10 5 5 8 6 8 7 15 13 5 10 5 8 5 9 11 3 13 5 13 4 6 8 12 9 4 4 8 5 10 11 8 7 14 8 9 9 8 5 6 6 8 10 14 5 10 4 10 7 6 15 10 7 7 6 10 5 9 9 7 10 12 7 6 9 11 10 6 7 3 8 8 2 9 9 16 12 16 6 12 10 9 12 18 10 16 12 12 20 5 18 5 11 12 14 9 10 9 14 10 8 15 18 5 8 8 15 3 3 7 8 13 6 2 5 6 2 4 6 5 4 6 3 4 4 9 15 3 7 15 7 7 6 2 5 5 3 5 3 6 2 9 8 3 6 2 4 2 3 3 3 6 5 2 4 3 1 2 2 1 2 2 5 2 2 3 3 7 6 3 3 4 4 1 4 3 3 3 1 1 3 5 6 2 5 7 3 5 2 5 1 4 4 1 1 4 3 5 5 2 3 4 2 1 5 3 2 1 3 8 2 6 2 3 1 2 4 4 5 4 6 4 4 2 5 3 2 1 2 2 2 5 2 6 8 2 5 5 2 1 2 1 2 1 1 4 3 3 3 3 6 2 2 3 2 1 5 0 1 7 4 4 1 7 8 2 3 3 4 1 2 2 5 3 3 2 3 2 5 2 3 2 8 2 4 4 3 10 4 0 3 1 2 4 2 8 2 4 5 5 6 2 3 2 4 5 3 1 7 4 3 2 1 1 6 1 1 0 2 0 4 1 3 2 5 5 4 9 3 2 1 4 3 6 6 2 7 5 4 3 3 1 7 4 49 105 136 112 100 67 81 66 16 0 5 2 4 2 6 2 2 8 0 1 4 4 3 5 2 3 2 3 1 5 2 2 3 1 3 5 7 8 2 6 10 3 5 3 2 5 3 3 3 1 4 2 0 0 2 1 4 3 6 2 3 6 2 1 2 3 3 6 2 0 0 4 5 6 5 3 1 2 3 2 1 5 3 10 3 1 1 5 1 4 2 4 4 2 1 2 4 5 2 3 7 6 2 5 4 2 5 1 1 5 0 3 1 1 3 2 0 4 5 1 2 0 1 1 0 0 1 6 1 2 2 0 3 3 4 0 2 3 2 1 0 2 1 3 4 1 2 2 1 3 3 1 4 1 3 3 3 0 8 5 3 3 3 2 5 0 2 5 3 0 2 1 3 2 1 6 9 3 0 0 3 1 2 3 2 5 4 3 1 2 4 2 5 0 0 1 3 1 0 7 1 2 1 2 2 2 4 0 5 0 1 1 0 0 2 0 2 3 2 4 0 1 1 4 3 3 3 0 2 1 2 4 2 3 3 1 3 2 2 1 1 3 4 0 3 2 2 3 2 3 4 0 4 2 2 4 1 1 3 2 1 4 2 2 3 1 2 0 1 1 1 1 0 2 4 2 3 1 0 0 7 5 2 3 0 1 4 5 6 3 3 2 5 2 0 1 5 5 4 0 1 2 3 2 4 2 0 0 3 8 0 0 4 3 3 3 4 1 4 6 5 2 3 
];
B = [
0 0 0
 27172 11560 15612
 12552 5301 7251
 44966 21102 23864
 29148 12572 16576
 15958 6506 9452
 43695 19996 23699
 34625 15022 19603
 19436 8462 10974
 58554 26164 32390
 56497 23825 32672
 10405 4559 5846
 166079 74628 91451
 22188 9691 12497
 6634 2857 3777
 39815 20589 19226
 12454 6139 6315
 3599 1713 1886
 42458 21439 21019
 3386 1628 1758
 3105 1355 1750
 668 255 413
 19 7 12
 667 294 373
 64263 33114 31149
 3744 1644 2100
 4512 2133 2379
 63880 31851 32029
 3285 1525 1760
 6744 3139 3605
 99556 48352 51204
 6303 2897 3406
 10668 4967 5701
 69840 35389 34451
 38182 19203 18979
 61997 31382 30615
 131378 66889 64489
 100824 49707 51117
 59264 29837 29427
 155013 80154 74859
 58576 28343 30233
 4124 1981 2143
 152730 78533 74197
 2108 1006 1102
 3682 1749 1933
 214588 113140 101448
 3880 1819 2061
 46516 22437 24079
 310844 170067 140777
 44954 21659 23295
 1 1 0
 2181806 1246254 935552
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
9 10 1 0
11 3 0 0
19 4 0 0
40 3 0 0
24 7 0 0
58 2 2 0
117 9 17 0
176 17 16 7
401 8 24 8
1743 16 30 30
3838 36 30 20
7707 43 46 40
16201 55 135 36
41151 71 200 65
101674 102 264 93
232206 124 209 203
357108 208 368 291
329004 321 515 413
206708 431 439 472
93060 615 558 571
27212 685 635 764
4605 769 742 717
1657 911 792 668
1389 883 850 914
1218 1335 820 2070
1197 2261 744 1644
2110 846 684 707
1358 773 768 719
1089 1843 789 799
949 921 934 784
1042 940 900 852
2700 1054 856 892
1175 1117 919 1029
1368 1471 1075 1069
1425 1252 1187 1329
1449 1368 1359 1269
1686 1442 1537 1514
1826 1813 1738 1696
1935 2000 1867 1905
2194 2174 2191 2131
2435 2493 2399 2422
2795 2811 2732 2640
3130 3110 3240 3123
3563 3515 3594 3527
3957 4082 3949 4014
4391 4624 4683 4973
5069 5130 5723 5114
5749 5729 5631 5638
6337 6365 6499 6335
7241 6978 6876 6989
7747 7695 7675 7561
8100 8157 8102 8234
8876 8644 8743 9181
9048 9117 8932 9097
9987 9780 10948 9987
9812 9989 10050 9996
10602 10709 11615 10693
12777 11423 11340 10901
12009 11391 11566 11485
13212 12030 11931 12724
13313 13771 12841 12828
12770 12868 13334 12984
14324 12451 13393 12783
11390 11281 10569 11285
9116 11256 10293 7883
4939 6518 4740 5305
2502 4463 2961 2888
2790 4139 3831 2296
2768 2320 1737 1842
1928 1608 3375 1210
814 876 1175 1196
1807 1046 1412 1204
70 49 53 26
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
