A = [
2368783 2172534 41776738 1289562 1444365 1277815 1267745 1414324 1218219 1160645 1184147 1016787 1012277 1009425 1018932 1016849 1016139 1012842 1007676 1000608 993283 989702 983141 987490 1012272 1432975 1445448 1487686 1918748 1927721 1965645 1988207 1982582 2009925 2002891 1992005 1985965 1971016 1965328 1939204 1925614 1919916 1894523 1874285 1857105 1848788 1824842 1807290 1794158 1772819 1752160 1733407 1718076 1700045 1683374 1660815 1645265 1626774 1608544 1590629 1576551 1559927 1542272 1526907 1506779 1494510 1479176 1461213 1449399 1432525 1420015 1409656 1397793 1387338 1378125 1368127 1355372 1343403 1327540 1314869 1298789 1283222 1267552 1253455 1237611 1222339 1207993 1190737 1175591 1160182 1147115 1127849 1116265 1099788 1087805 1073593 1059389 1045064 1032482 1020158 1005861 994799 979393 966307 954540 942152 929458 917255 907490 894086 880004 869285 859221 846650 834918 823284 811205 801411 788521 779419 768222 756550 748003 736432 725134 713833 706747 696230 685988 677278 666817 656680 647544 639349 630604 620942 613002 602812 594465 586067 579206 570809 561481 552712 546264 536622 529815 522044 515037 507643 499568 493016 486072 478343 471080 465651 458203 450991 445070 436531 432026 424202 418865 413061 406455 399261 394338 388710 384740 377969 371260 366084 361297 357038 351610 343661 339932 335145 330146 325553 319803 315510 310019 305768 301261 297141 291181 288001 283957 278911 275956 270324 267392 262452 258201 255454 252135 247194 242698 239628 236786 232390 228244 226377 221742 219508 216036 212648 208827 206607 202730 199814 196751 194091 191847 188251 185131 181665 179234 177039 174830 171320 169149 166244 164223 161225 159292 156455 153917 151461 149315 146811 145736 142530 140693 138174 136005 134087 131881 129856 127714 125530 124329 122043 120248 117858 116762 114837 112771 110765 109209 108468 106549 104669 103180 101571 99778 98981 97577 95482 93260 92318 91030 89611 88457 86626 85181 83347 82499 81254 79735 78422 77344 76551 75094 73696 72638 71559 70216 68810 68043 67080 66198 64768 63675 62946 61913 60646 59719 58828 58102 56585 56418 54851 54374 53346 52467 51613 50930 49783 49142 48722 47689 47202 46187 44907 44556 43680 43046 42744 41874 40954 40339 39634 39005 38475 37582 37473 36797 36031 35561 35094 34270 33988 33125 32816 31986 31490 31078 30978 29893 29767 29108 28671 28091 27644 27398 26607 26116 26251 25902 25349 24818 24326 24058 23768 23223 22880 22342 21947 21533 21419 20702 20702 20377 19908 19726 19290 18828 18696 18338 18046 17870 17278 17153 16982 16846 16540 16306 15798 15536 15371 15151 15056 14588 14405 14195 13898 13775 13470 13377 13230 12946 12500 12433 12182 12035 11858 11499 11497 11309 10937 10766 10764 10662 10386 10460 10122 10106 9656 9641 9372 9384 9210 9096 8772 8783 8449 8490 8327 8066 8055 7923 7621 7680 7474 7390 7316 7366 7017 7055 6974 6732 6608 6492 6380 6414 6195 6218 6027 5934 5743 5808 5659 5486 5449 5360 5321 5120 5075 5016 4976 4838 4801 4782 4721 4576 4542 4482 4371 4297 4291 4192 4026 4139 4042 4006 3845 3873 3792 3761 3756 3665 3558 3482 3449 3540 3436 3354 3291 3270 3123 3072 3106 3053 3092 2998 3009 2828 2879 2682 2767 2722 2765 2574 2558 2572 2489 2483 2475 2496 2453 2463 2328 2326 2226 2314 2272 2177 2112 2153 2059 2100 1993 2077 2022 1977 1999 1921 1898 1882 1870 1778 1752 1736 1742 1855 1699 1634 1667 1594 1633 1560 1611 1571 1519 1545 1488 1489 1441 1474 1485 1437 1379 1385 1382 1338 1364 1357 1346 1271 1331 1254 1222 1272 1218 1247 1202 1165 1169 1188 1140 1138 1130 1156 1127 1123 1132 1064 1057 1049 1070 1060 1043 1020 993 1001 942 1019 977 939 921 935 934 927 890 900 960 855 923 879 852 853 809 812 847 778 843 816 813 804 804 753 784 803 765 781 711 748 748 727 752 723 723 683 675 736 669 702 655 684 672 645 664 622 660 648 645 633 642 592 578 613 624 619 590 549 624 593 570 563 567 560 586 616 540 554 549 569 542 546 510 519 528 507 498 583 565 500 510 535 509 488 536 470 473 507 502 483 472 490 430 476 458 480 487 494 440 442 433 465 424 406 472 426 400 435 455 413 411 411 436 444 355 394 395 385 397 375 405 426 436 402 429 370 396 378 368 391 375 350 367 371 378 391 386 360 324 366 362 363 372 353 344 361 322 338 381 296 351 357 316 362 305 331 324 336 294 342 314 343 314 316 295 305 326 340 288 322 290 304 293 316 251 325 318 285 280 288 304 276 286 293 302 306 312 295 275 298 275 279 243 278 285 249 287 289 269 288 266 243 261 237 281 269 274 238 259 233 268 247 256 239 252 279 264 249 238 244 245 228 246 211 254 258 232 238 245 215 208 210 245 217 224 235 223 225 196 230 213 218 194 214 228 188 221 196 217 206 197 196 200 190 159 198 208 244 194 204 210 192 198 181 178 182 197 200 174 181 189 180 202 159 178 182 166 175 171 183 170 203 179 169 177 158 195 184 163 162 138 159 188 148 162 149 155 160 180 166 149 161 155 151 169 142 138 129 159 163 148 159 166 145 155 146 128 129 166 148 140 146 143 137 123 149 121 159 139 146 121 146 135 135 155 129 137 137 162 117 132 136 121 152 118 132 133 138 124 133 113 96 114 143 109 130 141 135 126 118 118 109 123 108 106 123 126 129 115 98 110 109 124 121 128 113 122 114 140 99 125 111 131 115 108 130 126 104 108 123 109 109 89 109 103 89 111 117 87 101 102 104 94 98 117 90 113 105 126 107 109 98 69 95 91 92 101 99 99 84 95 105 94 91 81 90 91 87 78 97 97 97 77 100 79 83 83 80 69 75 85 74 89 81 60 75 81 76 63 82 69 80 83 74 98 98 87 81 84 73 89 74 66 85 76 95 78 68 56 76 76 86 73 62 92 88 73 62 85 63 70 66 67 64 64 68 63 66 73 55 64 79 73 75 65 85 83 67 69 57 73 60 64 67 67 77 63 67 70 58 74 62 53 71 52 79 75 64 62 71 61 65 65 48 65 50 51 63 68 65 57 56 62 61 61 55 39 46 52 51 57 46 48 50 48 42 55 53 52 57 59 49 55 65 52 47 47 41 45 49 55 58 38 43 50 53 49 41 45 47 55 39 59 36 43 37 41 50 46 47 35 38 34 40 41 38 28 51 38 34 45 49 37 46 37 53 44 47 42 41 42 34 38 41 35 39 42 42 35 28 37 45 48 50 38 41 31 35 39 43 35 34 33 34 34 33 44 34 32 51 44 36 30 29 33 36 44 34 29 28 31 39 39 27 23 26 33 30 43 29 37 35 26 23 33 32 28 35 27 36 33 36 27 29 29 42 27 22 28 37 21 24 29 35 22 33 29 29 30 23 23 32 18 29 20 29 29 30 21 21 26 26 21 35 30 18 34 25 22 20 21 23 24 25 23 35 31 26 26 31 18 23 31 25 23 25 26 26 28 24 17 29 23 24 25 20 20 24 25 25 14 24 23 23 29 28 25 26 27 20 21 23 19 21 20 25 27 25 29 13 20 19 20 22 23 28 11 25 25 21 25 19 20 23 17 17 18 26 25 26 14 20 20 9 20 15 13 23 12 25 14 22 14 19 17 22 11 15 15 15 26 17 18 13 17 17 12 19 10 18 13 20 18 17 18 13 10 16 14 14 17 11 19 10 16 14 11 14 23 9 9 17 17 10 13 11 8 19 12 11 15 7 18 14 14 15 15 20 17 15 16 16 9 9 11 18 12 19 9 10 10 15 14 14 14 9 9 11 12 16 17 13 14 14 10 9 8 13 13 10 19 11 7 10 9 15 12 13 12 7 8 12 13 10 13 7 10 12 10 10 13 12 14 13 11 6 12 6 10 7 12 7 13 12 12 10 10 10 8 10 21 9 11 9 11 16 10 9 11 10 9 10 14 3 8 12 3 10 9 8 13 9 12 9 4 6 7 5 4 7 7 9 4 9 12 8 14 10 9 11 12 5 13 10 10 11 7 8 14 9 12 10 10 4 10 9 3 9 9 6 11 10 11 15 7 4 8 5 3 8 9 11 7 7 7 5 14 7 9 11 8 4 8 8 6 10 7 7 6 4 5 3 3 4 7 9 9 9 11 4 8 8 4 9 4 8 12 10 6 7 9 10 4 6 6 10 7 8 4 9 8 7 6 8 7 7 2 5 3 5 12 12 6 5 7 7 4 5 9 3 11 6 7 10 11 11 5 8 6 7 3 3 10 4 7 7 4 5 3 1 3 8 5 3 7 3 4 5 4 3 4 5 4 4 3 3 7 7 5 4 3 1 3 12 5 5 6 6 2 5 2 2 2 5 7 9 4 7 8 6 3 5 4 7 3 2 3 4 5 3 7 4 5 6 6 3 5 5 4 1 4 2 4 5 3 1 1 5 6 2 5 4 8 4 5 7 3 5 3 4 6 1 4 3 2 4 3 2 5 3 3 5 8 5 3 6 3 6 4 5 7 6 0 4 4 6 3 4 4 3 2 3 3 3 4 7 2 2 2 4 2 1 2 3 5 6 2 3 3 2 7 1 8 3 9 3 4 4 2 3 3 2 3 3 1 5 3 4 4 2 4 4 3 3 2 2 1 1 3 0 1 4 4 2 5 3 2 3 3 2 4 4 3 4 2 3 1 0 3 3 4 4 2 2 2 5 2 3 1 1 1 5 4 5 3 1 3 0 2 3 3 4 3 1 2 2 3 5 2 4 3 2 3 5 3 3 6 1 1 4 3 5 0 0 2 2 0 0 1 1 1 2 2 2 4 5 2 2 3 1 3 3 4 2 2 4 0 0 1 1 2 3 1 2 2 2 2 1 3 0 2 0 1 4 2 3 2 3 0 4 2 3 2 1 3 3 3 2 2 0 0 1 2 4 1 2 3 4 0 2 2 1 4 1 1 2 1 2 0 1 2 2 5 1 1 3 0 0 2 2 0 2 4 4 1 1 2 1 2 0 2 2 4 0 0 2 1 0 0 3 3 4 4 3 0 1 1 3 2 0 2 0 1 1 1 1 4 1 0 1 0 1 3 2 2 1 0 2 0 2 2 
];
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
 1657565 1433610 223955
 496174 431540 64634
 2951136 2551633 399503
 1657499 1457248 200251
 3579301 3111210 468091
 1371647 1227801 143846
 2351761 2089429 262332
 6292078 5513204 778874
 1837228 1645018 192210
 4052291 3624514 427777
 6246464 5488366 758098
 2208352 1970859 237493
 4716836 4202481 514355
 4971130 4399642 571488
 1549524 1383122 166402
 5643718 5076639 567079
 5859416 5217888 641528
 1742222 1529404 212818
 6907949 6316539 591410
 11368212 10199446 1168766
 289407 254529 34878
 12738934 11683865 1055069
 17064760 15452767 1611993
 860544 760518 100026
 6 6 0
 27189596 24767083 2422513
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
232 328 0 3
48 55 0 1
65 89 1 2
85 99 3 3
60 94 17 16
454 122 1370 123
144124 181 3993 533
739305 207 4852 1126
1589687 299 6118 1746
2605957 376 7920 2847
3616962 536 8772 3940
5400178 809 10621 5329
7293425 1243 12159 7173
9472445 2067 14024 9504
10632830 3373 15679 12417
10884612 5554 18915 16266
9320968 8326 22185 20771
6618525 10904 27755 27130
3785638 14904 35493 35399
1551252 21491 44819 45108
425343 30998 54708 54917
111677 41905 65599 65660
80932 56665 77899 78579
91137 74273 90778 91383
106163 94238 106174 106125
121030 115146 122740 123036
137906 137594 140701 140117
157058 158222 158942 159696
175492 179072 178147 178032
192828 199322 196321 196275
209644 216007 212705 213356
222892 230597 226748 226837
233776 242591 237533 238336
241802 251570 247305 246036
246820 255905 251495 251761
250311 257726 253270 253619
249330 258151 254050 254111
251595 256914 253154 253877
250232 256041 252436 252840
251590 255029 252822 253044
254578 257448 254447 256423
259054 262220 259657 260925
267269 268941 267766 269557
276877 279216 277885 278793
290170 292438 291187 292024
305613 306848 305888 307205
321657 323095 322487 322313
337145 338061 337194 337085
348778 350486 350134 350415
358813 359510 359560 358992
361625 363213 362437 361853
358969 361181 360023 360501
349542 351415 351107 351947
337894 338030 338647 338406
318334 320097 319552 319617
296337 297058 296162 297898
269507 270477 271277 270972
243286 245120 243075 243539
216552 217919 218175 217126
192551 194606 194098 194486
174124 174705 174118 173772
154024 154156 154799 154468
140660 140909 141334 141300
132942 133253 133061 133411
127534 128450 127780 127692
125623 125622 125847 126027
131250 132326 131648 131886
154863 153008 153591 153810
140585 141387 140655 140370
147279 147666 148060 148318
137881 139110 137360 137855
122122 121571 120802 121843
129295 130107 130031 130573
86850 86966 86976 86332
71990 71873 72155 72279
58255 58092 57372 57692
47410 47605 47511 47154
40931 40899 41130 40869
34771 35575 34822 34754
27535 27519 27676 27607
17399 17531 17705 17440
8444 8379 8493 8378
407 399 422 406
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
