A = [
1696284 2405074 31486155 1275873 1346560 1308481 1270550 1343386 1296835 1265526 1256153 1221586 1227201 1209155 1194990 1193641 1167076 1165541 1164228 1140042 1127639 1123689 1115778 1108837 1101725 1103199 1100840 1092623 1092290 1076799 1074473 1075152 1056543 1050899 1048096 1046843 1040626 1030890 1030132 1028843 1021177 1025062 1023213 1022318 1023456 1019470 1010347 1014296 1011397 1002257 1000747 990748 993543 991761 981978 985152 978973 979363 972452 963676 963273 955335 947071 939332 933576 927438 919769 911522 903621 898579 894799 892293 888201 885574 884261 881156 877435 873397 866077 861242 857653 853670 845916 840923 834707 830654 819549 804139 797073 788307 785287 778142 775363 769769 763664 759425 753532 749347 746308 739342 736874 731714 728032 723378 717678 714527 710323 703959 700593 697073 690408 688544 684319 678067 673089 669676 666628 661395 656976 654238 648161 642467 638464 633867 627194 622708 617531 613697 609100 603063 599500 595187 588876 586186 581217 576156 570583 566153 562505 558050 552936 548215 544523 537263 533127 529292 524050 519785 514629 510586 504776 499441 494896 489725 486034 480268 474872 470444 466737 462543 457692 452876 448921 444237 438864 434448 431524 426901 421536 417454 412570 409015 405993 401196 397150 392995 389311 384636 380738 377246 372916 370091 365223 361971 358282 354895 350365 347833 344290 339896 335894 332678 328514 324754 320999 317591 314717 310638 307465 304482 301691 296786 293496 291432 286918 285160 280536 277261 274633 270370 267645 264447 261554 258459 255902 253152 249769 246596 243876 240312 238245 235370 233606 230100 225879 222885 220663 217497 214124 209888 207819 205703 202509 199797 197746 194455 191931 190726 186995 184659 182284 179049 177878 175313 173208 170688 168106 165898 163713 162684 159597 158012 154761 153413 150961 149157 147265 145506 142400 140979 139283 136903 135764 133307 130933 129989 127795 126833 124599 122821 121178 119893 117711 116282 115060 112444 111305 110522 108037 106791 105241 103524 102809 100538 99752 98025 96331 95445 93309 92476 91373 89521 88561 87294 86214 84558 83499 81601 80666 79700 79272 77281 76071 74959 73520 72718 71638 70522 69785 68699 67306 66262 65670 64014 62944 62378 61430 60353 59365 58928 57853 57124 56157 55025 54438 53670 52621 52006 50728 50097 49595 48579 47914 46931 46300 45467 44931 44160 43490 42820 41778 41431 40469 39828 39331 38789 38115 37564 37120 36050 35325 35541 34686 34129 33439 32868 32413 31947 31406 30888 30184 29887 29413 28940 28656 27475 27613 27131 26606 26139 25452 25051 24929 24548 24116 23624 23152 22897 22760 22223 21600 21576 21221 20794 20122 19882 19305 19202 19001 18556 18420 17959 17909 17567 16998 16632 16665 16176 16173 15749 15584 15328 14938 15051 14774 14202 14136 13806 13716 13176 12939 12740 12462 12412 12178 11848 12053 11527 11223 11187 11062 10823 10646 10465 10436 10121 10144 9463 9640 9379 9205 9026 8893 8958 8824 8308 8307 8301 8110 7883 7903 7636 7504 7240 7406 7133 7207 6911 6929 6771 6651 6524 6503 6290 6009 5971 5993 5771 5623 5780 5555 5518 5441 5335 5067 5072 5079 4943 4880 4763 4609 4703 4565 4289 4346 4272 4188 4251 4116 4021 3892 3850 3774 3798 3609 3632 3542 3421 3433 3481 3364 3256 3167 3089 3129 2993 3141 2933 2874 2864 2868 2747 2740 2732 2629 2647 2648 2527 2507 2457 2520 2368 2273 2217 2243 2215 2126 2159 2083 2172 2008 1940 2069 1967 1946 1923 1912 1940 1865 1797 1775 1703 1742 1653 1628 1598 1644 1595 1515 1468 1566 1523 1539 1421 1461 1398 1402 1397 1361 1329 1362 1334 1295 1242 1295 1212 1250 1185 1197 1208 1131 1138 1221 1095 1081 1074 1085 1080 1047 1073 1070 1017 959 1044 964 992 970 894 932 904 922 870 852 836 871 864 811 829 849 796 769 845 746 766 798 754 767 757 796 721 758 721 703 696 699 632 643 696 639 674 673 676 665 592 586 622 656 589 629 583 608 608 577 558 540 580 603 560 569 540 543 545 556 508 513 526 537 545 526 490 490 499 520 490 497 456 469 528 524 469 439 429 443 414 488 409 423 438 450 462 410 449 418 421 436 444 439 429 402 382 421 412 411 425 404 409 397 388 382 387 367 383 378 373 393 364 364 366 369 386 324 376 363 378 374 336 363 340 346 363 334 331 344 333 346 361 329 349 337 350 335 321 324 349 332 315 317 304 293 308 286 283 292 280 311 280 327 298 327 312 298 278 274 295 247 271 305 293 283 292 284 263 303 277 282 273 247 273 250 240 271 258 268 246 263 290 240 244 276 239 236 249 243 264 261 273 231 240 270 237 244 233 255 216 242 232 239 227 219 244 198 236 210 223 231 238 212 192 235 223 208 219 216 219 224 192 216 226 221 222 193 200 238 197 214 203 205 208 212 203 184 207 182 224 202 168 177 181 197 145 169 185 199 190 167 197 171 182 165 169 200 170 206 163 176 195 187 160 186 150 185 154 160 164 174 169 172 166 178 180 168 167 160 161 165 170 146 159 142 155 158 148 142 151 178 137 166 174 144 149 139 157 141 154 142 150 158 139 145 156 156 126 127 155 156 166 135 150 151 147 125 158 144 144 139 129 146 119 111 137 151 129 119 108 142 136 137 116 139 141 116 136 118 116 141 128 116 112 115 123 120 133 117 99 127 123 128 118 125 115 115 131 120 134 125 112 110 113 124 121 115 126 116 108 122 110 117 110 116 107 101 104 113 125 104 110 109 97 105 95 97 109 117 92 108 110 111 109 95 105 99 100 98 100 98 97 98 112 113 85 93 100 91 95 117 84 98 96 111 83 92 81 85 93 103 101 71 91 80 88 76 89 88 93 89 95 82 81 97 79 92 74 77 83 85 84 69 85 74 77 74 75 74 65 61 79 73 94 67 85 77 77 69 70 77 77 88 68 86 92 72 70 72 66 89 65 68 85 75 59 65 72 66 75 74 67 65 76 70 83 68 57 67 62 71 74 64 64 66 63 69 56 59 60 62 63 75 65 60 55 61 67 58 60 70 60 72 58 59 58 61 57 57 67 51 56 59 60 58 64 64 70 52 56 45 51 71 61 53 50 57 63 48 63 43 47 56 50 45 48 54 52 42 62 54 61 58 55 55 55 50 65 61 78 64 77 81 52 74 48 54 69 79 75 75 82 74 90 59 88 83 95 91 91 89 88 94 95 90 76 87 112 141 133 102 116 101 78 87 79 94 80 75 81 78 58 66 58 49 71 48 54 44 55 30 45 58 50 30 36 42 37 29 27 40 42 46 40 36 30 33 27 40 33 41 38 43 46 51 42 28 37 49 33 27 28 30 52 52 41 39 33 46 44 49 46 54 48 48 38 49 73 60 57 68 57 69 91 75 75 59 68 71 62 69 71 70 84 87 70 60 64 42 44 46 42 43 39 35 28 32 20 35 37 27 34 26 36 32 30 31 34 27 33 23 28 33 27 35 39 34 25 23 25 27 33 23 22 31 27 20 22 29 26 22 21 26 24 24 34 14 19 26 19 21 18 21 22 27 35 25 25 29 25 28 31 16 25 19 21 25 19 24 33 25 20 26 22 32 19 17 24 24 19 19 15 19 32 25 26 18 24 28 20 21 30 18 23 22 21 12 10 15 17 27 21 24 18 18 20 23 19 24 19 27 23 15 22 23 16 16 22 22 12 14 17 16 14 13 21 19 20 15 14 15 14 20 13 14 17 19 11 20 11 15 13 13 15 21 19 20 18 23 13 26 17 20 25 14 16 17 14 22 15 25 20 13 13 20 14 12 11 16 18 23 11 15 12 16 18 9 17 18 13 15 15 11 11 13 18 18 17 31 21 22 26 17 23 17 28 25 23 24 28 40 27 36 28 17 23 25 30 34 21 24 26 25 20 29 13 16 19 18 16 25 29 13 19 15 17 12 17 26 24 30 23 28 25 18 17 28 8 20 13 14 21 11 14 14 12 9 13 12 13 13 8 6 11 14 8 16 15 14 11 16 9 17 11 13 6 13 9 12 16 12 12 17 11 6 20 20 9 14 8 17 16 15 18 11 17 20 18 13 14 17 22 11 17 21 12 9 18 10 11 10 10 17 18 16 13 13 12 12 20 16 20 18 24 19 12 12 11 9 13 6 11 7 9 10 10 9 13 12 13 10 8 13 8 9 16 11 4 9 11 9 4 6 3 6 11 8 5 9 8 11 10 6 9 14 4 7 9 9 5 3 6 11 12 3 7 2 10 10 6 12 4 6 3 6 14 7 6 5 8 8 8 2 7 10 7 9 5 8 4 3 7 9 6 9 9 6 11 6 7 6 8 7 5 6 8 9 6 7 8 6 8 3 6 6 6 10 7 7 3 11 11 7 6 8 8 7 9 2 10 11 7 8 8 6 7 13 6 9 10 6 13 5 6 3 5 7 3 8 5 6 11 7 9 8 4 7 5 5 10 9 9 3 6 2 8 7 8 7 6 7 6 2 7 4 6 4 4 2 1 8 3 6 1 9 5 2 3 1 6 3 9 7 2 5 7 4 4 5 6 6 3 3 3 3 5 3 5 5 3 7 5 2 6 1 6 7 8 4 3 3 5 2 1 7 5 6 4 3 9 3 6 5 1 4 5 3 4 5 2 5 2 5 3 4 4 2 3 3 2 2 4 1 3 2 10 3 7 4 5 3 0 1 6 5 6 3 5 4 6 5 2 3 4 1 3 2 4 9 3 6 2 3 4 5 1 5 3 4 3 3 2 3 4 3 3 2 2 4 6 2 1 3 2 3 2 1 5 3 2 4 0 3 3 4 3 1 1 4 4 2 2 2 1 3 4 2 3 1 4 6 1 3 2 3 4 3 2 5 4 5 4 7 4 3 2 2 2 2 3 2 4 4 3 3 0 4 5 3 4 0 5 1 3 5 5 0 4 3 1 0 6 4 5 2 3 4 2 2 3 1 5 2 1 1 4 0 2 4 1 1 2 4 2 1 2 2 1 0 3 2 1 3 1 1 0 1 4 6 2 3 3 4 1 2 3 0 4 2 7 0 0 1 2 1 1 1 1 1 4 6 4 2 3 4 1 1 4 2 0 7 3 3 1 4 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
 398965 375738 23227
 1188622 1140111 48511
 1142590 1096720 45870
 418137 396472 21665
 1451746 1395518 56228
 450258 428262 21996
 1150331 1106201 44130
 422357 395588 26769
 1134598 1093011 41587
 1130656 1089001 41655
 465679 440838 24841
 1091483 1052372 39111
 446306 423961 22345
 1178882 1139092 39790
 1057913 1022206 35707
 415348 395132 20216
 1078105 1042876 35229
 446919 426744 20175
 1055000 1021599 33401
 441345 422625 18720
 984835 953974 30861
 1079814 1045095 34719
 367349 353250 14099
 1009547 977448 32099
 362414 349753 12661
 1010472 978299 32173
 901910 873268 28642
 455860 442206 13654
 962235 933122 29113
 361126 350871 10255
 84999725 83891535 1108190
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
95 95 3 3
63 17 1 0
77 33 0 0
77 30 1 0
36 30 3 1
52 40 6 3
1847 68 30 7
11112 61 92 32
54788 65 438 89
231665 80 698 206
746969 119 828 289
2149264 142 1092 493
5017590 213 1358 645
10022404 334 1599 970
15358670 550 1860 1208
19954956 687 1983 1593
20624925 932 2214 1970
16811394 1334 2445 2384
9929613 1644 2909 2878
3674944 2113 3494 3526
712558 2630 3981 4114
57734 3207 4589 4754
7449 4045 5059 5369
6569 4937 5731 5647
6975 5718 6372 6134
7594 6539 6838 6624
8041 7546 7373 7293
8862 8276 8165 8126
9473 8954 8697 9096
9726 9185 9313 9547
10196 9568 9544 9813
10642 9830 9862 9950
10142 9884 9799 9861
9800 10218 9512 9862
9644 9902 9463 9745
9481 10444 9512 10039
9258 13712 9223 10520
9183 9031 8987 8995
9240 9335 8962 9061
9030 9070 9080 8984
9356 9127 9230 9127
9382 9437 9351 9440
9992 9874 9569 9682
9929 10081 10118 10188
10737 10699 10382 10338
10824 10715 10655 10545
11019 10799 10941 10752
10854 10958 10830 10885
10662 10745 10843 10821
10429 10355 10556 10723
9979 9936 9991 9802
9136 9177 9126 9257
8218 8422 8308 8211
7520 7429 7421 7407
6434 6490 6580 6556
5725 5868 5638 5690
5115 5040 4898 5095
4422 4416 4483 4396
3884 3893 4009 3926
3518 3411 3521 3524
3325 3328 3381 3300
3155 3194 3177 3175
3077 3168 3077 3159
3088 3168 3212 3034
3214 3159 3121 3186
3373 3283 3182 3228
3469 3489 3575 3647
3817 3850 3818 3807
4186 4238 4125 4210
4402 4555 4489 4546
4841 4901 4873 4881
5178 5221 5263 5298
5619 5573 5649 5590
5689 5618 5665 5660
5170 5216 5254 5263
5041 5139 4980 4909
4623 4426 4437 4317
3727 3685 3570 3586
3219 3153 3309 3262
2469 2428 2455 2396
1565 1556 1566 1565
849 847 823 846
49 40 64 53
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
