A = [
377187 391299 1618261 319944 331571 299346 290626 294568 284894 267478 264470 266034 261950 257976 254796 250760 247564 246370 242984 241856 239187 236018 235319 234935 235244 280924 280707 282030 328821 327989 331275 332679 334400 335776 335378 333994 330260 327086 325311 321490 320508 318092 317585 316745 316740 311558 309165 307053 303913 301066 298358 296133 295713 294768 291669 290207 288129 285150 283302 280454 277068 275137 274459 274534 270324 269350 267844 264917 263640 260942 258728 254999 253380 251382 250172 249549 246632 243913 241445 240478 238232 235081 232991 231448 229694 227361 226049 224899 222663 221021 218090 216990 215179 212560 210302 208708 207115 205954 204283 201769 200172 199104 196293 194208 193919 191785 190156 189735 186930 185536 183627 181150 179895 178372 177381 175999 173750 172740 169881 169141 168434 165562 163550 161950 160185 159629 158225 155976 154508 153188 151797 150471 148731 148048 146443 144702 142872 141949 140556 140016 138062 137282 135734 134218 133057 131525 129749 128296 127453 125978 124686 123451 122260 121655 119495 119415 117674 116548 115698 113843 113047 111710 109793 108661 107332 105721 105136 104088 102750 101506 101121 99751 98251 97768 96367 95614 94655 93013 91876 91332 90311 89262 88443 87232 86373 85757 84222 83196 82963 81375 80831 79481 78388 78052 76830 76003 75081 75104 73447 73091 71923 70652 70218 69221 68691 67625 67125 65685 65029 63957 63005 62898 62609 61523 60601 60188 59380 58368 57957 56818 56409 55987 54845 53635 53447 52465 52021 51722 50589 49480 49366 48979 47827 47553 47035 46456 45791 45185 43992 43642 43345 42490 42079 41807 41461 40806 40582 39670 39503 38950 38215 38036 37205 36628 36605 35731 35120 34877 34152 33803 33679 32815 32393 32084 31421 31033 30797 29966 29960 29765 29210 28835 28576 28122 27643 27385 26996 26478 26405 25862 25482 25396 25073 24626 24135 24082 23455 23676 23318 22662 22125 21987 21645 21619 21313 21127 20841 20442 20100 20100 19529 19352 19426 19263 18964 18426 18263 18099 17918 17320 17322 17115 16993 16407 16352 16185 15665 15605 15348 15173 15235 14595 14230 14134 13817 13894 13573 13312 12982 12965 12690 12588 12402 12326 12013 11978 11918 11993 11824 11345 11450 11320 10864 10877 10726 10366 10536 10434 10242 9742 9763 10321 9889 9516 9451 9123 10249 9055 9048 8942 8778 8745 8522 8564 8251 8090 8158 7877 7822 7812 7687 7427 7386 7364 7213 7157 7150 6999 6951 6719 6623 6574 6441 6457 6606 6347 6055 6301 6127 5861 6112 5978 5937 5958 5883 5771 5562 5384 5313 5349 5258 5109 5148 5054 4904 4943 4800 4814 4689 4670 4461 4464 4369 4421 4370 4378 4413 4106 4136 4020 3935 3948 3931 3908 3852 3817 3706 3703 3726 3734 3529 3494 3570 3509 3411 3284 3392 3293 3324 3190 3182 3099 3042 3027 3079 2942 2998 2827 2913 2806 2829 2861 2716 2753 2722 2702 2649 2668 2575 2582 2411 2496 2408 2365 2494 2336 2406 2272 2295 2366 2304 2256 2185 2239 2253 2148 2179 2199 1909 1979 2035 2104 1954 1901 1920 1950 2051 1908 1934 1876 1880 1923 1878 1903 1860 1834 1753 1756 1775 1654 1763 1701 1702 1637 1634 1717 1689 1611 1691 1599 1540 1524 1449 1473 1508 1497 1457 1480 1424 1464 1417 1392 1459 1371 1385 1341 1341 1329 1395 1409 1433 1346 1329 1295 1335 1365 1237 1306 1315 1353 1359 1223 1230 1279 1254 1377 1298 1482 1348 1193 1259 1200 1240 1156 1223 1247 1170 1184 1206 1142 1163 1188 1096 1178 1211 1039 1027 998 1016 995 978 1047 1077 1095 1150 1135 1111 1046 1081 983 1000 922 982 979 927 981 916 963 886 916 868 912 908 930 913 910 963 910 884 918 793 820 837 838 812 789 785 822 773 760 812 791 778 756 748 704 801 765 803 763 686 685 710 731 656 676 661 723 714 692 661 640 696 676 637 659 696 663 623 649 623 632 609 640 611 610 609 581 565 583 600 555 588 617 558 614 566 575 553 600 565 587 561 555 548 541 570 507 544 495 551 546 522 491 488 468 527 496 536 536 504 519 502 454 495 467 459 493 498 490 517 532 498 491 456 433 480 431 472 491 430 447 431 453 443 454 470 437 437 427 427 454 418 437 430 403 418 427 449 444 402 436 458 464 434 422 422 422 444 430 440 487 469 477 518 603 635 520 518 511 474 469 474 539 428 442 514 487 483 447 463 466 450 454 416 422 437 402 369 363 345 374 348 378 365 353 385 381 370 359 389 433 353 455 381 386 353 377 357 353 327 392 356 378 374 352 358 382 314 329 321 350 311 336 337 321 324 344 336 349 340 302 311 344 366 332 297 324 354 275 290 270 306 304 277 313 265 326 278 280 274 251 282 264 252 285 288 257 274 259 265 280 308 271 299 272 289 271 285 291 332 319 297 270 251 262 262 266 247 281 255 256 269 239 251 249 233 209 239 226 209 239 204 194 215 186 237 218 227 207 193 238 237 236 230 235 235 235 225 260 212 243 216 237 215 225 194 218 233 201 192 211 206 223 204 179 222 190 180 195 181 182 167 173 205 158 208 226 170 191 195 164 183 154 199 188 198 199 222 209 292 210 180 182 208 178 165 181 172 179 180 166 169 166 157 145 147 153 197 159 182 166 137 134 145 153 154 172 149 148 147 137 169 151 148 153 141 158 140 135 139 133 143 142 130 128 132 115 125 124 121 130 127 112 128 115 123 117 116 119 130 140 140 133 146 127 138 126 97 135 140 119 112 133 121 119 128 139 132 132 120 132 130 117 121 126 136 116 101 123 92 85 114 105 90 116 130 105 144 140 107 115 126 110 118 98 104 113 113 113 98 95 108 111 114 122 115 112 113 95 117 108 90 107 105 125 109 113 99 118 116 104 103 99 89 115 124 132 117 116 86 134 119 102 105 130 111 91 109 111 108 107 119 111 100 110 89 107 69 85 98 96 101 87 99 108 84 93 102 99 96 85 95 87 96 106 92 90 71 84 79 92 85 88 72 94 93 87 92 76 86 88 82 80 97 81 85 85 79 101 82 67 80 112 85 91 85 98 80 95 93 92 92 82 70 90 89 83 89 83 84 84 83 83 76 71 71 71 105 81 80 85 84 90 75 83 88 86 86 70 89 80 86 79 86 81 88 92 64 102 84 90 100 91 88 65 77 82 103 84 70 80 79 79 92 79 99 94 82 80 62 80 71 72 73 78 93 76 80 68 66 81 75 50 61 65 56 55 47 57 57 67 75 41 55 59 64 64 70 50 58 51 57 42 43 57 62 54 59 61 52 68 57 50 56 49 50 42 45 49 47 49 52 52 60 42 63 52 44 41 44 44 50 49 49 48 55 53 49 60 54 61 44 50 57 57 38 47 46 52 45 53 45 56 41 36 56 45 54 50 42 51 33 47 55 45 55 36 42 55 49 48 60 50 58 63 36 63 36 38 41 51 48 37 44 42 43 62 45 36 40 41 36 38 39 35 52 32 35 42 52 55 34 36 33 38 39 31 39 36 34 36 38 38 36 31 36 36 27 31 33 40 39 34 29 32 40 35 39 42 41 26 45 24 42 39 35 35 33 32 39 27 45 36 30 41 33 34 34 26 22 37 42 28 26 27 29 33 30 26 23 35 31 40 41 27 27 35 34 32 35 31 36 45 38 22 31 42 28 18 28 31 33 26 44 29 43 37 52 43 45 28 38 46 39 55 44 42 41 47 29 46 29 37 46 43 44 34 31 36 35 44 32 31 46 38 32 42 43 33 25 36 32 37 39 37 44 33 34 18 25 34 30 37 34 26 37 24 26 26 23 26 28 36 27 30 36 14 38 31 30 22 27 20 21 23 16 25 23 24 27 21 18 21 16 26 25 28 21 16 14 25 21 22 24 22 31 29 25 24 18 28 23 31 24 26 24 28 28 15 24 16 19 21 26 26 22 18 24 29 20 23 25 17 25 23 22 22 19 18 20 19 25 21 26 17 19 33 16 19 16 17 32 20 20 14 20 24 24 17 14 16 20 23 19 17 16 18 21 14 16 22 15 21 27 14 26 27 24 17 19 19 16 13 15 18 13 19 14 20 15 11 24 25 12 16 18 12 16 23 12 16 29 14 24 24 17 25 15 23 16 19 24 22 26 23 32 23 23 22 15 16 18 27 23 22 22 15 20 28 27 27 20 17 14 17 19 19 24 19 22 30 24 31 26 19 28 26 17 28 16 21 30 24 14 18 13 16 19 20 16 20 15 13 23 16 22 21 21 18 18 28 17 17 14 17 27 15 26 18 15 21 22 28 26 16 18 65 99 113 115 86 76 76 70 31 14 22 15 15 21 17 18 16 16 17 17 15 16 17 16 13 19 20 16 16 24 12 17 15 13 19 24 31 36 31 23 31 24 27 22 20 14 15 9 17 14 14 16 16 10 10 11 11 18 15 9 18 13 15 15 9 14 16 17 16 11 13 18 21 15 10 21 10 15 12 19 13 14 17 14 19 11 15 16 14 9 14 8 11 13 18 14 27 16 20 17 19 17 15 21 19 14 17 14 11 18 13 8 10 7 15 8 13 15 11 9 7 10 9 6 10 6 13 15 8 9 17 14 13 14 14 8 7 14 13 5 9 11 13 10 15 12 18 15 15 15 13 16 15 12 9 12 17 16 23 13 14 10 12 11 19 12 12 16 14 10 12 8 18 18 12 17 20 9 7 21 11 11 18 11 14 13 23 18 15 13 20 14 17 19 12 10 16 9 13 13 11 8 14 19 16 15 19 7 11 10 11 13 12 5 13 6 12 10 6 17 14 15 15 12 19 20 12 11 11 12 11 13 11 8 18 7 7 6 14 8 11 7 22 10 11 14 12 17 12 11 14 13 16 9 4 10 10 9 17 10 8 10 11 18 13 12 17 8 13 14 10 10 8 10 11 9 8 7 7 11 17 18 11 9 9 14 14 11 9 4 13 14 12 6 10 14 16 12 14 9 5 13 13 13 17 12 10 12 7 16 5 11 10 6 9 11 15 6 20 9 12 12 8 
];
B = [
0 0 0
 129669 38723 90946
 61992 18592 43400
 215901 74388 141513
 137278 43048 94230
 80560 24350 56210
 211955 75269 136686
 168071 55058 113013
 93987 29608 64379
 287299 100462 186837
 297477 97597 199880
 53228 16544 36684
 855298 301320 553978
 113693 38926 74767
 36040 11671 24369
 199263 81274 117989
 63375 24665 38710
 19096 6625 12471
 220171 91349 128822
 17524 6027 11497
 18344 6501 11843
 4335 1562 2773
 96 25 71
 4265 1593 2672
 327560 139420 188140
 21024 7447 13577
 27395 10494 16901
 342739 148103 194636
 19610 8013 11597
 41618 16738 24880
 534282 222069 312213
 38487 15575 22912
 68463 28532 39931
 386784 175149 211635
 252141 113147 138994
 419739 191349 228390
 785338 358617 426721
 628291 269255 359036
 389341 174407 214934
 917794 427073 490721
 354286 148115 206171
 24530 10328 14202
 844217 388874 455343
 13231 5619 7612
 23486 9941 13545
 1162625 553358 609267
 24232 10593 13639
 284231 119466 164765
 1624081 826472 797609
 282502 121580 160922
 10 5 5
 11262807 5956776 5306031
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
37 63 1 0
31 9 0 0
102 18 0 0
152 15 1 0
116 20 0 0
109 21 12 1
209 48 57 10
841 68 64 18
4297 59 90 34
16909 100 143 57
38007 128 183 82
79622 169 241 137
158044 204 353 194
324501 285 485 323
612311 393 640 502
1056384 608 919 807
1356952 880 1294 1195
1234694 1410 1642 1735
846692 2164 2159 2211
443745 2948 2714 2668
171594 3600 3070 3052
41197 4286 3242 3309
9569 4387 3462 3275
6996 4006 3555 3446
5879 4298 3637 3807
5711 4721 3601 3712
5830 4071 3752 3876
5372 4189 3960 4002
5429 4663 4373 4204
5208 4658 4546 4418
5412 4839 4725 4769
6064 5457 5071 5112
6538 5983 5551 5536
7317 6465 6148 6012
7721 7037 6877 6995
8291 7799 7465 7502
9236 8692 8283 8558
10104 9650 9559 9756
11057 10623 10672 10776
12250 12046 12151 12134
13802 13802 13714 13777
15666 15449 15702 15517
17554 17660 17640 17555
19885 20053 20179 19646
22844 23041 22506 22695
25439 25684 25817 26090
29104 29004 29267 29043
32674 32370 32426 32137
36194 35849 36066 36269
40083 39544 39908 39671
43133 43262 43260 43391
45904 46515 45729 45979
48950 48803 48959 48386
51682 51044 50833 51316
53965 53622 54684 53832
55924 56114 55839 56030
59197 59272 59587 59412
62351 62045 61807 61740
65219 64452 64711 64382
67027 66752 66860 67525
69912 70671 70059 69730
70310 70280 69901 70095
68430 67000 67593 67436
58617 58934 59400 59125
43974 44150 44242 43200
24826 25212 24971 24389
11035 11637 11320 10823
6960 6751 6824 6237
5818 5244 5260 5172
4720 4872 5854 4359
3462 3534 3427 3703
2742 2255 2549 2606
198 198 163 158
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
