A = [
661810 724643 2453240 561008 634831 551069 544050 552921 540173 511850 511976 515621 514855 502180 498650 488296 480919 479664 472702 469040 466944 462672 458899 457973 457019 522782 523761 523982 589273 593436 596706 597736 601464 604092 604676 602098 597397 594283 589915 585283 582815 579822 575977 572282 571574 565623 561587 557783 551016 545879 544197 539256 535389 532917 529130 525735 521552 516713 511354 508237 502672 498559 495626 490769 487865 485062 480137 478288 472247 466776 464304 460098 455116 450616 447393 443418 440175 435308 431413 426842 422766 416928 412770 409663 405677 401954 397400 393873 389230 384533 380585 376832 373849 367817 365273 360769 357962 353680 349691 346174 342332 337749 333790 330064 326871 322730 319413 315778 311759 309036 305482 301953 298674 295323 291954 287275 284507 280749 277000 274719 271552 268441 265297 261180 258230 256474 252877 249758 246969 243438 241374 237811 234204 232452 228925 225383 223327 221046 218129 215065 211973 209891 206530 204774 201462 198938 197081 195170 192113 190687 189447 185503 183949 180364 177729 175928 173252 171251 169241 166782 165158 162728 159813 157600 155937 153860 152062 150425 148164 146456 144658 142332 140095 138903 136216 135051 133161 130632 129084 127560 125658 124423 122405 120773 119197 117718 115635 113718 112928 111535 111027 108482 107331 105587 103967 103521 101350 100423 98596 97089 95975 94754 93211 91881 91037 89573 88605 87160 86856 85665 83929 83262 81828 80379 78653 78151 77078 76260 74631 74038 72693 72485 70961 70279 69715 68062 67535 67168 65460 64544 63392 63231 62143 61790 60472 59355 58772 57999 56792 56697 55503 54911 54056 53670 53509 52273 51665 50728 49988 49296 49202 48214 47864 47126 46794 45666 45015 45075 44168 43172 43080 42120 41484 41219 40716 39908 40172 39250 38814 37999 37989 37336 36729 36147 35931 35567 34839 34357 34100 34036 33248 32970 32419 32222 31880 31412 30377 30509 29803 29487 29244 28776 28586 28944 27831 27871 27299 27183 26935 26305 25891 25657 25134 25030 24692 24295 23976 23494 23324 23093 23021 23063 22692 22217 22224 21541 21678 21225 20628 20607 20341 19805 19776 19448 18946 18816 18717 18531 18361 18028 17874 17753 17680 17208 17090 16776 16827 16279 15973 16088 16052 15650 15497 15321 15196 15372 14954 14877 14344 14460 14493 15405 13848 14096 13776 13319 14743 13374 13377 13162 12902 12785 12663 12572 12309 12458 12202 11902 11699 11779 11598 11332 11242 10935 10874 10782 10559 10479 10325 10373 10069 10094 9871 9719 10022 9863 9640 9630 9558 9530 9704 9389 9477 9306 9030 8853 8375 8342 8206 8427 8281 8452 7912 8140 8131 7965 7717 7682 7750 7596 7506 7424 7566 7313 7286 7279 6892 7015 6762 6812 6781 6793 6688 6539 6515 6445 6456 6329 6312 6177 6191 6127 6089 6018 5968 5897 5954 5882 5820 5536 5655 5672 5481 5504 5357 5345 5405 5415 5205 5234 5167 5130 5201 4931 4830 4843 4774 4857 4734 4680 4679 4618 4586 4510 4529 4566 4404 4516 4386 4299 4270 4307 4259 4090 4205 4096 4017 4091 3998 4040 3851 3928 3833 3723 3854 3874 3785 3743 3695 3806 3734 3564 3521 3597 3572 3477 3485 3477 3395 3397 3401 3315 3362 3342 3249 3317 3334 3206 3216 3132 3178 3108 3134 3127 3063 3021 2988 2993 2970 3053 2870 2929 2965 2825 2908 2766 2854 2689 2820 2752 2782 2784 2709 2734 2656 2599 2605 2617 2562 2601 2530 2610 2559 2433 2569 2478 2441 2475 2499 2429 2521 2402 2344 2406 2305 2296 2307 2302 2216 2315 2190 2212 2239 2275 2208 2159 2215 2167 2173 2230 2097 2059 2085 2067 2085 2079 2054 1898 1991 2032 2034 1950 2001 1967 1991 1986 1903 1901 1824 1877 1857 1804 1852 1795 1767 1753 1870 1719 1742 1771 1757 1709 1653 1720 1713 1631 1709 1618 1644 1682 1640 1634 1656 1647 1593 1550 1636 1572 1540 1630 1450 1510 1605 1580 1466 1522 1496 1578 1349 1393 1447 1462 1487 1365 1447 1443 1384 1462 1389 1336 1449 1345 1395 1340 1329 1262 1304 1328 1316 1224 1195 1253 1270 1218 1189 1160 1223 1212 1173 1227 1158 1161 1160 1166 1213 1166 1207 1178 1135 1127 1160 1108 1147 1055 1058 1065 1074 1101 1071 1097 1106 1054 1043 1059 1031 1067 964 992 1002 1015 1021 1057 1045 991 965 947 1010 914 940 1000 961 1003 973 943 999 980 960 964 922 923 894 921 866 930 885 884 887 852 885 931 915 873 892 939 920 935 926 838 864 892 880 874 895 948 839 782 814 870 907 901 934 859 926 966 813 816 824 828 835 801 860 795 839 760 712 722 733 749 743 700 802 738 735 725 733 670 665 702 700 664 699 689 703 692 688 695 704 766 722 665 654 723 608 662 704 655 685 710 641 674 616 630 608 631 632 607 672 638 612 637 588 550 546 518 580 592 544 556 520 594 523 529 530 578 551 521 533 502 515 551 557 540 513 523 530 535 581 563 483 521 491 555 491 474 503 511 494 568 462 476 482 491 490 476 504 443 486 497 480 468 446 441 471 441 417 427 419 445 406 392 470 422 407 410 408 337 413 386 415 385 367 398 361 393 390 386 382 391 437 406 444 386 421 429 394 381 415 379 403 399 374 364 337 381 359 387 399 335 371 384 348 306 395 340 298 354 361 384 339 338 337 345 319 316 353 323 300 386 335 323 359 331 331 372 342 288 324 344 293 353 319 307 312 293 229 274 278 281 293 308 314 284 309 302 272 262 277 326 261 255 302 256 288 242 297 270 235 341 256 261 241 271 280 256 255 227 246 218 240 237 231 214 217 224 199 222 223 222 226 209 218 214 218 226 202 201 205 213 196 179 198 200 228 235 191 221 224 232 217 214 227 225 187 213 197 198 198 193 207 195 181 202 179 210 188 194 197 199 205 210 222 198 222 216 221 179 169 171 202 178 181 213 212 180 206 182 177 190 169 173 192 175 192 146 193 162 164 167 167 167 179 174 161 195 180 165 183 165 173 191 207 165 205 173 165 181 170 147 168 175 183 190 189 162 174 171 140 184 156 158 165 149 174 161 139 140 153 164 144 175 152 151 144 144 143 162 152 161 139 149 124 145 147 134 121 128 137 134 124 136 133 134 128 143 147 157 143 144 136 122 150 142 113 134 128 125 124 130 150 138 111 141 169 138 117 136 122 147 117 132 108 108 120 134 107 119 132 135 120 131 119 121 151 131 103 126 121 149 132 125 111 140 126 125 138 96 120 121 101 138 99 119 106 112 140 116 120 134 120 102 110 134 129 108 114 133 143 123 141 114 136 114 137 115 122 122 101 107 111 100 107 125 106 100 113 79 90 93 105 85 100 116 126 91 107 96 103 85 96 78 92 113 88 95 76 82 87 75 97 66 80 78 88 91 85 67 77 56 72 102 77 82 77 67 74 76 63 106 79 81 104 69 88 86 96 73 75 87 67 102 93 95 71 87 82 81 70 88 68 59 69 94 83 90 75 77 77 80 72 75 71 86 89 70 65 62 71 85 94 71 82 85 91 92 90 110 97 94 87 96 77 90 75 78 69 70 73 94 74 77 60 77 66 77 49 56 71 66 55 54 61 72 75 59 54 58 64 52 50 62 49 56 60 55 63 68 66 48 60 67 59 62 55 65 72 44 71 59 39 63 57 53 73 69 70 47 52 70 54 50 38 57 55 49 47 47 64 54 72 50 61 52 51 36 42 36 44 42 43 51 46 42 43 54 61 46 52 45 47 44 44 45 42 53 60 53 52 70 63 70 48 40 56 59 61 56 53 46 54 52 46 57 70 62 52 60 61 54 52 57 62 77 53 51 55 56 52 65 62 75 51 59 51 73 74 68 59 48 47 43 45 50 61 49 41 43 29 52 37 41 48 48 45 36 50 44 46 55 31 36 37 46 30 37 34 45 39 51 45 35 33 48 31 38 28 36 32 32 32 40 41 41 36 38 32 54 48 31 35 40 34 34 28 43 38 55 32 39 41 40 41 35 34 30 40 32 38 36 33 28 29 27 33 28 43 26 36 40 24 37 38 45 23 35 30 32 43 24 34 35 29 36 37 30 36 31 33 34 37 33 29 29 34 36 22 27 35 31 34 26 27 29 26 33 27 31 22 27 29 28 33 33 27 34 20 27 26 28 44 40 23 19 21 25 28 30 16 27 30 36 28 26 26 24 23 30 29 33 26 21 23 32 19 23 33 29 30 36 19 29 32 36 23 37 40 33 34 28 37 36 29 29 36 47 25 32 31 30 24 34 24 17 34 23 26 28 33 17 31 30 23 40 23 23 22 34 23 29 27 24 20 18 36 32 24 27 19 25 23 28 16 46 21 29 36 20 25 25 23 24 30 40 24 14 30 33 18 34 28 18 33 36 24 26 20 19 36 23 29 22 24 24 26 31 28 31 24 16 21 19 15 16 18 19 29 24 30 28 27 30 25 23 19 22 26 26 17 26 21 24 25 29 23 20 22 19 24 27 31 30 20 28 21 19 19 29 19 19 21 30 22 20 18 18 33 23 13 13 15 15 26 19 16 37 5 30 25 15 25 17 12 22 19 15 20 20 20 22 26 17 16 33 19 11 16 15 20 27 19 28 20 16 29 23 10 20 11 13 23 16 13 22 20 22 16 14 18 16 18 19 16 21 16 27 23 20 22 26 20 17 19 19 23 19 21 11 13 18 24 25 21 19 21 16 23 19 17 21 27 16 23 19 17 17 11 21 18 19 22 22 19 21 16 21 19 22 15 19 18 23 21 17 29 26 14 13 25 17 20 29 24 19 23 23 31 22 21 38 26 29 19 17 25 17 23 17 28 25 12 28 18 26 16 8 15 13 26 16 28 11 30 15 27 20 16 22 18 19 20 18 24 15 14 21 25 22 13 16 14 16 17 19 11 20 15 19 17 19 9 18 14 26 21 17 21 19 13 15 10 18 22 22 17 18 13 17 11 11 21 24 18 11 18 18 13 23 16 16 14 16 17 28 26 15 20 16 11 10 20 14 18 19 18 23 15 16 20 29 23 27 16 15 23 18 26 17 23 23 14 14 16 22 21 25 13 19 18 23 21 21 15 18 21 19 28 23 23 17 26 16 21 22 23 17 15 11 18 20 15 13 
];
B = [
0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 1049302 446385 602917
 76611 30992 45619
 135137 56501 78636
 754145 347486 406659
 514077 235221 278856
 857962 402100 455862
 1563141 731732 831409
 1269420 545662 723758
 791087 362449 428638
 1833036 872478 960558
 716464 294762 421702
 49184 20290 28894
 1664565 774872 889693
 26344 10990 15354
 46844 19468 27376
 2282305 1108579 1173726
 48443 20694 27749
 587513 241802 345711
 3162441 1674669 1487772
 587203 249666 337537
 15 5 10
 22779141 12626661 10152480
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
77 101 0 1
117 18 0 0
191 31 1 2
248 38 0 0
125 39 1 0
106 42 51 1
374 80 103 13
2731 83 143 30
18516 110 192 69
85042 143 293 122
217224 172 342 189
477768 219 473 287
917679 324 659 419
1671466 438 856 629
2416365 575 1164 921
2821982 867 1533 1414
2502350 1269 2041 1981
1810581 1801 2631 2607
1115344 2887 3343 3316
577264 3880 4078 4084
240418 5204 4652 4505
63302 6526 4855 4814
13539 6857 5030 4972
9135 5927 5034 5157
7982 5969 5217 5203
7613 6389 5371 5415
7442 6157 5473 5700
7136 6146 6041 5913
7352 6704 6410 6151
7538 6752 6820 6693
7808 7278 7148 7145
8513 7943 7624 7895
9854 8657 8242 8128
10498 9173 8889 8839
10776 9978 9716 9797
11472 10795 10417 10633
12505 11605 11597 11596
13858 13146 12919 12725
14606 14270 14187 14448
15823 15691 15619 15768
17384 17599 17082 17332
19343 19446 19512 19556
21928 21848 21730 21425
24516 24609 24699 24511
27456 27296 27410 27498
30778 31178 31184 31317
34811 34844 35021 35103
38543 38375 38542 38519
42287 42664 42370 42641
46813 46658 46060 46104
50465 50130 49927 50513
53672 53337 52824 53551
56480 56116 55717 55555
58623 59019 58553 58878
61820 61290 61968 61255
63357 63847 63281 63203
67379 67403 66934 67089
71426 70531 70267 70198
73653 73144 73435 73351
76639 76119 76376 76525
79695 79369 79602 79113
79853 79757 79906 79927
77388 76424 77023 76689
67179 66916 66484 67106
49920 50266 50900 50494
28425 29063 28966 28024
11927 12602 12425 12150
6600 6795 6842 6386
5718 5413 5086 5298
4704 5035 5996 4409
3108 3569 3424 3545
2759 2047 2216 2681
226 244 86 91
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
