A = [
6520058 4912532 52988818 2080586 2261367 2031372 1824931 1915494 1735123 1640689 1600000 1524010 1512446 1469553 1416310 1390961 1369297 1366882 1360228 1315100 1298464 1310371 1282788 1257266 1245855 1303427 1295580 1279890 1314001 1174711 1173511 1157979 1020733 1028017 1023942 1023057 1020430 1003800 1004110 1009831 996949 1009808 1001696 997444 1013743 990786 985475 1018737 999901 994486 1002790 971240 975236 971077 949932 935474 941260 953639 924652 912012 924722 912166 899850 888668 877693 881100 864847 852336 852151 839691 839144 840984 836372 834555 840507 833293 830435 825433 815980 805581 802279 802131 787936 778537 781434 762038 749078 726439 712084 710140 699579 691184 689545 684216 674903 671384 666402 661363 654266 647687 644862 641201 633746 628833 623633 622354 616248 609979 606332 603834 596331 595170 592752 590647 586867 584541 617688 619452 617857 652370 661565 662653 662235 663858 662910 658255 654009 649718 643923 640992 635527 629308 626163 620533 617146 611509 605557 601832 595695 591376 586965 581076 576167 572493 567082 562717 558013 552571 547180 542578 534966 530077 525417 519123 514989 511476 504571 499169 494995 489213 484903 481264 475734 470301 467364 461561 456787 452685 448643 442454 438322 434292 429285 426584 422403 417468 414316 408708 405130 401074 395727 391948 390802 384772 381394 377649 373019 370002 365685 362962 358246 353912 349287 346187 342040 338526 335365 331372 327074 323754 320554 317674 314073 309593 306766 302593 299429 296161 292973 289525 284876 281432 278605 275791 272334 268447 266515 263589 260850 257070 253717 251616 247472 244679 241514 238850 234004 231246 227127 223889 220787 217724 214081 211902 208762 206045 203697 201271 198319 195907 193045 190558 187904 184716 183350 180259 177480 175880 174007 170446 168424 166184 164788 162174 161112 157442 155671 153574 151264 149872 148400 145422 143174 141894 139552 138150 136182 133737 132692 130451 128753 127163 125196 123005 121973 119788 118162 116834 114882 113344 112244 110848 108538 107290 105614 104005 102631 101930 100342 98609 97311 95041 94711 93682 91916 90467 89761 88613 86265 85684 83828 83322 81705 81296 79722 78378 76948 76258 75652 73427 72977 72233 70727 69722 68564 67427 67032 65942 64464 64022 63447 62031 61015 60236 59509 58368 57706 56726 56561 55051 54630 53571 52800 51661 50952 50415 49127 48745 48075 47242 46835 45741 45241 44579 43973 43404 42554 41857 41206 40608 39821 39984 39016 38092 37774 37118 36323 36210 35562 34654 34567 33981 32918 32781 32025 31601 31183 30843 30476 29836 29423 28860 28288 28265 27555 27168 26764 26378 26331 25412 25318 24508 24417 24182 23387 23343 23168 22672 22074 21757 21461 20975 20886 20418 20202 19902 19613 18970 18753 18592 18113 17939 17824 17497 17174 16948 16670 16382 16257 15834 15580 15566 15149 14856 14682 14258 14347 13937 13613 13638 13393 13179 12894 12730 12657 12301 12219 11868 11833 11353 11579 11323 11197 10785 10803 10459 10332 10253 9994 9765 9713 9506 9352 9216 9147 8890 8726 8643 8486 8416 8282 8033 7901 7704 7746 7557 7406 7374 7252 7145 6982 6830 6842 6749 6538 6544 6270 6273 6213 5964 5941 5848 5631 5737 5586 5590 5307 5395 5176 5175 5130 5010 4991 4892 4657 4773 4489 4493 4474 4339 4345 4347 4179 4162 4073 4021 3891 3898 3782 3869 3719 3606 3519 3613 3523 3382 3360 3368 3287 3197 3167 3122 3071 2937 3125 2982 2887 2917 2878 2838 2707 2783 2672 2651 2530 2498 2493 2452 2314 2455 2227 2288 2279 2238 2192 2236 2145 2063 2081 2010 2043 1920 1990 1871 1891 1859 1839 1880 1747 1765 1705 1742 1669 1641 1661 1652 1591 1635 1553 1544 1535 1528 1500 1430 1403 1463 1438 1366 1354 1359 1226 1307 1251 1260 1215 1203 1171 1247 1231 1156 1148 1112 1151 1043 1112 1033 1087 1072 1069 977 968 1018 974 1031 1014 945 928 983 934 974 908 861 864 889 815 824 801 844 765 835 771 755 768 801 751 714 744 758 730 690 743 728 676 642 686 705 636 622 601 638 617 645 591 604 566 635 569 650 569 567 545 564 613 533 598 512 575 586 510 533 492 527 507 494 545 513 486 501 485 478 498 438 454 418 456 477 465 449 415 451 434 427 418 451 430 394 406 408 382 393 385 350 387 398 384 386 395 387 374 372 382 344 383 380 359 357 346 346 356 325 366 339 354 361 340 332 342 317 334 308 305 324 323 304 296 323 292 327 303 309 313 276 286 309 300 284 312 280 257 283 289 268 267 268 270 291 284 289 265 305 275 262 249 267 274 265 233 288 242 236 250 285 230 237 226 269 253 234 236 247 228 218 219 234 228 205 225 231 235 256 208 213 248 235 196 229 209 214 222 227 200 231 204 233 192 197 211 207 199 202 197 219 193 211 216 184 191 175 222 180 173 182 186 195 173 180 207 203 197 184 192 211 178 183 180 182 185 171 157 160 179 160 178 190 177 194 185 190 168 153 157 157 144 159 160 166 147 170 168 178 155 146 173 171 169 141 150 138 166 155 161 158 156 146 150 166 140 145 154 156 143 144 155 137 160 141 131 135 133 142 138 127 119 115 124 133 140 127 122 150 132 127 141 130 120 139 124 134 127 111 134 126 124 123 137 126 145 121 126 113 104 115 121 116 129 122 107 115 138 142 102 123 132 110 132 103 103 110 94 98 101 89 116 120 91 115 87 127 93 107 110 128 95 101 108 91 90 95 97 91 105 104 96 102 116 110 99 77 100 99 85 94 105 99 101 88 107 105 72 83 91 85 91 102 86 102 89 88 100 86 94 98 80 84 100 80 83 86 72 80 69 64 103 97 90 60 92 86 81 74 67 72 77 84 75 73 88 76 93 85 66 81 91 88 84 84 65 64 66 64 74 64 77 80 60 67 64 64 88 71 72 69 64 95 60 75 63 75 74 60 66 62 60 60 74 66 70 60 76 60 56 50 82 66 63 54 62 57 65 63 58 69 66 69 72 55 62 55 67 76 78 76 87 74 84 66 55 71 68 78 66 77 95 77 80 85 76 74 86 79 83 84 92 83 86 85 85 106 82 105 91 94 95 102 94 94 93 80 84 75 89 77 81 74 86 75 81 74 75 69 83 81 76 83 84 492 68 78 77 80 70 73 69 60 71 80 88 59 65 65 53 59 45 58 45 53 59 52 66 50 59 53 78 51 64 54 53 71 57 50 45 47 47 46 46 55 44 56 35 54 54 37 47 50 42 58 56 56 30 39 51 47 58 35 53 45 59 29 52 41 36 46 53 100 574 34 24 35 37 33 30 38 29 42 33 34 25 43 39 42 21 27 27 31 38 31 32 26 26 35 30 27 27 29 30 32 33 22 33 23 29 28 28 16 30 39 26 35 17 36 34 23 27 21 30 27 23 32 24 42 22 32 28 29 42 29 33 27 26 35 35 34 31 38 26 31 30 27 45 26 40 37 28 44 36 30 46 45 36 38 31 32 32 36 38 28 41 29 31 50 33 43 38 39 40 45 42 37 30 38 39 40 48 36 44 41 42 35 45 46 42 37 40 35 47 44 58 50 43 55 47 62 43 38 35 44 41 45 47 48 37 33 37 34 27 46 24 25 27 16 38 23 29 25 22 28 13 21 18 22 17 21 26 22 29 19 19 14 26 14 21 20 19 20 14 17 11 11 19 19 14 14 21 15 20 19 22 27 18 24 24 14 19 28 15 25 19 15 21 27 18 18 21 13 23 22 17 20 13 20 21 21 21 12 12 16 13 12 16 22 13 25 22 14 18 29 18 20 17 21 19 12 23 22 17 25 8 14 16 13 17 19 20 22 13 15 17 8 16 20 14 14 8 15 15 13 15 14 13 17 20 12 13 16 10 20 10 14 11 13 10 12 16 7 11 13 18 11 14 9 9 12 10 7 13 12 8 22 9 12 9 13 8 11 12 12 8 6 18 16 18 8 11 8 8 9 10 8 9 6 11 16 13 4 12 10 6 11 11 6 4 6 13 4 10 7 6 11 13 6 7 9 12 9 6 6 8 9 14 9 7 12 11 12 4 1 12 9 9 9 11 8 5 9 8 14 5 5 4 11 6 14 6 13 8 7 9 10 12 11 7 5 14 12 10 15 11 10 13 13 8 7 10 11 13 11 10 10 6 10 8 4 5 9 12 8 12 13 7 10 13 11 12 12 6 13 10 7 8 7 6 8 12 5 9 8 13 5 15 10 8 7 8 12 11 16 15 13 12 8 14 8 4 8 8 9 10 6 10 9 6 5 9 11 10 10 5 13 9 12 11 10 9 9 6 11 6 5 8 7 8 2 14 9 9 7 13 8 7 2 3 3 4 3 3 3 7 4 3 8 4 3 3 9 7 4 1 6 5 6 4 3 4 4 6 7 3 4 4 1 5 7 5 6 3 8 4 7 3 2 3 5 5 4 8 3 6 2 2 3 5 6 3 6 2 5 5 7 3 0 4 3 4 5 2 3 5 2 7 3 3 2 6 3 5 7 7 5 7 5 5 2 3 7 5 8 5 4 2 3 2 3 6 4 2 9 4 6 4 2 1 1 1 7 5 3 3 3 0 5 1 5 1 2 3 5 6 5 4 0 6 5 3 5 0 4 3 1 1 4 2 4 4 6 1 5 1 3 10 5 2 6 3 0 2 5 3 5 4 3 2 2 2 1 1 1 5 1 1 4 4 1 3 2 2 5 0 4 1 1 2 1 3 4 1 3 1 4 9 5 2 1 1 3 1 0 2 4 0 1 2 2 2 6 3 5 1 5 0 0 1 1 3 2 1 3 3 1 1 3 3 3 4 1 3 2 1 2 2 3 8 2 2 1 4 4 2 2 0 3 2 3 4 2 6 4 1 1 6 3 2 3 3 1 2 1 2 3 2 3 5 2 5 0 3 0 3 0 2 0 8 4 2 2 1 3 6 0 1 2 2 0 1 0 5 1 2 3 1 1 0 2 6 2 3 1 2 1 1 0 2 2 3 1 1 4 1 2 1 4 2 0 0 0 4 3 0 3 1 3 4 2 3 0 0 1 1 4 4 2 1 1 4 3 1 1 3 2 2 1 3 1 2 2 1 2 2 2 2 1 3 2 3 1 7 2 0 1 3 4 
];
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
 491713 421585 70128
 428532 363361 65171
 428792 363783 65009
 413663 353600 60063
 454761 383886 70875
 469969 407903 62066
 434717 372170 62547
 685806 565668 120138
 421172 362406 58766
 467551 397446 70105
 666757 559084 107673
 462324 395556 66768
 610425 511005 99420
 426343 369850 56493
 452983 388271 64712
 644154 543265 100889
 466638 401675 64963
 618265 520703 97562
 462779 400789 61990
 595402 501777 93625
 476280 414311 61969
 594555 502349 92206
 485674 420736 64938
 591647 500331 91316
 459318 398660 60658
 625414 529403 96011
 571149 485006 86143
 449938 394152 55786
 579728 493204 86524
 408002 361516 46486
 118423359 113203005 5220354
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
63 247 1 1
15 27 0 0
21 103 0 0
21 49 0 0
18 50 0 0
11 37 2 0
15 63 9 0
99 61 5 4
82600 53 12 3
631711 85 28 6
1373444 104 60 13
2881068 105 162 67
5330700 185 1562 451
9583783 293 6536 2386
14947332 560 6555 3411
19538577 1461 6695 4262
19441540 3379 9289 7908
15801678 6699 13875 13441
9958223 10590 20197 20112
4418350 15247 26369 26394
1287478 20346 32204 32559
241135 27594 38362 38886
61548 36549 44689 45670
54457 46068 52276 52777
60979 56574 60179 60896
69160 66870 69366 69629
78148 77524 78271 78951
86963 88582 88321 89008
96101 98917 97644 99178
106394 109184 107425 108948
114699 117956 116548 117314
122478 125686 123213 124406
127574 131693 129375 131266
131406 136040 133746 135038
133857 138725 136728 136697
134847 139732 135482 137511
133171 137141 134580 136766
131163 134363 132397 132988
129366 131684 130485 130832
127411 128944 128609 129439
127339 127895 127124 127866
127479 128097 127415 128172
128703 129319 129042 130315
132153 132066 131965 133206
135902 136224 135872 136729
140415 140944 139852 140738
143266 144269 143293 144548
146348 145774 145935 146919
146163 146239 146193 147807
145496 145577 144758 145180
140869 141379 140287 140741
133819 135733 133578 134363
125784 127309 125608 126687
116279 118290 116961 117446
106159 107878 105881 107201
95497 97243 95730 96617
86133 87327 86655 87350
77727 78381 77643 78482
69900 71055 70004 70526
63065 64163 63698 63594
58804 59347 58582 59319
56281 56371 56308 56423
51811 51956 51521 51535
48484 48762 48681 48986
45894 46279 46456 47055
45890 46115 45830 46046
45612 45135 45079 45702
46073 45742 45936 45834
45370 45275 44995 45218
44467 43721 43811 44774
42773 42337 42054 42620
41138 41376 41362 41698
39706 39918 39352 39948
36924 36839 36820 37257
32884 32713 32668 33530
29042 29101 29138 29354
24989 24547 24659 24725
17991 18063 17993 18264
14695 14663 14810 14771
11075 11126 10958 11172
6711 6671 6606 6768
4019 4350 4297 4249
231 219 237 277
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
