A = [
507598 682854 10581354 393796 394289 382191 375242 375688 359460 351582 349060 336303 341489 333451 328675 331746 321338 321390 322936 313266 310591 310251 306348 307195 303697 304832 307380 303392 304154 300401 300550 302228 297121 294092 295833 298423 293512 291248 293039 294040 291636 294168 296222 295209 296666 298365 292901 295731 293355 290309 290967 282814 287659 285853 281319 282929 280925 282128 279016 274248 274788 272791 268887 266362 264643 262751 259364 257170 255247 252700 251351 252333 250142 249331 249194 249423 247796 245597 242676 239954 238426 236668 235074 232189 231183 228534 222876 215332 211535 210476 208171 205958 206100 204024 202538 201182 199852 198250 197424 196199 194338 194604 192587 192009 190060 189408 189484 186422 185766 184338 183475 183545 182554 180482 179832 179133 178326 177526 175772 174278 173782 171953 171367 170295 169160 167485 166701 164889 163577 162946 161561 159763 157949 158070 156669 154866 153910 153193 151993 150973 148878 148601 146914 145142 144056 143249 142004 141016 138759 137667 136232 135427 133494 132283 131190 129946 128827 127092 126417 125177 124017 122358 121762 119990 118608 117431 116788 115854 113768 113139 111322 110646 109672 107975 107878 106167 105328 104393 103339 101928 100924 99730 99070 97044 96501 95803 94396 93997 93222 91693 91230 90083 88870 87525 86768 86250 85324 84447 83559 82164 81936 80842 79618 78971 77661 77440 76586 75071 75069 73091 72784 72138 70388 70043 69601 68353 67949 66786 65976 65224 64441 63961 63739 62292 60816 59933 58953 57887 56408 55421 54908 53957 53639 52832 51971 51321 50367 49625 49229 48100 47854 46819 46298 45624 45004 44333 43896 43028 42483 41878 41253 40701 39910 39516 38963 38668 38266 37423 36720 36540 35782 35431 34614 33823 33492 33048 32705 32360 31765 31451 30839 30186 30020 29870 29239 28619 28180 28213 27360 27091 26571 26063 25615 25339 25059 24670 24147 23952 23286 22905 22552 22477 22286 21835 21409 21053 20759 20445 19862 19807 19749 19132 19000 18707 18288 18118 17809 17534 17137 16855 16828 16211 16397 15786 15605 15561 15131 14995 14731 14215 14199 13942 13905 13339 13308 13126 12993 12695 12371 12332 11989 11700 11801 11429 11189 11174 10761 10771 10318 10388 10099 10111 9762 9592 9394 9369 9100 9047 8955 8593 8536 8489 8491 8183 7998 7858 7785 7553 7545 7477 7207 7143 6910 7043 6914 6549 6519 6431 6475 6185 6146 5923 5927 5951 5822 5627 5526 5462 5447 5315 5194 5178 4903 5097 4788 4727 4577 4489 4477 4391 4349 4162 4141 4156 4033 3942 3950 3787 3863 3683 3711 3519 3512 3513 3557 3285 3344 3219 3113 3061 3009 2990 2963 2898 2875 2799 2819 2670 2619 2625 2611 2553 2474 2481 2423 2409 2363 2237 2161 2198 2159 2143 2147 2148 2077 2019 1895 2015 1936 1806 1897 1781 1791 1720 1877 1637 1699 1595 1647 1596 1579 1543 1464 1529 1504 1427 1460 1426 1270 1369 1358 1288 1365 1321 1233 1266 1240 1213 1159 1140 1167 1205 1127 1013 1077 1064 1026 1026 1023 985 981 953 933 937 923 869 914 870 864 833 857 849 807 781 807 741 765 808 772 742 778 720 693 663 691 648 649 688 655 635 670 613 572 560 567 539 592 562 559 545 547 538 542 517 548 497 542 504 495 478 503 456 443 472 485 444 471 454 462 432 435 417 455 415 412 405 390 396 403 410 406 403 389 362 403 347 401 353 372 356 370 351 350 355 346 309 318 347 355 314 375 344 300 367 327 316 301 325 298 296 304 300 301 281 305 279 265 269 273 272 268 291 274 271 282 263 287 247 277 239 248 248 273 236 280 225 225 256 237 233 255 252 237 235 203 209 225 209 212 190 212 230 213 209 225 218 210 212 189 207 199 223 204 193 187 191 203 192 194 200 199 195 178 182 179 174 177 167 213 184 189 202 179 192 199 176 166 188 181 217 210 181 178 175 173 178 177 171 191 182 179 179 176 201 171 202 193 167 179 176 160 199 171 203 195 181 200 151 156 181 145 181 173 179 168 172 183 169 165 160 152 164 163 137 155 152 144 140 150 142 147 161 144 139 166 136 144 152 152 145 117 139 131 135 132 123 130 131 135 136 145 136 141 151 149 126 142 133 118 135 121 131 143 139 143 134 113 135 139 120 157 146 140 145 143 148 147 144 139 157 138 140 120 163 152 139 129 127 146 134 103 144 146 119 122 139 142 125 112 133 114 107 133 121 114 121 112 108 102 94 116 124 103 119 99 119 103 109 95 119 108 115 119 102 90 104 102 107 106 102 106 112 92 109 104 80 81 96 118 84 107 93 111 107 94 115 70 104 87 103 96 84 106 86 91 98 86 85 86 82 84 103 83 91 88 100 84 94 97 108 88 95 101 89 92 111 98 103 100 87 110 116 110 83 107 102 109 114 77 102 86 99 92 90 106 89 100 85 82 92 87 91 83 79 79 90 94 72 96 83 94 96 90 82 92 117 75 78 95 78 81 89 98 64 97 70 73 80 87 96 92 75 79 58 94 76 88 81 68 95 96 88 100 72 95 85 85 94 86 86 106 88 97 95 103 102 106 93 89 81 77 100 90 78 103 81 86 97 93 85 97 88 97 99 81 69 86 76 82 80 74 80 92 108 87 79 78 91 90 94 103 90 69 99 97 89 96 102 86 78 75 86 87 68 75 82 75 83 92 69 67 64 88 77 77 76 74 79 79 65 53 79 73 74 88 69 86 72 67 71 74 80 77 72 73 87 60 84 76 65 82 62 71 65 49 62 58 66 66 73 86 74 72 57 58 56 76 68 54 69 57 49 67 75 50 51 59 63 53 53 40 49 50 35 59 67 41 55 38 51 46 43 48 41 45 46 48 34 54 49 54 56 47 62 51 55 47 68 64 66 64 87 58 72 66 75 75 57 71 49 62 55 66 53 53 66 55 47 65 54 77 50 56 66 60 50 60 41 46 50 30 38 51 48 32 35 54 48 36 33 47 40 46 44 41 63 51 68 125 96 147 146 145 156 153 163 171 135 182 132 103 126 115 93 105 131 110 114 118 138 109 140 121 119 147 147 134 199 160 129 133 130 121 122 104 116 119 111 116 99 113 99 105 101 101 85 75 74 76 97 64 54 42 73 153 36 50 28 26 99 28 33 32 35 47 30 37 38 34 38 39 27 34 46 33 52 47 49 62 51 66 52 59 82 73 64 54 91 76 97 76 73 90 94 94 81 89 103 110 118 132 141 153 131 157 172 172 189 216 225 177 196 204 187 181 194 178 191 211 201 152 115 102 76 64 73 59 55 39 24 39 27 25 31 24 29 20 20 22 39 39 42 25 28 33 36 34 26 37 42 40 25 26 34 30 25 28 28 40 35 35 28 46 40 32 46 38 35 30 36 32 34 27 34 27 40 41 30 37 39 35 46 30 28 34 34 24 27 26 29 24 29 25 38 47 29 32 43 39 41 43 16 32 31 33 29 26 37 35 33 30 28 36 32 28 32 30 32 31 28 19 32 25 32 27 29 30 14 21 24 29 21 35 23 28 18 22 21 19 23 19 29 34 28 37 25 36 25 27 39 32 32 28 23 27 22 34 28 18 27 23 26 26 23 30 29 32 25 37 23 22 27 29 30 30 20 37 40 15 15 23 30 27 64 59 38 33 21 33 38 40 35 31 38 43 26 44 45 40 40 47 48 47 42 34 36 22 24 17 17 17 33 26 32 31 27 22 28 34 38 34 33 43 40 50 39 36 35 37 27 29 37 29 35 35 36 39 43 29 46 30 51 31 37 32 39 48 43 34 47 37 32 29 46 47 39 41 41 34 39 30 22 31 24 27 28 30 20 21 26 29 21 18 29 23 24 32 18 29 23 24 25 30 23 26 26 38 34 28 29 20 28 29 30 28 24 34 33 25 33 30 25 40 21 30 28 29 47 33 39 38 37 43 32 32 37 42 37 41 38 25 34 36 43 29 46 38 41 54 46 41 52 46 74 56 61 71 41 52 32 49 42 32 34 26 26 30 32 31 19 22 35 27 30 23 31 32 33 30 35 45 33 35 35 35 32 27 23 23 23 20 26 25 19 26 24 22 20 32 18 12 11 18 8 22 21 20 16 19 9 30 19 28 17 25 17 25 34 26 19 21 23 26 16 18 20 18 15 17 14 21 19 21 14 17 19 20 15 11 13 20 21 20 22 18 18 16 18 11 11 21 22 23 17 14 15 34 19 13 25 26 19 21 13 26 19 17 23 19 17 26 24 20 17 23 13 14 16 15 18 17 12 15 14 15 17 18 14 21 28 29 24 26 19 25 18 22 24 12 16 9 17 20 18 19 20 19 19 19 22 16 13 16 9 14 15 15 18 20 14 14 13 9 6 6 11 5 6 6 4 10 8 9 11 14 6 6 14 12 9 12 4 11 16 7 4 5 9 8 8 5 5 7 7 7 10 9 9 11 8 10 9 9 9 6 11 5 8 18 8 10 14 16 7 17 16 10 12 20 13 16 17 16 19 8 16 15 11 18 16 14 13 12 11 11 12 7 10 10 10 18 12 8 12 12 6 6 10 9 7 19 12 11 15 6 8 5 9 6 4 9 7 13 8 14 7 7 7 17 15 6 4 11 5 9 9 7 6 11 7 8 6 9 10 12 6 13 12 13 11 11 10 14 9 6 9 9 10 19 13 19 15 22 15 13 17 16 16 18 14 13 12 26 18 19 29 19 24 14 17 14 11 10 14 12 12 7 14 11 18 15 11 10 9 8 8 8 11 3 14 18 14 20 9 13 13 9 21 9 9 7 16 8 11 9 12 7 17 9 14 11 18 13 12 17 18 10 8 9 9 8 13 9 9 13 14 9 14 7 16 24 22 24 12 19 19 13 16 16 25 20 11 13 18 9 8 25 14 8 14 6 8 3 8 9 8 14 9 7 13 10 6 4 9 13 13 8 12 11 8 8 16 18 6 5 14 8 5 9 12 
];
B = [
0 0 0
 166961 120278 46683
 199410 157035 42375
 174584 137733 36851
 296293 256902 39391
 115787 92559 23228
 504480 464959 39521
 180283 162122 18161
 64601 53225 11376
 159483 147821 11662
 48993 41278 7715
 26256 21039 5217
 20502 16558 3944
 28113 24325 3788
 214604 206043 8561
 204560 196668 7892
 106529 99943 6586
 610991 594087 16904
 140030 132793 7237
 259731 251335 8396
 93416 88603 4813
 278384 270428 7956
 269338 262024 7314
 93471 89273 4198
 266645 259779 6866
 95039 91148 3891
 460554 450147 10407
 278194 271345 6849
 91040 87699 3341
 281141 274714 6427
 90320 87178 3142
 282208 275995 6213
 272876 267147 5729
 95460 92574 2886
 343711 336450 7261
 102739 99720 3019
 272988 267216 5772
 96574 92542 4032
 270721 265158 5563
 269304 263760 5544
 106058 102387 3671
 260731 255488 5243
 101906 98510 3396
 280094 274696 5398
 250901 246002 4899
 94908 91651 3257
 255615 250710 4905
 102143 98980 3163
 250777 245995 4782
 100478 97512 2966
 234953 230511 4442
 256364 251077 5287
 83671 81402 2269
 239130 234334 4796
 82612 80487 2125
 239396 234486 4910
 213823 209228 4595
 103439 101236 2203
 229064 224327 4737
 82721 81012 1709
 20195464 19979400 216064
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
44 47 0 0
23 7 0 0
27 26 0 0
41 14 0 0
14 15 0 0
23 23 1 1
481 37 3 1
3134 31 29 13
14698 41 118 26
61957 52 205 58
201181 49 236 86
603811 71 338 140
1485638 110 384 194
3098572 168 445 257
4879001 215 535 340
6129542 269 542 433
5948394 366 618 534
4482352 445 696 690
2401572 603 821 793
794016 713 921 1012
137877 901 1192 1194
11244 1109 1297 1382
2215 1290 1443 1557
2139 1601 1723 1745
2217 1883 1920 1826
2451 2187 2107 1944
2604 2505 2256 2172
2907 3044 2495 2488
3325 3222 2556 2903
3193 3023 2937 3110
5060 4557 3022 3060
3761 3966 3040 3181
3792 3831 3140 3298
3426 3722 3045 3067
3694 4148 2995 3188
3784 4136 3068 3210
3265 7369 2907 3400
3388 3273 2887 2756
3383 3549 2848 2784
3088 3194 2878 2992
3522 3318 2959 2880
3336 3201 2998 3178
4064 3892 3822 3813
3285 3477 3385 3251
4395 4203 3396 3483
4020 3895 3522 3394
3615 3521 3468 3446
3423 3484 3486 3530
3340 3419 3472 3548
3398 3321 3402 3573
3231 3233 3353 3517
2890 2899 3101 3132
2684 2740 2910 2911
2379 2362 2651 2610
2110 2108 2192 2145
1892 1812 1962 2001
1611 1631 1839 1991
1597 1626 1832 1862
1325 1300 1514 1561
1330 1310 1500 1537
1208 1226 1191 1208
1081 1182 1152 1192
1106 1105 1177 1187
1128 1129 1280 1157
1143 1068 1298 1323
1149 1143 1137 1143
1043 1103 1134 1214
3810 3670 2335 2590
1351 1324 1379 1413
1344 1483 1539 1584
1883 1763 1854 1879
1745 1779 2181 2186
1836 1805 1848 1789
1816 1862 2002 1864
1862 1794 1737 1716
1891 1842 1671 1550
1522 1436 1469 1455
1204 1145 1163 1203
1056 1008 1057 1037
824 783 780 789
559 517 516 523
351 312 364 355
14 16 21 16
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
