A = [
1699898 2409194 31534904 1278032 1350029 1311389 1273115 1346625 1299764 1268689 1259000 1224314 1229949 1212011 1197977 1196558 1169617 1168302 1166553 1142898 1130441 1126192 1118350 1111296 1104404 1105712 1103287 1094992 1094963 1079483 1076979 1077750 1059016 1053555 1050859 1049555 1043270 1033488 1032789 1031445 1023865 1027531 1025718 1024704 1025887 1021997 1012819 1016538 1013847 1004676 1003212 993324 996083 994162 984133 987330 981476 981708 974566 965772 965568 957599 949296 941516 935945 929758 922092 913632 905719 900839 896899 894317 890299 887505 886158 883227 879651 875463 868317 863256 859835 855717 848056 842822 836583 832637 821202 805911 798809 790053 787038 779924 777257 771381 765409 761147 755284 751029 747944 740900 738503 733388 729601 725146 719095 715892 711878 705501 702088 698474 691903 689969 685777 679440 674466 671097 668211 662759 658301 655653 649474 643805 639610 635073 628257 624014 618914 614980 610322 604353 600725 596427 590025 587325 582433 577222 571687 567438 563575 559096 553998 549292 545563 538248 534131 530354 525142 520847 515629 511643 505789 500557 495899 490525 487057 481206 475885 471452 467716 463328 458553 453731 449887 445209 439826 435350 432299 427698 422436 418307 413405 409933 406827 401978 397871 393842 389994 385392 381454 377945 373686 370829 365912 362687 358993 355578 351005 348397 344948 340575 336485 333336 329189 325434 321633 318224 315401 311218 308063 305025 302231 297365 293911 292021 287517 285664 281146 277788 275108 270864 268165 265061 262017 258852 256404 253541 250107 246975 244227 240687 238664 235759 234023 230466 226249 223320 221013 217860 214503 210309 208137 206097 202827 200192 198073 194842 192230 191114 187306 184942 182536 179382 178177 175785 173508 170942 168388 166200 163883 162945 159777 158295 155064 153666 151192 149387 147549 145758 142601 141214 139515 137105 135965 133457 131162 130154 128026 127070 124815 123000 121387 120133 117888 116556 115269 112626 111484 110689 108200 106943 105459 103693 102989 100706 99901 98227 96535 95613 93458 92624 91567 89706 88697 87434 86354 84703 83694 81762 80830 79814 79462 77386 76203 75089 73708 72881 71724 70546 69930 68865 67407 66383 65815 64164 63077 62488 61452 60463 59476 59072 57935 57259 56235 55159 54525 53820 52770 52165 50824 50158 49690 48653 48029 47036 46407 45574 45015 44274 43549 42906 41872 41544 40583 39864 39384 38862 38222 37675 37224 36127 35428 35653 34787 34191 33488 32984 32480 32028 31483 30927 30247 29965 29504 29002 28718 27501 27673 27173 26657 26237 25569 25087 25013 24603 24140 23666 23210 22977 22820 22252 21675 21618 21258 20848 20156 19936 19346 19252 19063 18633 18441 17985 18002 17573 17014 16640 16710 16252 16237 15816 15626 15356 14992 15102 14793 14239 14135 13871 13750 13233 13002 12760 12499 12430 12217 11876 12094 11579 11265 11209 11123 10886 10651 10499 10476 10165 10185 9499 9674 9423 9231 9051 8943 8991 8843 8334 8359 8316 8134 7915 7946 7650 7532 7290 7442 7166 7233 6966 6939 6807 6684 6537 6524 6333 6044 6008 6027 5802 5639 5822 5589 5551 5458 5356 5120 5091 5107 4967 4891 4795 4638 4733 4597 4301 4396 4314 4222 4254 4142 4056 3915 3876 3800 3818 3642 3658 3568 3433 3454 3512 3405 3285 3204 3119 3152 3039 3173 2936 2913 2904 2912 2805 2771 2765 2665 2675 2684 2548 2510 2487 2522 2395 2301 2239 2268 2238 2134 2174 2114 2176 2027 1959 2086 1980 1953 1930 1930 1941 1874 1810 1772 1698 1755 1651 1659 1611 1650 1606 1540 1490 1583 1522 1559 1416 1472 1408 1402 1399 1364 1344 1369 1353 1302 1267 1298 1216 1245 1188 1211 1216 1130 1139 1234 1115 1103 1085 1096 1084 1060 1079 1075 1021 957 1054 965 990 971 900 934 903 924 877 866 846 873 873 808 839 846 798 769 850 757 775 799 766 774 759 797 728 759 730 704 702 709 633 644 699 650 668 683 676 660 598 593 625 658 595 625 585 612 607 578 567 540 578 595 574 570 547 540 541 560 506 518 529 538 559 527 492 502 502 527 489 499 452 474 527 531 471 444 428 448 412 488 404 423 437 454 459 413 451 417 421 432 441 441 437 408 383 419 413 408 414 401 409 404 394 383 385 371 380 375 384 393 363 363 370 371 381 332 381 367 382 368 329 363 337 343 362 334 328 344 332 345 362 327 348 342 345 332 320 322 352 328 323 316 301 293 307 287 285 300 284 311 277 325 296 326 314 293 274 277 294 251 265 307 288 274 290 283 261 297 270 277 272 242 287 257 238 267 258 266 244 260 286 241 243 278 236 239 251 241 262 258 277 225 237 271 236 236 239 252 216 245 232 241 225 220 232 198 228 206 224 226 233 212 190 238 219 208 223 215 221 222 194 217 222 223 217 197 202 244 195 215 202 206 216 211 195 187 202 176 222 202 169 179 184 194 151 166 182 198 182 168 199 167 180 163 170 196 168 206 159 179 199 188 163 185 147 185 155 158 163 171 171 174 173 178 178 163 167 165 156 170 172 146 160 139 138 157 151 140 147 171 132 165 172 138 150 141 149 138 157 134 141 152 139 144 147 144 126 121 143 153 167 133 147 152 147 121 157 146 147 141 132 146 118 113 138 153 130 121 109 136 132 138 119 141 142 111 134 121 114 139 128 115 113 110 119 117 134 119 95 128 120 125 116 127 112 119 131 120 131 121 109 106 109 122 120 106 126 115 108 121 107 116 104 111 107 99 99 108 120 100 107 119 91 103 91 98 106 113 92 107 115 109 111 96 105 99 99 97 98 99 92 92 110 112 83 92 103 95 95 106 85 100 95 110 82 95 82 87 87 102 99 79 86 78 82 75 91 87 92 85 86 78 74 88 80 92 66 78 79 83 84 65 85 79 72 73 72 73 62 61 82 73 96 66 79 72 74 70 72 77 73 84 64 88 87 77 68 70 66 88 65 69 94 74 65 73 70 64 73 72 66 64 76 73 80 69 61 68 65 68 74 64 66 67 64 68 54 60 58 64 64 69 63 61 56 63 67 59 57 66 61 72 60 61 58 59 57 59 63 50 51 60 60 62 63 64 67 50 58 48 54 70 60 55 51 58 67 46 61 45 47 58 50 48 48 52 50 45 60 52 60 57 55 52 52 48 63 65 78 65 80 78 57 79 52 55 68 78 71 72 81 75 91 60 90 83 100 85 91 87 91 91 93 88 74 90 134 141 130 99 113 96 80 86 84 89 81 80 81 81 55 69 58 51 71 47 54 46 54 30 41 54 43 26 36 40 38 30 28 39 39 48 35 34 30 30 30 39 33 40 35 40 44 49 45 30 38 47 32 27 29 30 49 49 41 38 35 46 40 48 46 50 44 44 35 47 62 57 56 64 53 67 88 68 68 58 62 63 64 68 59 64 82 78 68 54 58 40 48 45 38 43 38 32 27 29 20 37 34 28 34 24 35 29 32 29 32 24 29 19 29 34 27 33 39 33 23 25 25 24 31 24 21 31 28 20 24 29 27 20 21 26 27 25 32 14 15 24 18 19 17 21 19 25 33 27 22 26 22 29 26 15 25 18 15 21 18 21 33 21 19 27 21 30 15 15 24 25 17 19 19 26 34 27 23 18 27 27 23 18 30 17 21 25 19 16 11 16 16 24 20 18 18 16 19 24 19 22 18 24 25 14 19 28 18 16 24 21 10 15 15 17 13 12 25 15 21 16 13 18 16 22 13 14 16 16 9 19 11 15 13 12 14 17 19 17 15 22 18 22 13 19 25 15 16 17 15 21 14 22 18 14 12 18 13 12 10 13 18 21 11 16 13 16 18 8 13 18 14 14 13 9 11 14 20 18 19 29 25 23 27 17 23 17 28 24 26 25 28 37 27 36 29 18 21 27 32 32 23 25 21 20 21 29 14 13 19 18 14 24 25 13 19 16 16 10 18 25 19 29 22 33 24 17 14 28 9 16 8 13 18 10 15 12 12 11 11 15 15 15 8 9 10 14 12 14 15 13 10 18 11 16 12 11 7 12 11 11 14 12 8 13 10 8 19 19 8 12 9 17 15 8 17 8 18 12 16 10 11 16 15 8 11 17 8 5 12 7 8 5 9 11 15 12 11 12 12 14 15 18 16 13 23 15 13 9 8 4 10 5 10 8 8 11 10 10 9 10 12 12 9 11 5 9 14 11 5 8 9 11 4 10 4 7 9 8 6 6 8 9 8 4 9 13 3 5 4 9 3 3 4 7 13 2 7 2 11 10 7 8 2 5 3 6 12 5 5 5 6 6 5 3 7 11 3 9 4 9 4 3 6 9 4 9 8 5 13 4 6 6 3 4 5 5 5 8 5 6 6 5 4 3 6 5 4 8 3 7 2 7 9 10 5 4 5 4 9 5 8 6 4 6 4 4 5 8 4 5 8 4 5 2 5 2 4 3 2 9 6 7 6 4 5 6 2 4 7 2 6 5 9 3 3 3 5 3 7 5 3 3 6 1 6 3 4 1 3 2 1 6 2 5 1 9 5 3 3 1 6 3 8 5 3 5 6 4 2 6 6 4 3 3 6 2 4 3 4 5 4 7 6 1 6 2 5 7 9 3 4 4 3 2 1 6 5 5 2 3 6 3 4 4 1 4 4 3 4 4 2 3 2 6 3 3 5 3 4 2 2 2 2 2 2 3 10 3 7 5 4 3 0 1 6 5 5 3 5 4 4 4 2 2 5 1 3 4 5 8 2 5 2 3 3 6 1 3 3 4 1 3 2 3 3 2 2 1 3 5 4 1 1 2 3 4 1 1 2 5 1 1 1 3 1 4 2 1 1 5 2 1 2 2 2 2 3 2 2 1 4 2 1 2 1 2 2 4 2 4 4 4 4 5 3 4 2 2 4 2 3 2 4 3 4 2 0 4 5 2 3 0 5 0 4 2 5 1 2 3 1 0 4 4 3 1 3 2 1 1 3 2 3 1 0 2 2 0 1 3 1 1 2 5 2 1 3 1 2 0 3 2 1 1 1 1 0 2 2 4 2 4 3 3 2 1 2 1 3 0 7 1 2 1 0 1 2 2 0 1 2 4 4 1 3 3 0 2 3 2 0 6 4 3 0 3 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
 402977 377729 25248
 1193121 1142636 50485
 1147218 1099092 48126
 421994 398576 23418
 1455758 1397740 58018
 453566 430218 23348
 1155646 1109043 46603
 426138 397873 28265
 1138959 1095815 43144
 1134574 1091530 43044
 469047 442949 26098
 1095038 1054795 40243
 449621 426171 23450
 1181732 1140988 40744
 1061919 1024986 36933
 418178 397155 21023
 1081900 1045442 36458
 449490 428586 20904
 1058221 1023811 34410
 444020 424588 19432
 987290 955908 31382
 1082603 1047362 35241
 369297 354768 14529
 1012292 979539 32753
 364180 351195 12985
 1012991 980330 32661
 903902 874918 28984
 457907 443878 14029
 964861 935133 29728
 362348 351917 10431
 85131178 84016072 1115106
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
100 98 3 3
61 18 1 0
79 35 0 0
74 30 1 0
36 33 3 1
52 42 6 3
1860 74 31 7
11167 64 95 32
55026 71 447 90
232434 80 712 204
748841 127 838 289
2153509 165 1102 499
5026557 232 1371 652
10039300 352 1615 979
15383963 555 1887 1212
19987942 703 2007 1619
20659449 947 2245 1996
16839930 1346 2467 2421
9947356 1662 2923 2921
3682457 2132 3520 3565
714568 2651 4016 4135
58105 3229 4608 4767
7551 4057 5069 5404
6637 5002 5755 5686
7023 5801 6422 6216
7718 6585 6886 6697
8138 7558 7400 7337
8881 8281 8188 8166
9493 8945 8724 9137
9785 9245 9326 9574
10245 9528 9563 9830
10713 9867 9873 9994
10186 9922 9809 9859
9859 10159 9523 9860
9704 9988 9474 9755
9602 10489 9525 10055
9318 13644 9251 10474
9199 9044 8999 9045
9306 9407 9034 9080
9044 9069 9061 8999
9378 9112 9228 9139
9410 9428 9334 9439
10040 9883 9563 9688
9936 10099 10116 10226
10780 10718 10426 10336
10814 10696 10685 10547
11031 10785 10929 10739
10842 10951 10827 10893
10679 10773 10868 10861
10457 10354 10560 10707
9933 9956 9981 9808
9169 9159 9136 9266
8217 8450 8329 8206
7556 7461 7428 7406
6454 6502 6605 6605
5773 5907 5703 5698
5149 5065 4896 5117
4418 4424 4512 4392
3893 3925 4015 3931
3526 3453 3544 3558
3327 3318 3381 3320
3132 3192 3173 3172
3105 3172 3130 3160
3117 3182 3187 3064
3252 3200 3147 3225
3362 3305 3222 3243
3487 3496 3610 3644
3750 3788 3819 3843
4190 4275 4146 4220
4431 4584 4536 4601
4826 4907 4834 4897
5232 5241 5297 5335
5655 5589 5667 5583
5694 5611 5694 5699
5181 5241 5346 5323
5040 5142 5027 4921
4630 4425 4440 4351
3794 3744 3608 3635
3308 3197 3354 3324
2506 2503 2508 2437
1567 1554 1565 1562
849 858 832 840
51 43 63 54
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
