A = [
190797 192376 4132250 198550 203823 203538 210102 233782 238556 253409 274455 286320 304228 317560 331760 345327 355445 364243 372650 377984 379537 381706 383470 384479 387207 400242 400204 401242 411630 410855 410389 410381 409833 408303 408072 404933 404615 403882 404469 398304 398143 397475 393839 392958 390068 387915 385956 384622 383303 379674 378946 375177 373073 372460 367659 366527 365034 363610 358945 357669 355546 352979 349588 347502 344637 342756 340164 337430 333645 332787 331566 328762 325961 325013 322105 320572 318327 316395 313324 310362 308261 306213 303016 299518 296853 294619 290857 288845 285246 282622 279152 277409 273977 271371 267293 264999 261338 260374 256682 254213 251350 248384 246448 243934 240829 239073 235254 231955 230958 228683 225948 223105 218949 217052 215150 212662 210243 207770 205462 202725 199031 197296 195232 193458 189460 186979 184539 183139 180470 178009 176520 173669 171576 168913 166560 164119 162216 160340 157899 156076 153377 151634 149848 147501 144642 143166 141272 139152 137681 134948 133263 131166 130176 127695 125912 123928 121640 120431 118631 116610 114985 113944 111608 109999 108168 107059 104815 103193 101810 100911 98112 97204 95259 94370 93037 92015 90267 88224 86969 85625 84221 83590 81893 81072 79171 78127 77468 75575 74440 73461 72222 70833 69549 68447 67485 66715 65338 64433 63017 62702 61170 60267 58641 58336 57318 56663 55309 54802 53585 52314 51836 50857 49896 49260 48313 47333 46514 45849 45364 44600 43499 42946 42097 41399 40568 39887 39078 38761 37864 37128 36429 36062 35237 34783 34383 33406 32904 32433 31585 31446 30461 30287 29608 28837 28634 28151 27733 27067 26757 26200 25815 25303 24993 24555 24289 23623 23231 22865 22681 21923 21759 21104 20612 20336 20013 19487 19303 19029 18977 18092 17992 17678 17361 16708 16596 16128 16123 15631 15483 15329 15007 14373 14123 13797 13705 13543 13104 12894 12571 12434 12316 11932 11964 11210 11213 10928 10693 10644 10450 10069 9961 9812 9737 9305 9200 8993 8692 8634 8415 8331 7907 8035 7830 7537 7385 7300 7151 6973 6969 6696 6530 6602 6493 6368 6054 5946 5867 5784 5637 5424 5428 5241 5249 4989 4949 4907 4801 4598 4459 4401 4269 4252 4175 4026 3949 3961 3896 3741 3652 3707 3606 3402 3345 3409 3212 3123 3133 3125 2988 2970 2821 2814 2765 2705 2621 2616 2537 2418 2463 2344 2334 2335 2235 2219 2088 2015 1971 2015 1972 1953 1903 1857 1765 1714 1732 1677 1665 1574 1434 1503 1496 1470 1401 1334 1386 1313 1295 1283 1207 1227 1218 1214 1115 1136 1117 1075 1089 1019 1016 994 994 1002 890 907 896 865 825 854 845 786 797 734 761 758 723 676 687 678 613 646 619 594 603 598 619 574 544 566 523 494 479 486 468 472 463 453 427 396 409 444 399 413 414 347 388 360 360 343 341 330 321 295 330 308 306 303 290 292 279 281 271 246 254 215 255 258 265 225 221 234 201 218 205 194 179 206 187 194 196 198 159 170 175 171 173 163 143 153 176 155 154 148 152 146 143 136 142 115 131 106 129 124 113 150 111 110 102 111 104 118 91 107 98 103 80 107 83 85 92 87 82 79 82 67 65 77 68 85 77 80 74 71 79 67 73 75 71 64 63 60 55 53 65 59 63 68 54 39 70 54 60 54 56 52 51 56 48 49 47 51 53 63 46 49 50 45 39 48 30 45 42 46 40 37 32 51 30 39 41 36 44 33 53 38 36 25 45 37 45 28 22 26 30 36 34 27 36 32 34 29 32 35 35 38 19 35 20 26 32 33 28 25 21 28 31 19 37 22 26 19 33 15 29 23 18 20 32 18 23 18 31 28 15 23 19 30 25 23 14 38 21 23 17 29 25 28 18 16 10 10 12 12 26 22 20 22 21 13 19 16 18 15 18 20 19 17 23 22 17 18 23 22 14 20 9 8 19 20 18 17 14 14 13 14 9 20 15 23 17 10 15 14 15 5 10 7 14 26 10 11 17 14 13 16 16 15 15 17 12 19 14 15 11 12 9 11 15 11 13 17 12 16 15 13 7 15 17 13 11 6 12 12 13 12 11 6 16 14 11 10 6 9 13 13 6 9 13 12 8 8 10 9 8 7 10 8 11 11 6 9 9 8 4 8 11 12 6 12 11 6 10 8 13 9 4 5 7 6 13 8 9 8 10 7 10 4 9 9 14 7 5 7 9 5 10 5 10 10 12 7 6 8 7 3 5 8 6 7 8 13 2 12 5 12 7 9 7 7 6 8 7 4 8 7 6 11 4 8 5 6 3 6 6 5 3 6 4 10 5 3 5 8 7 6 4 4 5 5 8 6 5 3 4 1 6 5 8 3 3 6 3 5 4 6 6 8 7 4 6 6 7 6 6 5 2 1 8 4 7 5 4 7 4 6 3 4 6 6 6 3 5 10 5 2 6 8 7 4 3 4 2 4 7 5 4 3 5 5 7 4 1 3 4 4 3 4 5 4 4 5 3 5 4 9 7 3 1 6 3 8 3 6 8 3 5 7 4 2 8 3 0 5 3 5 3 4 2 3 1 4 4 6 1 5 1 5 7 0 1 2 1 3 5 2 2 4 5 5 3 3 7 0 1 2 4 2 2 1 2 3 3 2 3 5 4 2 1 4 3 0 2 4 4 0 0 6 2 3 3 4 4 2 3 2 3 2 1 2 2 1 2 0 1 2 2 0 2 0 1 2 4 1 0 4 5 2 1 0 1 0 3 1 4 5 1 3 3 2 4 4 0 1 2 2 2 3 2 4 4 6 1 2 1 3 7 2 1 2 2 0 0 2 3 0 3 1 4 1 2 3 2 0 1 4 1 3 3 1 0 4 1 3 1 2 2 2 4 0 1 1 5 2 1 2 3 1 2 0 3 2 3 2 1 3 0 2 2 1 1 3 0 1 1 3 2 3 4 0 1 0 2 2 0 0 3 1 1 0 2 2 2 0 3 1 2 0 3 3 1 1 2 2 2 3 0 2 5 1 0 2 1 1 3 1 4 0 1 1 1 0 1 1 0 3 0 0 2 0 2 2 0 1 5 3 1 0 1 3 1 2 1 0 1 2 2 2 0 1 1 2 3 0 0 0 1 1 0 2 2 4 2 0 1 0 3 2 0 1 1 1 1 1 2 0 2 0 1 0 1 1 1 0 0 1 1 0 1 0 0 0 2 2 1 0 3 1 0 0 0 0 1 2 0 1 2 1 1 0 3 0 3 1 0 1 0 1 0 0 0 1 2 1 3 0 1 0 1 0 1 0 1 0 0 0 0 1 0 1 0 1 1 2 2 1 0 1 1 0 3 0 1 1 1 1 1 0 0 1 0 1 1 1 1 0 0 0 0 0 0 0 1 0 1 1 0 1 2 0 0 1 0 0 1 1 1 0 3 0 1 0 1 1 0 0 1 1 1 1 1 0 0 0 0 1 1 0 2 0 0 0 1 1 0 0 1 1 2 0 0 1 1 0 0 1 1 2 0 1 0 0 2 0 0 0 0 0 0 0 0 2 0 0 0 0 1 1 2 1 0 2 1 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 2 0 1 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 1 1 1 0 0 0 2 0 0 0 0 1 0 0 1 2 1 0 2 1 1 1 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 1 0 0 0 0 0 4 1 1 1 1 0 0 0 2 0 1 1 0 0 0 1 0 0 0 1 0 0 0 2 0 2 0 0 0 1 0 0 1 0 0 1 1 0 0 0 1 0 1 1 0 1 0 0 1 1 0 0 0 1 1 0 1 0 0 1 0 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 1 0 1 1 0 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 1 0 1 1 0 2 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 
];
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
 73359 64613 8746
 76998 69460 7538
 682279 599687 82592
 117439 109744 7695
 752638 675614 77024
 211426 201494 9932
 169047 161181 7866
 1179667 1098261 81406
 402384 389370 13014
 647018 628375 18643
 1377599 1302849 74750
 699602 679830 19772
 535540 518789 16751
 1320303 1259088 61215
 479082 467566 11516
 277273 268089 9184
 1399755 1345454 54301
 272057 263506 8551
 53744 51842 1902
 2858722 2781971 76751
 64291 62233 2058
 207771 201675 6096
 5025104 4925680 99424
 219719 214614 5105
 3 3 0
 9507502 9366090 141412
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
1 4 0 0
0 1 0 0
0 4 0 0
2 2 0 0
3 1 0 0
9 3 24 0
1144 6 55 7
9094 0 72 16
44528 3 100 21
160682 8 112 25
401285 5 150 39
944734 8 200 77
1893588 19 246 104
3407169 35 300 161
4740792 65 363 242
5387049 142 516 373
4563864 207 652 581
2855562 273 843 833
1271538 393 1181 1194
331606 615 1507 1667
40411 887 1922 1930
4080 1178 2254 2242
2971 1717 2637 2685
3285 2281 3047 3095
3803 3097 3539 3730
4278 3622 4128 4138
4858 4540 4635 4827
5450 5034 5281 5412
6007 5720 5762 5739
6386 6227 6205 6488
6895 6653 6703 6749
7124 6937 7001 6991
7190 7279 7404 7181
7396 7431 7478 7406
7464 7464 7453 7508
7592 7659 7590 7606
7903 7905 7772 7900
7881 7775 7941 7795
8259 7960 8011 8129
8153 8130 8109 8086
8298 8255 8393 8103
8650 8612 8584 8690
8676 8843 8806 8863
9164 9294 9224 9160
9581 9651 9685 9725
9994 10219 10156 10122
10463 10677 10588 10418
11105 10978 10993 11211
11097 11485 11379 11545
11818 12161 11684 11630
12123 12072 11992 12126
12036 12196 12113 12279
12114 12088 12260 12332
11794 11878 11996 12143
11764 11617 11411 11415
11192 11014 11329 11311
10528 10583 10508 10593
9867 9848 10012 9749
9020 8975 8826 8865
8145 8244 8095 8228
7379 7327 7430 7450
6724 6806 6603 6647
6066 6210 6046 6024
5701 5631 5417 5505
5339 5280 5201 5239
5113 5090 5083 5080
5008 5221 5151 5059
5122 5045 5071 5024
4920 5031 4968 4915
5030 5027 5013 5109
5009 4936 5044 4975
4647 4685 4644 4841
4415 4468 4464 4629
3961 3942 3977 3920
3408 3372 3371 3511
2874 2927 2823 2972
2257 2320 2288 2276
1518 1540 1564 1525
1274 1225 1238 1247
992 1013 1021 1002
610 589 558 588
306 304 332 350
7 20 20 17
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
