A = [
445798 486298 1686772 367944 414087 359639 353369 359534 350266 331211 331089 332576 332627 324776 322463 315330 310092 309903 305415 303645 301982 298610 297041 296671 296094 341632 342193 342786 389567 391485 394192 394511 398043 399970 399920 398533 394883 393364 390959 387533 386017 384059 381555 379173 379120 374685 372286 368829 364790 361828 359944 357545 354507 352718 350680 348785 346081 343026 339159 336723 333473 331625 328885 325871 323820 322425 319813 317711 314236 310800 308713 305985 302622 299797 297959 294698 293287 290110 287122 284218 281759 278074 275157 272967 270346 268394 264982 262261 259668 256998 253583 252035 249726 245578 244147 241009 240107 237018 234277 231509 229300 225769 223754 221020 219312 216544 214368 211831 209085 207178 204705 202715 200507 198532 196215 192706 190907 188776 186698 184898 182375 181096 178627 175801 173828 172867 170747 168384 167091 164206 162854 159835 157614 156971 154723 152141 150517 149379 147330 145127 143131 141709 139315 138645 135969 134431 133178 132138 130206 129343 128263 125568 124625 122036 120403 119268 117513 115779 114829 113086 112358 110203 108435 106654 105826 104287 103382 102069 100214 99418 98077 96327 95162 94250 92318 91521 90274 88694 87766 86585 85216 84142 83005 81990 81094 79975 78359 77325 76635 75622 75178 73723 72829 71486 70371 70190 68948 67932 67108 66125 64943 63977 63140 62033 61641 60659 60136 59199 58662 58190 56927 56457 55453 54329 53557 53131 52218 51449 50790 50324 49246 48943 48145 47445 47148 46091 45639 45342 44373 43796 42962 42781 41935 41837 40999 40101 39774 39472 38430 38174 37401 36925 36439 36303 36292 35186 34786 34275 33510 33280 33184 32528 32306 31968 31557 30626 30366 30405 29572 29071 28909 28320 27970 27679 27335 26786 26840 26464 25965 25483 25376 25182 24616 24219 23976 23814 23496 22939 23108 22698 22267 22031 21739 21622 21228 20998 20348 20375 19785 19682 19568 19281 19216 19199 18583 18502 18230 18134 17943 17606 17292 17113 16752 16675 16502 16168 15930 15692 15639 15271 15197 15241 14990 14777 14673 14316 14355 14141 13646 13613 13473 13038 12930 12913 12557 12403 12366 12361 12141 11910 11819 11697 11661 11249 11233 11126 11054 10777 10576 10517 10560 10301 10192 10111 9985 10074 9826 9736 9433 9498 9535 10085 9126 9271 8956 8707 9739 8778 8737 8623 8404 8375 8286 8249 8078 8131 7846 7782 7670 7703 7578 7317 7250 7162 7051 7051 6849 6847 6725 6717 6447 6465 6430 6303 6457 6407 6179 6236 6172 6235 6263 6077 6152 6074 5838 5703 5379 5332 5278 5464 5341 5529 5104 5258 5170 5203 4927 4898 4999 4840 4846 4727 4879 4718 4689 4653 4486 4481 4350 4374 4431 4354 4305 4206 4191 4094 4162 4064 4026 3950 3950 3870 3890 3826 3861 3794 3863 3695 3703 3561 3632 3626 3515 3425 3390 3371 3439 3485 3220 3325 3259 3257 3308 3120 3062 3067 3011 3097 2955 2957 2929 2904 2898 2892 2867 2945 2815 2857 2734 2717 2706 2710 2730 2657 2681 2600 2557 2578 2480 2525 2411 2498 2432 2368 2431 2418 2374 2342 2326 2383 2308 2273 2193 2266 2280 2194 2216 2186 2108 2169 2172 2095 2111 2108 2011 2091 2099 1984 2051 1980 1972 1974 1965 1934 1912 1876 1883 1882 1821 1880 1819 1843 1832 1802 1784 1712 1788 1703 1798 1737 1761 1745 1706 1748 1679 1645 1594 1659 1601 1618 1585 1653 1611 1516 1628 1541 1609 1545 1563 1570 1584 1516 1452 1510 1460 1353 1463 1453 1437 1448 1342 1360 1441 1450 1421 1379 1386 1354 1382 1354 1295 1303 1304 1310 1298 1310 1290 1235 1230 1288 1281 1240 1271 1252 1250 1228 1181 1188 1134 1130 1194 1111 1131 1133 1117 1117 1182 1082 1101 1082 1043 1075 1062 1067 1095 1010 1073 1017 1036 1071 1050 1010 1052 1025 987 982 1029 988 944 1066 889 952 1004 993 913 965 934 968 845 864 904 955 950 872 877 880 861 925 858 856 935 847 872 831 856 772 775 811 799 795 745 794 823 780 725 719 741 766 720 764 726 715 745 722 749 719 751 735 721 713 732 688 689 673 690 655 682 697 695 666 733 653 647 643 624 685 615 619 627 618 639 645 656 625 607 578 616 569 583 627 594 643 620 586 639 600 586 595 584 587 568 571 541 593 562 511 569 529 533 585 592 532 577 569 573 595 604 549 540 558 563 529 574 591 540 508 529 566 581 563 600 528 585 607 539 499 529 521 569 506 552 531 529 461 440 463 478 480 486 450 522 452 445 468 458 407 394 433 447 423 430 452 410 430 438 449 458 467 459 400 409 449 373 422 441 415 446 483 417 420 395 408 403 399 399 384 442 398 374 396 367 361 340 319 343 378 339 347 304 368 327 332 326 357 357 319 335 325 315 353 362 342 333 327 309 351 364 336 346 323 318 342 297 316 315 313 296 358 299 304 288 318 307 312 314 262 306 317 303 297 272 275 290 279 271 275 257 266 240 255 299 262 255 245 270 223 248 232 255 239 231 251 212 255 249 244 255 236 271 267 272 231 259 277 243 241 265 230 247 252 236 238 209 235 235 242 244 220 244 259 217 200 259 206 182 204 219 234 214 206 200 217 201 199 212 197 190 251 196 213 221 215 211 240 224 184 217 214 185 211 208 204 188 174 157 157 181 171 179 175 202 185 180 171 168 158 176 199 164 151 199 150 183 152 193 166 147 235 157 172 155 171 173 159 159 141 150 137 149 151 146 132 134 138 124 147 142 145 143 130 127 124 140 143 136 132 128 123 129 113 113 121 152 156 128 152 135 142 138 135 149 133 101 137 135 125 121 132 120 112 122 116 118 121 128 125 126 131 137 125 140 97 168 137 134 106 104 111 136 110 109 133 138 117 134 120 100 121 100 115 133 96 130 88 127 90 109 104 103 106 115 120 96 110 112 109 115 103 121 129 141 99 129 115 113 111 115 86 111 103 115 116 119 120 113 103 81 122 99 91 106 96 108 93 84 83 100 96 88 117 84 96 100 95 96 107 92 107 75 93 68 98 103 83 82 70 85 82 83 79 72 83 79 87 87 97 95 99 82 73 89 86 78 75 90 82 84 85 100 85 65 84 114 96 72 91 73 95 81 84 72 59 84 83 68 73 78 86 69 80 75 81 86 94 62 82 85 101 74 76 74 81 72 81 88 57 84 85 73 90 58 69 70 72 101 73 80 85 67 64 80 99 74 73 65 87 83 80 81 76 85 74 88 74 82 74 62 63 71 73 74 78 75 64 78 46 50 69 66 66 66 69 78 64 64 67 70 61 63 42 56 70 61 60 50 53 54 51 59 45 49 55 60 62 50 41 47 35 49 68 52 52 46 40 44 43 49 66 55 42 52 43 61 62 57 40 41 54 38 61 55 58 44 48 50 47 45 52 50 33 43 45 57 53 45 42 51 45 49 45 50 58 57 46 28 42 51 47 50 48 51 57 59 62 58 63 69 61 56 61 49 54 55 55 48 45 47 63 52 49 35 43 47 51 33 35 45 36 42 33 40 47 50 39 35 37 37 31 34 47 25 34 32 33 37 34 44 29 35 49 38 37 35 51 45 29 48 35 23 34 36 34 40 39 43 30 27 39 38 27 20 27 38 30 27 27 40 36 43 29 37 30 31 22 27 20 32 27 24 31 25 24 22 37 33 25 37 23 32 27 31 27 27 34 40 33 36 41 47 46 31 26 38 35 40 34 31 31 37 30 29 34 43 43 39 37 36 36 29 33 40 47 34 38 33 40 30 41 42 48 35 44 38 47 43 44 38 31 27 26 27 34 33 34 23 29 17 32 24 23 29 31 29 24 30 25 31 28 23 24 28 34 23 21 24 32 23 37 31 21 17 21 15 24 17 22 22 18 21 22 22 23 26 24 20 30 27 18 24 23 21 19 16 23 23 37 23 23 28 20 28 20 25 21 17 17 25 21 12 19 22 16 16 17 31 13 21 24 12 26 27 26 14 20 22 17 22 13 20 24 22 22 28 23 20 18 21 26 25 24 21 18 22 19 7 21 23 18 21 14 21 18 18 20 17 23 13 18 14 17 19 26 16 23 13 14 20 14 29 27 15 9 11 11 18 15 10 20 22 23 18 17 14 18 16 15 21 20 16 15 12 22 10 10 20 17 20 16 11 20 18 19 16 19 25 16 19 18 26 24 18 21 24 24 17 26 19 22 15 24 16 11 19 11 17 17 17 10 18 14 13 30 18 9 17 23 16 20 16 18 15 13 26 17 14 16 11 20 11 16 10 30 14 18 28 12 14 15 15 14 20 26 15 11 20 19 12 22 17 12 18 19 16 14 13 8 25 13 18 15 16 13 15 18 16 19 17 10 13 13 9 10 14 11 21 16 18 18 20 16 16 16 11 16 16 12 9 19 16 11 20 12 14 15 10 12 18 18 17 22 12 22 14 11 13 19 15 16 13 12 17 14 13 9 19 16 8 9 10 10 16 14 9 28 3 16 13 7 13 10 11 13 11 9 10 11 16 13 17 10 6 18 12 8 9 10 9 20 13 18 12 11 19 17 7 14 9 7 14 11 7 19 16 14 10 7 10 13 11 11 13 14 8 17 17 11 16 12 12 12 12 9 14 14 15 8 10 12 16 16 15 11 10 11 13 13 13 17 17 7 15 11 9 6 5 16 13 12 14 11 13 13 11 12 14 13 12 12 7 13 16 10 20 14 11 12 16 9 12 19 16 14 10 13 18 15 12 26 18 17 8 10 17 7 14 9 19 11 6 15 8 16 8 5 8 7 15 9 17 7 17 11 18 8 11 13 13 11 10 14 11 9 11 16 15 17 11 10 11 10 10 6 8 9 11 9 11 10 7 9 7 16 13 9 15 7 7 9 6 8 16 16 10 15 9 11 5 7 17 14 10 9 11 12 8 11 9 11 6 10 12 19 15 9 11 8 5 7 13 10 12 15 13 12 8 10 14 15 14 18 8 8 12 13 17 14 16 13 9 11 7 10 10 15 8 12 11 14 13 9 9 9 17 10 13 16 15 12 17 10 13 12 11 11 7 6 12 11 6 10 
];
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
 702814 295563 407251
 51883 21011 30872
 92536 38553 53983
 505528 230631 274897
 352699 160637 192062
 589453 274453 315000
 1059856 491882 567974
 866512 371689 494823
 544738 248226 296512
 1241827 586528 655299
 485105 199563 285542
 33184 13722 19462
 1111914 513566 598348
 17911 7510 10401
 31156 12907 18249
 1519420 730893 788527
 32584 13887 18697
 395480 163203 232277
 2089792 1092916 996876
 399415 170181 229234
 11 4 7
 15047835 8243356 6804479
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
55 72 0 0
74 14 0 0
113 19 1 2
159 26 0 0
90 25 0 0
76 26 35 0
231 54 62 8
1583 60 110 22
10576 77 118 47
48725 102 199 72
126898 115 223 123
284652 149 324 189
557881 222 436 283
1040760 278 569 423
1542746 373 753 632
1834188 573 1066 955
1643184 884 1431 1351
1195070 1262 1820 1798
737088 2031 2296 2308
379446 2788 2805 2836
156657 3723 3321 3190
40075 4615 3432 3385
8752 4887 3563 3483
6196 4215 3486 3581
5483 4165 3662 3680
5183 4497 3835 3830
5129 4292 3844 4034
4878 4316 4211 4167
5130 4721 4493 4266
5215 4669 4799 4684
5438 5129 5060 4997
5935 5526 5308 5553
6771 5963 5771 5704
7208 6435 6229 6267
7450 6931 6843 6831
8038 7593 7254 7490
8759 8123 8146 8153
9540 9155 9102 8852
10243 10035 9912 10092
11205 10966 11037 10956
12171 12350 12023 12054
13573 13623 13661 13780
15378 15389 15208 15092
17335 17410 17361 17254
19114 19104 19265 19231
21431 21804 21857 21879
24283 24410 24510 24461
27026 26877 26879 26987
29668 29820 29477 30028
32739 32619 32386 32123
35407 35102 34976 35331
37379 37271 36849 37476
39622 39245 38751 39043
40796 41204 40759 40984
43201 42793 43250 42607
44227 44668 44267 43926
46941 47027 46748 46650
49773 48998 48983 48793
51244 50844 51177 51372
53529 53091 53179 53174
55456 55418 55301 55107
55684 55539 55610 55681
54172 53211 53730 53263
46773 46757 46379 46556
34757 34878 35457 35244
19665 20231 20159 19589
8287 8730 8630 8496
4615 4806 4726 4411
3996 3731 3526 3636
3319 3472 4200 3005
2149 2429 2356 2448
1944 1394 1558 1879
162 167 52 57
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
