A = [
338303 323821 1715348 369764 359616 365857 360375 379467 375340 377501 391076 381028 387049 388386 391132 391422 390920 391749 392590 388926 386565 384761 384815 388866 409730 995700 1032744 1041361 1633846 1672457 1703676 1723975 1722730 1766985 1761742 1738230 1726140 1700386 1674706 1643451 1624740 1610380 1589129 1571157 1556563 1533122 1508589 1491280 1463736 1436580 1415332 1391020 1375932 1359638 1339637 1318930 1300214 1282056 1257050 1231188 1212098 1189960 1174200 1157528 1140057 1122082 1104353 1086770 1069917 1051868 1035635 1023234 1008141 998670 989301 975040 962009 950983 932075 916754 898301 883414 867555 850393 835672 818977 805234 787774 771890 757657 739131 723907 709168 695120 680350 667691 653486 642733 629412 614845 603265 589210 576211 564831 552687 541925 530637 519717 509374 499273 488435 476415 467208 457323 446439 437256 428668 419185 411274 402082 393363 384376 375378 367979 359623 351841 344486 335867 329188 322208 314871 308644 301328 295173 288428 281679 275503 269468 263969 257850 252352 246773 241570 235399 230542 223746 220512 216839 210971 206005 201851 197180 192275 188687 183457 180066 175439 171783 167790 163964 160898 156671 153564 150301 146906 143072 139110 136347 133695 130922 128096 125207 122804 118957 117271 114568 111361 109875 107241 104199 101865 100007 97811 95651 93592 91336 88725 87591 85192 83824 81848 79856 78060 76405 75081 73075 71737 69520 68217 66716 65462 63788 62107 61174 59744 58447 57094 55952 54901 53809 52496 51234 50411 48945 48224 46948 45795 44759 43998 42782 42150 41088 40305 39527 38559 37593 36600 35921 35619 34592 33626 32863 32524 31739 31048 30562 29608 28767 28526 27424 26840 26708 26147 25694 25200 24652 24294 23415 23098 22965 22222 21677 21263 20785 20515 20058 19803 19363 18875 18479 17941 17853 17487 16774 16732 16426 15828 15548 15163 15040 14530 14314 14217 14050 13420 13091 12966 12613 12307 12055 11870 11593 11223 11076 10932 10590 10455 10250 9830 9727 9401 9357 9148 8921 8650 8650 8459 8235 8095 7708 7519 7516 7401 7098 7025 7008 6733 6756 6573 6342 6354 6371 6015 5990 5731 5683 5582 5438 5270 5203 5069 5057 4957 4866 4582 4606 4495 4260 4418 4195 4125 4116 3892 3850 3770 3755 3552 3658 3490 3446 3447 3340 3293 3173 3164 3042 3062 3083 2914 2875 2765 2761 2717 2626 2674 2619 2561 2491 2321 2415 2295 2316 2227 2129 2185 2061 2041 2088 1955 1927 1882 1921 1853 1821 1821 1725 1698 1773 1668 1676 1621 1535 1593 1531 1521 1463 1491 1470 1363 1327 1325 1348 1256 1260 1255 1257 1140 1182 1138 1151 1111 1123 1085 1079 1095 1039 1111 975 954 1013 1019 934 899 922 956 916 953 894 964 884 860 851 794 784 806 783 788 811 749 734 689 702 716 711 701 643 635 630 680 638 661 666 590 651 613 556 631 579 561 565 540 553 526 544 527 561 533 485 490 488 489 527 465 473 496 461 403 429 463 436 449 453 462 400 429 444 398 419 412 397 429 422 376 439 361 364 385 378 364 325 376 381 358 349 358 328 375 321 306 315 359 342 314 336 320 354 299 331 294 302 272 306 300 284 287 306 275 258 263 259 279 289 275 282 247 284 276 267 262 266 252 249 274 265 262 213 254 243 239 232 231 225 262 235 249 222 222 224 218 224 256 229 219 230 208 206 228 235 232 230 214 203 203 218 197 229 205 209 212 211 210 204 194 214 183 201 184 168 202 159 184 172 203 157 193 175 163 159 162 160 198 163 192 161 173 184 173 154 174 164 152 189 185 163 172 173 164 154 184 171 162 172 167 155 169 131 160 145 157 166 160 155 140 162 151 126 144 160 130 148 149 133 135 157 146 140 135 119 156 152 144 132 131 131 128 135 104 111 122 127 126 116 121 143 108 125 106 124 110 111 92 131 113 114 104 120 134 117 109 108 122 124 114 116 114 103 106 104 93 98 90 112 112 104 90 118 118 116 121 99 96 98 102 113 114 108 110 102 110 116 99 97 90 95 119 96 114 114 90 117 103 103 110 88 103 87 85 90 120 85 92 103 99 86 103 113 93 107 101 94 95 83 99 95 91 90 108 99 101 97 92 88 83 85 76 76 78 91 83 93 79 74 64 76 70 75 80 81 56 86 77 79 78 70 78 76 80 57 84 60 84 79 71 79 64 80 73 69 76 61 71 71 63 67 73 59 76 76 67 41 59 57 52 62 63 62 58 63 68 57 62 57 72 60 55 66 59 59 56 54 63 57 55 69 74 60 51 61 57 58 50 51 49 52 64 59 56 46 43 51 45 43 54 52 55 53 62 55 59 61 51 42 53 58 36 52 39 32 56 46 50 57 49 55 43 43 62 46 51 57 39 43 41 71 50 54 45 50 54 49 55 50 41 39 55 36 48 49 45 40 38 40 56 51 42 44 50 44 44 42 34 41 50 45 42 36 41 44 38 35 41 36 38 31 38 21 31 30 56 37 55 36 44 34 29 40 28 32 36 30 38 38 39 48 45 29 30 36 34 35 35 37 38 26 41 32 27 25 33 31 35 27 39 23 30 30 30 40 28 37 26 26 36 30 27 21 36 34 37 26 28 28 33 27 36 31 28 27 14 33 20 28 25 21 25 31 35 31 25 25 24 21 27 24 21 25 31 26 30 24 23 23 25 28 33 36 26 23 13 25 24 28 24 18 25 18 28 26 22 21 25 31 12 20 18 23 13 24 21 18 24 20 28 23 18 21 21 23 26 26 23 19 29 31 13 18 30 21 12 24 20 17 16 19 16 25 24 11 16 16 9 15 18 15 19 15 12 19 13 12 14 17 21 12 10 15 15 19 15 17 18 16 15 17 18 18 15 12 18 18 14 10 14 17 6 17 18 16 15 15 23 17 22 21 27 15 18 24 14 20 15 16 22 10 11 16 12 10 12 10 13 10 14 15 14 6 11 17 12 14 13 21 12 9 13 10 13 9 11 15 12 9 10 20 15 9 7 9 15 13 14 10 14 11 10 14 11 12 10 10 9 12 7 5 10 7 6 9 13 16 5 4 6 10 9 12 11 11 10 13 6 6 8 10 6 11 9 9 5 20 12 8 7 14 11 11 11 10 8 6 15 10 13 9 9 4 9 12 8 11 10 10 7 7 3 8 5 6 9 8 6 7 10 13 7 5 12 6 9 14 9 14 6 11 10 17 8 17 8 6 3 11 8 10 15 11 7 5 5 10 8 12 5 8 13 8 5 9 9 6 10 8 10 5 15 15 11 5 3 14 8 11 7 4 8 6 4 9 3 7 6 8 8 15 7 9 4 8 9 9 6 10 5 11 8 6 10 8 11 7 7 7 10 7 8 0 2 7 2 6 9 2 7 3 5 4 9 6 11 10 10 6 7 6 6 1 6 6 5 3 5 7 9 7 6 8 6 2 3 9 3 7 8 9 6 8 3 5 3 5 3 4 6 1 7 4 2 9 2 3 3 6 4 4 7 6 9 10 9 7 7 5 5 4 7 10 5 4 9 4 11 5 3 7 3 5 4 4 4 2 9 3 10 3 5 2 6 7 3 6 5 5 6 3 10 4 5 3 4 4 4 1 3 7 6 3 1 5 4 4 2 6 5 1 4 3 4 1 3 5 3 7 6 5 9 3 0 4 4 7 9 4 6 4 4 4 4 6 3 3 3 6 3 2 3 5 4 3 4 8 5 2 3 8 2 2 5 4 4 2 3 4 4 3 4 3 4 6 5 4 3 5 4 0 2 4 2 4 1 5 3 2 2 5 3 4 5 3 4 6 1 1 5 3 2 5 2 6 7 1 0 4 5 2 4 5 3 6 4 1 1 3 4 6 2 3 2 3 5 0 3 1 6 1 3 4 6 3 6 4 5 2 3 3 8 3 1 1 4 2 1 2 6 4 1 3 5 1 1 4 2 1 2 1 3 2 4 1 0 1 1 1 3 3 1 6 1 2 3 3 4 2 2 2 0 4 3 3 1 2 3 4 5 2 3 1 0 3 3 2 1 3 2 4 1 0 1 0 0 2 0 3 2 2 1 1 2 2 1 2 1 1 1 3 3 1 3 2 3 3 4 1 1 1 1 1 3 2 2 0 4 0 3 4 1 2 0 6 0 2 0 3 3 2 1 1 3 2 0 2 0 1 1 1 2 3 4 4 4 1 2 1 4 3 4 3 1 3 2 3 2 3 4 0 2 4 0 1 2 2 3 2 3 3 5 1 1 1 0 1 3 0 3 2 0 1 4 3 1 1 2 3 1 3 4 0 3 2 0 2 0 1 0 0 1 1 0 0 2 1 5 0 1 0 0 0 1 3 2 2 1 0 0 1 3 2 0 3 1 2 0 1 1 1 2 0 2 1 0 2 0 1 2 0 1 2 1 0 0 2 1 2 1 2 1 0 1 3 2 2 1 0 4 1 0 2 3 0 2 1 2 2 2 0 1 1 3 2 1 1 2 0 0 4 1 1 2 3 2 1 0 0 1 0 0 2 0 0 2 2 1 0 1 2 1 2 3 0 0 1 0 1 1 5 3 0 0 0 0 0 0 4 0 1 1 0 2 0 1 1 0 1 2 2 2 1 0 0 0 1 0 0 0 2 0 1 0 0 0 1 1 0 1 1 0 0 1 1 0 1 2 0 1 1 0 0 0 0 0 2 0 0 0 2 1 1 0 0 1 0 1 1 2 0 0 1 0 1 0 0 0 1 0 0 2 1 0 4 1 1 1 3 2 2 0 3 1 1 1 1 1 0 0 1 1 1 1 1 3 1 1 0 0 0 0 1 1 0 0 1 1 0 1 3 1 1 0 0 1 0 0 0 1 1 1 0 0 0 0 1 1 0 1 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 2 1 0 1 0 0 1 1 0 0 2 0 0 0 0 0 0 1 1 
];
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
 304738 246278 58460
 320723 261816 58907
 2020573 1631508 389065
 405816 334351 71465
 2355190 1914761 440429
 563344 466560 96784
 512999 425943 87056
 4193557 3462623 730934
 918122 767340 150782
 1456677 1220932 235745
 4263499 3532185 731314
 1524262 1277521 246741
 1857534 1554532 303002
 3183390 2640991 542399
 1056738 888763 167975
 1322436 1105661 216775
 3495955 2915028 580927
 1229828 1029650 200178
 256188 213911 42277
 6592396 5539002 1053394
 257999 215721 42278
 900871 755538 145333
 9429928 7979487 1450441
 763682 642387 121295
 7 6 1
 14964050 12761437 2202613
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
3 28 0 0
1 4 0 0
0 7 0 0
2 23 0 0
0 14 0 0
5 20 325 10
566 32 934 77
5726 26 1167 248
29738 43 1551 474
110199 58 2225 896
268567 91 2614 1383
565095 156 3530 2296
922984 277 4845 3620
1248091 570 6881 5917
1260847 1190 9989 9182
1023707 2220 14731 14252
644153 3474 20458 20106
343975 5176 27444 27407
169393 8469 35946 36361
89490 13646 45638 45507
67463 22075 56566 56425
72531 32603 67274 67438
85993 48341 81139 81334
101738 67993 96294 96824
118411 90393 113354 113216
136657 115638 132468 131931
156146 140665 151397 151417
175810 163978 172254 171974
193233 184475 189516 190232
207478 202121 204364 206207
219092 215063 217376 217267
225021 223527 225097 224926
229028 229196 228581 229402
231235 231320 232000 232470
232799 232534 232213 232657
233653 234048 233762 234652
233725 234268 235346 234403
236433 237071 236165 236849
238941 240015 238466 238457
240791 241680 241561 241534
244490 245555 245673 246589
251625 251874 250938 251073
258358 258255 258737 258680
267937 268536 268802 267878
278659 279784 278907 279324
292108 292649 290980 291967
304197 304425 305845 304830
316258 316456 316120 315855
327271 327567 327153 326892
334627 336052 335286 335689
340055 340769 341048 340085
341068 342205 341251 341008
337990 339108 338953 337132
332017 334397 333186 332461
322097 323151 321170 321971
308379 310220 308690 309551
291311 292072 292429 292381
269630 272424 271248 271547
246522 247292 247156 247320
223685 224088 224424 225292
202039 201970 202753 202698
183218 184884 184444 184412
164667 164512 164550 164584
150980 150606 151339 150881
141476 142369 142055 141820
136818 136925 135907 136870
134690 135243 135270 136582
133885 133802 132700 134004
128781 129156 128057 129198
131085 130697 131262 131134
127230 127929 127240 126946
119310 118949 118972 119049
111010 110787 111150 110853
94702 95485 95116 95414
79757 80007 80037 79837
64337 64078 64276 63787
46983 47213 46991 47011
29847 29572 29578 29731
22468 21970 21946 22304
15414 15445 15333 15253
8655 8541 8581 8471
3720 3681 3732 3579
144 154 132 148
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
