A = [
442465 461621 1867850 381898 396101 358260 347358 352032 340939 319320 317059 317570 313193 309463 304530 300232 296318 294379 290207 288663 287601 283924 282798 282000 282544 335933 335366 336196 389253 390699 393180 394697 396737 398833 399326 396818 392978 389799 388515 383001 381329 379893 377628 376987 375971 371243 369164 364713 360718 359642 355410 352532 351413 349190 347003 344636 342427 338832 336584 333017 330531 328041 326830 326755 321602 320663 319460 316634 312652 309543 307101 304633 302140 300183 298597 296465 294242 291803 288209 286147 282827 280442 278145 276473 274461 272181 269342 267657 266121 262841 259486 257667 255422 252914 250913 247932 247632 245153 243004 240519 237435 236762 232722 231327 229435 226820 225851 224658 220898 220300 217888 214527 214240 210429 209711 208326 204811 203441 202043 199809 198375 196108 193611 192140 189937 188838 187168 184754 183579 181789 180442 178302 176208 174726 173193 171019 169157 168420 165845 164341 162605 161485 159108 157538 155930 154861 152924 151820 150146 148826 147957 145942 144843 142617 140550 139825 138744 137446 135762 133841 133690 131205 130057 128775 126839 125446 124306 123745 121663 120250 118981 117911 115849 115360 113554 112153 111569 109856 108234 107308 105963 104745 103802 102895 101183 100396 98877 97908 97109 95204 95140 93595 92292 91496 90552 88794 88135 87255 86327 85612 84121 82891 82000 80908 80360 79275 78279 76624 76134 75162 74163 73665 72727 71187 70504 69473 68820 67737 67125 66095 65297 64945 63892 62391 62475 60953 60289 60081 58771 58050 57270 57010 55675 54964 54112 53976 52760 52282 51503 51057 50382 49406 49053 48274 47510 47134 46433 45862 45175 44393 44157 43813 42970 42186 41928 40970 40564 40065 39438 38911 38688 37225 37116 36776 36334 35775 35206 34900 34352 34035 33627 33136 32635 32125 31752 30938 30799 30348 30146 29740 29268 28938 28949 28161 27663 27272 26577 26612 26133 25690 25512 25244 24562 24748 24241 24036 23640 23108 22856 22744 22085 21641 21405 21094 20770 20679 20458 19650 19761 19403 19400 18871 18886 18367 18499 18235 17771 17610 17157 17022 16682 16463 16117 15854 15807 15510 15182 14724 14592 14599 14383 14055 13876 14039 13458 13496 12885 13042 12841 12492 12334 12348 12101 12037 11722 11636 11534 11408 11071 10958 10885 11545 10901 10475 10377 10316 11377 9913 10189 9866 9671 9467 9274 9356 9039 8880 8923 8680 8601 8427 8370 8101 8048 7839 7890 7700 7546 7577 7444 7148 7074 6886 6930 6825 6981 6960 6782 6924 6701 6643 6741 6369 6400 6284 6254 6122 5857 5590 5455 5559 5387 5488 5397 5415 5301 5030 4944 5038 4972 4859 4825 4652 4550 4730 4625 4557 4428 4431 4378 4248 4177 4203 4092 4144 4107 3858 3924 3874 3875 3929 3749 3646 3625 3581 3592 3523 3529 3460 3465 3350 3449 3286 3226 3144 3245 3048 3115 2924 3017 2974 2955 3022 2802 2773 2818 2709 2756 2702 2663 2558 2483 2533 2397 2441 2427 2410 2405 2396 2315 2389 2266 2301 2227 2219 2266 2082 2210 2131 2034 1919 2064 2087 1947 1968 1924 1998 1960 1910 1936 1932 1887 1836 1862 1880 1775 1810 1687 1764 1731 1710 1633 1694 1652 1645 1634 1684 1585 1595 1660 1577 1530 1508 1497 1576 1563 1454 1544 1430 1454 1444 1428 1373 1450 1375 1417 1284 1286 1307 1308 1364 1298 1283 1233 1326 1296 1261 1239 1206 1183 1174 1244 1135 1188 1135 1148 1208 1138 1069 1167 1052 1108 1088 1095 1091 1092 1082 969 1015 1077 1006 946 1033 1043 1043 1027 953 923 926 917 976 975 1012 946 920 985 909 958 889 915 861 874 874 884 832 830 854 818 808 794 793 770 828 794 835 770 794 837 772 754 760 788 722 750 798 790 683 715 743 704 708 761 750 690 684 675 668 694 682 678 693 639 689 687 648 656 615 639 660 613 617 612 627 589 611 580 592 571 578 514 572 574 575 537 602 574 561 555 508 538 546 520 509 527 535 490 517 474 527 499 536 486 514 487 441 506 469 518 458 450 447 493 460 453 467 401 451 486 455 478 464 457 429 447 432 431 396 437 403 397 410 429 420 402 421 369 414 429 379 392 417 399 417 410 407 422 432 395 415 421 423 397 375 374 405 378 324 366 327 402 386 380 380 368 366 372 382 385 371 385 385 396 376 381 379 382 366 381 380 413 425 380 374 444 497 379 389 382 404 341 354 335 337 337 303 293 341 325 303 288 306 294 305 277 327 310 280 305 298 297 275 322 281 290 293 287 336 278 322 311 275 280 315 271 273 287 278 290 323 258 280 271 321 251 289 280 299 301 283 280 253 271 229 241 226 224 234 234 229 208 239 231 231 229 228 267 228 220 252 229 235 239 214 235 221 225 223 260 189 231 217 213 229 231 212 253 227 202 218 191 200 216 252 221 210 239 217 203 184 196 204 201 202 175 174 167 184 191 169 164 167 194 176 155 146 176 172 158 160 175 169 154 176 175 193 180 158 178 193 185 197 175 178 170 165 151 174 151 186 183 177 166 158 145 143 155 153 166 142 152 170 117 140 162 122 150 166 185 175 141 159 147 136 160 145 141 140 149 165 164 150 155 147 157 133 168 159 150 149 161 132 147 134 102 125 110 100 119 113 122 117 119 124 116 111 109 125 129 176 109 117 108 120 130 124 131 118 125 147 110 129 120 94 113 104 118 83 107 94 92 103 92 98 87 85 107 89 85 97 82 79 101 93 92 89 86 83 92 84 80 98 97 90 88 119 92 87 91 81 95 104 98 98 85 71 82 72 90 77 78 85 85 78 88 83 88 70 89 86 100 107 70 69 102 90 96 81 76 81 80 84 105 78 84 87 89 91 82 80 76 77 90 74 67 64 70 72 85 82 79 76 77 78 66 66 74 86 100 83 78 84 66 75 108 73 58 94 75 69 75 73 80 75 82 70 61 65 54 85 49 60 66 68 69 65 69 81 61 75 79 71 64 70 70 68 54 75 75 56 59 67 67 73 66 57 57 67 60 57 64 55 53 47 73 62 76 67 56 52 57 75 66 70 59 72 50 63 72 71 73 63 54 54 60 65 44 65 63 54 51 48 61 44 60 52 47 61 65 62 64 64 60 68 62 72 55 60 48 52 59 53 58 52 56 52 71 54 70 55 51 67 62 57 65 56 58 55 72 51 67 54 68 62 68 58 57 57 61 96 73 66 48 74 63 57 45 61 67 45 48 39 47 51 67 32 44 44 40 38 44 41 55 47 34 42 36 60 61 47 42 38 44 50 38 30 40 36 43 35 41 35 35 48 42 39 32 30 36 25 34 45 34 32 37 34 53 28 42 32 33 37 30 37 29 38 36 48 37 30 37 39 38 38 35 39 33 35 33 31 26 35 33 39 45 34 34 26 36 25 31 29 29 29 34 31 39 34 39 45 36 31 33 46 52 42 36 49 41 54 37 45 43 39 35 28 34 31 31 46 36 35 34 32 26 24 30 31 30 25 34 22 26 32 24 20 25 28 14 21 28 22 23 18 24 36 25 25 21 31 23 30 27 27 29 16 20 19 34 25 27 24 18 15 32 21 25 26 26 23 19 18 31 24 21 20 21 27 20 18 21 25 14 17 20 15 13 18 15 19 26 10 21 14 18 14 14 24 20 14 25 20 17 10 28 19 18 19 27 22 33 19 14 17 18 21 29 31 30 30 29 25 25 17 25 20 23 37 23 46 28 28 27 32 31 30 33 32 32 17 33 35 23 30 18 33 37 30 23 24 23 27 26 17 32 19 23 15 15 16 14 14 18 25 19 10 19 22 30 17 16 16 15 14 25 22 16 14 18 10 11 13 19 18 12 17 9 10 14 6 14 14 11 20 16 15 13 20 24 13 16 9 8 14 12 15 17 15 9 13 15 13 12 13 18 12 15 15 14 10 13 12 10 10 15 11 10 14 12 14 9 13 13 17 18 12 15 13 12 9 8 15 13 14 14 11 7 16 11 16 13 9 14 12 17 10 17 8 11 11 7 11 13 12 12 12 7 11 10 8 17 9 10 13 12 11 13 11 11 13 17 14 11 10 6 4 11 8 12 10 9 12 12 5 7 8 13 8 10 12 12 18 16 14 20 11 12 9 6 10 10 20 14 17 12 21 14 18 14 11 11 17 13 13 8 12 11 13 12 14 14 8 7 9 7 11 9 4 11 10 16 7 11 14 11 7 11 9 8 11 11 10 10 6 10 13 9 9 9 14 12 8 9 9 7 8 12 7 8 11 13 8 14 13 8 5 5 12 10 10 11 10 11 5 9 11 16 10 10 17 15 10 15 14 7 8 10 14 8 12 9 6 9 8 7 8 13 7 5 11 8 12 7 9 17 9 5 9 5 7 8 6 3 10 6 9 6 12 6 9 7 15 13 10 12 9 9 15 6 5 9 5 3 8 10 10 6 12 8 7 9 7 11 8 5 13 8 11 9 4 7 8 11 9 9 5 9 11 4 5 6 4 6 10 5 8 6 5 5 4 7 3 11 5 3 7 7 7 6 7 4 9 9 9 6 6 11 5 8 5 5 8 2 11 6 7 8 6 6 1 10 2 5 11 4 8 6 3 5 9 8 5 10 3 4 6 4 9 5 3 11 11 8 6 4 7 8 8 11 6 5 3 8 3 6 10 5 10 5 5 7 7 8 6 4 9 9 9 5 6 4 14 8 10 7 11 13 4 5 5 3 9 9 10 9 17 10 4 7 12 9 9 12 2 3 5 7 6 7 7 10 7 12 9 14 10 5 10 8 2 4 6 6 9 5 9 12 6 10 4 8 5 5 10 10 7 6 5 7 10 8 7 6 11 7 5 8 8 7 7 8 10 6 8 7 6 9 7 7 5 5 7 4 3 5 8 5 10 5 8 7 4 8 6 2 7 4 10 8 5 4 3 8 3 3 6 4 6 7 11 9 4 8 5 9 4 9 10 4 7 9 4 6 14 9 10 10 5 5 5 10 6 11 7 9 5 7 5 7 10 5 2 8 7 8 5 6 8 7 5 6 7 
];
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
 751187 315857 435330
 55749 22804 32945
 100031 42218 57813
 546757 249961 296796
 372240 169383 202857
 620593 286761 333832
 1133457 523349 610108
 915255 398271 516984
 574421 261576 312845
 1327609 626460 701149
 508638 216203 292435
 35281 15038 20243
 1192932 556461 636471
 19043 8194 10849
 32976 14041 18935
 1636072 787835 848237
 34871 15322 19549
 406583 173326 233257
 2268860 1166902 1101958
 409407 179757 229650
 10 5 5
 15784775 8441296 7343479
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
40 68 0 0
41 6 0 0
105 14 0 0
158 12 1 0
114 18 0 0
72 18 20 1
170 46 63 6
882 45 81 20
5170 58 101 46
20643 75 187 67
47303 81 212 91
101456 120 284 163
205093 153 429 248
427239 229 571 389
808064 362 769 654
1383610 564 1091 1008
1758778 898 1534 1414
1595250 1440 1971 1982
1091349 2337 2619 2618
568805 3224 3261 3192
214297 3931 3654 3602
48455 4804 3749 3788
10742 4793 3932 3870
7504 4339 4059 4053
6585 4550 4137 4232
6054 5077 4219 4210
5912 4667 4436 4513
5796 4609 4662 4819
5958 5051 5059 5022
6085 5336 5389 5226
6379 5614 5787 5764
6926 6105 6123 6210
7714 6979 6739 6749
8553 7549 7323 7422
9002 8171 8338 8363
9707 9221 9256 8972
11016 10219 10199 10485
12162 11572 11670 11511
13264 12923 13014 13027
14825 14739 14890 14926
16693 16745 16724 16763
19029 18793 18921 18950
21387 21472 21174 21276
24468 24336 24405 24078
27334 27582 27526 27614
31149 31359 31662 31725
35109 35089 35700 35263
39758 39485 39320 39185
43753 43664 43745 43886
48565 48260 48265 48097
52586 52746 52686 52241
56044 55979 55774 55957
59016 59257 59108 58263
61640 61889 61732 61948
64949 64289 65464 65238
66981 67266 67036 67021
70932 71204 70775 71229
74763 74350 73798 74116
77643 76668 77631 77261
80529 80197 80204 81242
83485 83773 83471 83589
83941 83554 84200 83999
80731 80224 80923 80119
68978 69887 69705 69349
51362 51718 52047 51011
28706 28963 28785 28090
11138 11488 11294 11155
5315 5440 5567 5156
4269 3860 3785 3902
3364 3561 4574 3133
2283 2553 2450 2463
2257 1543 1696 2015
142 153 69 37
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
