A = [
4803716 4498799 69727180 3500394 3711886 3507490 3425615 3927500 3797408 3759601 3896486 3971868 4136240 4260197 4284513 4350078 4499748 4586470 4615420 4574811 4556687 4603209 4568037 4435142 4392759 4794666 4752947 4670208 4963789 4096684 4053117 3971260 3126738 3133937 3099978 3083005 3064941 2984036 2985921 2985097 2946813 2960730 2940375 2919829 2945295 2880659 2853801 2926317 2863297 2854629 2860464 2761336 2772616 2744427 2681714 2638196 2635397 2663626 2581957 2538744 2553351 2516248 2478393 2434606 2398861 2391365 2348349 2307905 2302532 2269255 2263711 2271193 2250892 2246619 2264983 2239901 2226159 2216749 2181944 2151606 2134745 2125182 2082690 2054710 2060762 2006042 1961069 1899628 1856629 1841796 1818078 1788692 1784429 1754865 1736260 1720467 1700478 1685584 1663778 1644514 1630868 1613968 1592639 1579819 1564175 1548048 1532080 1513296 1501339 1489175 1469297 1468061 1458557 1445690 1443532 1429750 1618453 1618510 1613258 1800097 1835693 1834459 1827016 1838435 1828394 1813971 1797226 1776156 1755383 1737023 1716008 1695427 1673977 1655022 1633612 1615364 1592292 1575889 1556105 1534085 1514137 1495460 1479942 1460629 1438495 1422953 1406050 1384300 1364902 1346623 1326472 1309079 1294408 1272728 1256511 1238813 1219460 1204775 1187434 1170228 1152684 1138340 1119590 1104020 1089552 1073861 1063893 1044820 1033594 1018907 1005045 990582 979794 964350 952555 936628 925893 914107 900318 888974 875182 861499 851032 839244 830623 819611 804810 797155 784517 773882 764360 752992 744405 733848 722293 711998 703358 694026 684213 672227 664899 656527 645771 636324 628971 620063 612209 604005 595518 587175 576052 570124 560286 551516 545041 537917 530038 522803 516483 510447 503692 496497 489379 481206 473586 465669 457184 449513 440521 433418 425630 418194 411782 405658 398265 393267 386666 381622 374300 369659 363249 357807 352672 347032 342086 337163 330832 325791 321877 315425 312189 306364 302437 297193 292688 288214 284644 279588 274002 271915 267116 262954 259533 255668 251951 247667 244495 240232 235946 233000 229631 226746 223473 220072 215914 213209 209627 206132 203724 201497 197638 194547 191531 188910 186251 183004 180425 178171 175796 171764 170315 167575 164448 162729 159809 156520 155183 152559 149876 147541 145792 143457 142142 139707 136925 134912 133145 131077 128803 126720 125188 123433 121368 119916 117965 115892 114067 112105 110442 109334 107575 105388 104949 102586 101144 100306 97473 96549 95228 93590 91988 90631 89553 88698 86215 85021 83743 83071 81765 79950 78784 77684 76314 75512 74188 73033 72567 70978 69683 68742 67184 66547 65415 64675 63560 62552 61819 60487 59361 59436 57984 57350 56261 54850 54267 54085 52830 51954 51155 50196 49504 48766 48378 47356 46354 45687 44926 44355 43688 43169 42535 41662 41290 40872 39608 39164 38969 38073 37535 36915 36359 35886 35160 34983 34057 33579 33021 32728 31885 31777 31151 30456 30083 29790 29274 28968 28211 27621 27464 27041 26552 25999 25512 25371 24792 24888 24156 23964 23423 22937 22724 22368 22116 21790 21374 21473 20891 20519 19988 19798 19548 19288 18740 18577 18159 18215 17639 17510 17065 16880 16476 16264 16125 15933 15575 15267 15236 14813 14580 14518 14195 13953 13970 13665 13393 13070 13064 12853 12657 12457 11888 11908 11664 11595 11455 11195 10866 10907 10693 10492 10306 10350 10195 9716 9604 9687 9645 9217 9162 9217 8814 8750 8598 8318 8481 8051 7925 8278 7732 7787 7592 7540 7350 7265 7293 7081 7004 7036 6707 6671 6534 6388 6238 6151 6119 6248 6088 5906 5824 5715 5540 5749 5410 5318 5314 5380 5000 4960 5004 4945 4776 4658 4725 4611 4514 4481 4426 4357 4348 4070 4112 3916 4155 3922 3926 3676 3796 3681 3617 3570 3477 3588 3368 3396 3329 3306 3272 3204 3295 3060 3043 3023 3017 2807 2869 2881 2815 2627 2752 2761 2591 2642 2558 2577 2496 2434 2469 2427 2460 2384 2267 2209 2314 2270 2214 2157 2137 2113 2077 2075 2007 1941 1976 1908 1885 1876 1833 1815 1714 1730 1675 1732 1700 1713 1661 1623 1555 1559 1557 1542 1542 1511 1527 1493 1384 1369 1320 1476 1365 1363 1316 1317 1297 1311 1282 1320 1225 1209 1198 1231 1192 1129 1187 1152 1089 1079 1088 1073 1030 1054 1031 1054 1010 1011 1010 976 984 973 932 969 890 977 918 887 888 800 899 851 845 902 871 865 833 795 838 771 750 802 764 766 722 779 698 731 768 707 727 746 708 684 692 705 649 639 605 641 643 632 663 657 594 610 630 575 569 611 605 573 582 606 566 558 571 555 516 586 575 565 475 522 519 517 544 524 489 493 490 471 492 486 481 479 484 455 442 428 460 445 468 482 445 435 435 452 438 422 407 427 454 402 421 461 415 403 403 391 422 378 348 393 390 332 417 364 320 383 360 385 368 359 396 347 329 344 354 364 313 344 342 317 314 308 291 329 311 335 334 305 288 315 296 306 338 303 298 295 276 286 303 251 294 275 286 287 290 299 273 261 275 284 282 245 256 270 258 227 282 261 252 277 258 268 254 242 255 235 222 269 231 249 286 199 244 236 229 267 231 234 204 249 237 229 232 217 203 229 254 208 215 229 224 216 201 226 221 214 209 227 194 210 194 201 182 185 181 194 189 211 225 212 203 195 210 183 160 195 195 180 199 183 202 169 201 183 184 161 154 180 196 157 172 159 170 159 175 191 185 160 152 169 149 174 175 137 153 159 154 150 145 138 146 141 164 137 139 175 171 153 144 154 144 146 153 137 152 168 116 136 138 142 163 131 132 112 133 134 142 131 152 142 135 158 135 137 130 129 130 140 137 133 129 133 122 133 141 137 117 132 128 129 142 134 115 133 121 106 130 152 129 116 103 113 103 119 113 109 114 106 117 124 108 115 113 114 111 96 128 92 109 121 118 116 97 125 114 94 107 111 113 96 99 119 97 106 107 90 107 102 91 91 97 99 113 113 105 98 109 110 97 87 100 92 104 84 104 87 117 80 108 89 100 104 101 89 88 91 76 108 94 93 71 98 72 81 82 87 74 90 92 94 76 78 82 76 84 68 95 74 67 81 90 92 88 76 68 74 89 73 81 75 83 88 89 108 89 84 94 86 88 114 104 104 105 119 127 81 77 101 103 117 102 95 107 106 106 112 111 113 120 115 110 135 126 137 146 125 118 127 132 126 134 142 121 138 120 134 115 117 126 110 105 107 95 122 122 106 114 100 115 89 106 121 109 124 86 781 133 116 114 113 105 105 102 93 80 108 93 87 90 86 74 91 89 76 65 112 73 79 81 81 67 90 80 77 76 69 59 77 65 64 64 67 63 87 73 54 76 66 68 71 60 62 62 82 74 59 55 49 73 57 74 70 73 61 61 61 61 66 85 65 51 62 71 185 1413 49 48 45 39 43 49 44 35 48 32 38 52 30 40 42 44 47 37 53 43 43 41 34 48 35 46 39 43 37 25 33 34 42 45 33 35 41 49 41 41 50 41 42 35 30 41 48 65 48 35 29 49 40 38 46 42 44 44 36 42 42 39 43 40 41 46 41 47 44 43 57 59 48 40 53 42 62 38 67 59 54 61 58 54 55 63 55 61 61 57 60 58 52 64 57 53 55 60 65 59 55 60 64 65 64 60 62 63 66 55 63 68 71 59 67 68 77 64 54 72 65 70 58 65 85 78 94 72 64 62 58 54 50 50 63 54 31 55 56 39 38 36 53 31 40 43 32 26 37 19 23 18 23 28 19 35 26 18 20 23 28 24 23 17 29 20 19 22 14 20 28 17 22 21 19 19 14 18 27 21 20 18 29 20 32 18 32 27 20 22 19 28 20 31 24 28 38 27 20 26 33 26 20 30 27 26 14 19 24 31 25 27 27 25 29 21 23 24 16 33 28 31 29 30 20 24 30 25 22 26 18 19 20 25 19 20 24 17 13 23 14 6 19 18 17 19 16 24 22 22 18 25 20 19 20 14 12 17 18 23 21 19 14 12 14 13 11 13 12 20 19 25 9 12 19 10 14 13 10 15 9 18 17 15 16 11 12 15 22 12 15 16 19 13 18 19 13 9 11 22 12 11 20 17 12 16 18 8 16 15 9 16 13 15 8 8 9 7 12 6 13 5 13 10 8 10 10 17 11 8 10 9 6 11 12 13 9 13 7 12 13 9 6 11 19 11 6 19 21 11 7 11 14 11 9 15 11 11 16 8 13 11 12 10 11 12 10 10 12 8 8 11 14 21 10 9 7 18 16 13 10 20 10 11 16 12 10 18 5 14 15 11 20 15 13 13 18 16 18 18 13 30 10 19 10 14 20 15 8 5 11 12 26 12 11 12 13 17 6 14 8 12 15 9 11 15 22 15 14 9 14 9 11 7 4 9 10 6 9 5 9 7 8 14 11 12 7 12 10 12 10 8 9 20 11 11 15 11 11 10 9 10 10 11 9 12 6 8 10 6 3 4 12 6 8 5 5 5 5 6 12 1 4 11 6 5 3 4 5 6 8 7 4 3 4 4 6 11 10 5 9 6 5 5 5 9 6 5 6 9 5 6 3 7 7 6 8 6 6 1 5 6 4 5 6 5 8 6 3 3 6 3 4 1 6 1 6 8 4 8 6 5 7 4 4 3 7 9 5 5 5 5 3 4 3 6 5 6 4 5 4 4 2 9 0 8 4 10 5 5 7 1 4 6 5 2 7 6 2 4 1 1 7 6 2 4 2 5 5 5 3 1 2 4 3 7 4 2 5 6 3 3 4 4 9 2 3 1 3 3 2 4 3 2 3 3 6 2 1 4 6 8 1 3 4 6 6 8 4 5 5 3 3 3 0 4 3 2 2 4 2 8 1 6 3 3 3 2 3 3 3 3 3 3 3 4 3 5 2 4 1 4 2 4 5 5 3 1 5 2 3 4 1 4 8 2 2 3 3 4 2 1 2 4 1 4 1 0 5 2 4 1 2 7 4 2 0 2 5 2 2 3 3 2 4 1 4 3 2 0 4 2 1 3 1 5 0 4 1 2 1 1 2 2 2 5 5 2 2 1 2 5 3 4 2 3 7 1 3 3 2 0 5 6 3 3 1 3 3 3 3 3 2 1 2 2 4 5 2 2 5 2 3 1 1 1 1 1 3 4 2 1 1 0 3 2 3 1 1 0 3 1 1 1 4 2 0 1 3 1 2 2 0 3 1 2 3 1 2 1 1 1 0 0 2 3 2 0 1 2 1 0 1 1 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
 1342424 1098456 243968
 1295208 1052655 242553
 1278713 1039762 238951
 1231718 1007355 224363
 1451727 1179993 271734
 1318379 1086839 231540
 1305414 1057427 247987
 2656726 2144453 512273
 1242992 1023705 219287
 1451983 1185441 266542
 2369382 1928782 440600
 1401538 1151139 250399
 2169650 1765446 404204
 1235567 1024080 211487
 1387573 1141157 246416
 2215716 1810897 404819
 1407185 1160652 246533
 2126361 1738208 388153
 1381679 1147259 234420
 2041976 1669342 372634
 1389926 1157624 232302
 2012376 1649048 363328
 1442948 1199742 243206
 1989419 1630994 358425
 1364432 1138222 226210
 2096507 1720582 375925
 1880655 1547308 333347
 1294004 1086579 207425
 1898556 1564719 333837
 1081252 919992 161260
 239686485 221270616 18415869
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
193 387 1 0
31 46 0 0
36 187 0 0
68 96 1 0
53 101 0 1
52 80 3 0
49 130 9 6
253 132 13 6
223611 130 27 5
1690545 164 59 12
3418075 232 123 38
7068036 251 317 120
13207897 417 3195 1061
22158047 710 12983 4844
29073801 1297 13212 7136
31736091 3232 14998 10524
27520425 7736 23395 20656
20622276 14635 37101 35606
13097596 23459 54896 54253
6338691 34850 74807 74511
2164396 49358 92380 93823
532423 68264 112833 112614
175413 94082 134456 134295
163246 125258 158881 158908
187832 161097 184657 186278
216232 198793 213619 216171
247421 237090 246236 247011
280649 276040 280082 281735
314072 311966 314529 316016
344782 348052 347775 349459
373764 379539 377040 378133
399657 407407 401390 404432
421105 428300 421649 423857
433778 442869 436762 438310
441135 451422 444652 447242
447499 453507 448845 451612
446232 454335 449215 452068
444576 453568 446348 450475
445709 451068 447862 448014
445586 450524 445950 449389
449707 454523 451423 452025
457674 462180 458825 461326
472878 474526 471573 473998
492750 493337 490210 493797
514018 515030 511478 515870
540124 540005 538285 541914
565616 566804 563576 567484
588234 590126 588379 589897
609263 610228 608952 611776
622164 624067 622477 623782
626190 628128 626829 626384
618944 622242 618679 620958
602948 603311 600942 602598
573654 577901 574858 576298
539490 541996 541172 543564
500012 501687 497369 501602
452431 455286 452798 454953
407393 408699 408080 408446
362759 364595 362357 364036
325613 325673 324195 326005
291659 293760 291598 293400
261271 261326 259906 260152
240846 239969 240046 241099
227223 227598 226903 227540
218005 218149 218576 219825
215157 215500 214494 215334
225337 224621 224756 225070
259676 257352 258205 259053
240384 239862 239404 240529
250030 250835 249084 251793
234224 236584 235467 236257
210789 211550 210726 211423
223579 225350 223464 224859
153423 153471 153048 153706
129614 129348 129623 130048
104768 104724 103965 104140
85236 85675 85355 86205
74380 73525 73546 73712
63062 63432 62703 63203
50616 50727 50338 50575
32252 32691 32666 32955
17465 17462 17738 17504
829 928 898 877
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
