A = [
3340590 3402036 19720831 1571906 1510730 1403157 1194175 1161675 1107764 1131503 1250655 1388270 1570280 1768131 1947904 2076072 2094762 2109012 2106351 2001321 1951890 1954969 1918620 1902426 1923978 2179824 2231748 2200497 2370150 2035813 2005626 1941669 1565682 1577444 1578113 1568971 1560728 1523169 1523633 1524863 1521981 1525143 1527947 1540326 1544367 1532436 1563998 1581224 1562521 1600906 1617339 1608024 1630718 1641243 1633511 1628604 1621507 1611764 1588914 1564111 1569334 1561167 1555662 1554726 1551290 1557193 1534482 1562292 1576243 1575541 1620013 1659829 1682882 1700821 1722523 1729787 1731525 1731006 1713629 1701745 1692388 1685446 1677476 1672511 1674579 1660934 1650466 1621652 1598120 1583282 1566476 1555943 1551741 1546667 1544000 1541124 1533355 1527287 1511321 1492304 1483466 1471948 1460605 1456182 1450177 1448661 1441373 1435712 1425053 1412273 1397551 1385868 1378484 1373241 1365985 1364935 1359844 1354428 1344592 1332041 1321088 1308827 1296652 1288991 1283223 1275748 1271668 1266314 1256258 1244968 1233204 1222122 1208279 1199056 1196506 1187401 1181988 1179821 1168933 1157341 1148883 1138271 1127353 1118275 1107413 1099564 1096916 1089008 1081888 1076383 1064828 1053267 1045499 1030373 1023048 1015735 1008660 1001441 994206 985750 976686 969365 957737 946885 936885 930195 923475 917587 910732 903718 895334 888072 876220 868452 858084 849341 842396 838159 828486 824244 815276 808187 799367 788763 781512 773750 765565 760252 753814 747903 741602 733598 727189 718479 710286 703192 693962 686547 681132 677108 672600 665077 655748 648602 639879 633765 628497 620050 614734 608342 602108 594695 590024 581851 575605 567793 562000 554526 550191 543322 538457 532935 526691 519336 512077 505294 498477 490444 484213 477142 473197 466580 461264 455923 449957 442535 436599 430362 424624 420111 414692 410130 404462 398307 395392 389059 383699 378247 372366 367727 364276 359709 355169 349953 347461 341609 334391 330011 327009 322387 315975 313741 309006 304690 301265 296459 292973 287432 283722 280105 276018 272209 269136 265621 262970 258135 253992 250318 246623 242782 240941 236237 232946 229668 226775 223831 220210 217405 214045 211399 207762 204929 201759 199225 197583 193394 192190 188705 185577 182835 179984 177161 174789 172863 169981 167438 165013 162168 159822 157850 155503 153173 150654 149013 146577 143680 142537 139799 138176 136863 134136 130877 129635 127953 125761 124068 122418 120594 118671 117870 115369 113578 112252 110286 108546 106527 105593 103626 102909 100804 99546 98445 96253 94949 93434 91852 90892 89819 88724 87022 85582 84265 83130 82529 80521 79083 78071 77221 75765 74613 73069 72801 71591 70196 69548 68142 66559 66368 65030 63894 63323 62176 61445 60716 59463 58725 57469 57026 55895 55021 54706 53244 52488 51799 51245 50447 49341 48574 47738 47565 46503 45414 44928 44637 43935 43253 42588 41669 41054 40238 39800 39664 38948 38055 37643 37153 36425 35581 35301 34680 34165 33684 33232 32818 32398 31488 30884 30825 30042 29759 29030 29058 28750 28067 27643 27269 26935 26661 26191 25322 25135 25051 24718 23980 23444 23417 22890 22801 22299 21879 21661 21424 21031 20688 20496 20162 19824 19269 19409 18431 18190 18309 18005 17711 17293 16996 16830 16721 16270 16238 15715 15637 15202 14902 14857 14784 14458 14180 14220 13767 13591 13389 13325 13027 12667 12727 12299 12318 12167 11761 11735 11361 11300 11243 10990 10816 10741 10619 10446 10128 10147 9841 9560 9583 9453 9336 9272 8839 8663 8577 8437 8336 8293 8214 8064 7941 7845 7810 7613 7473 7467 7306 7137 7068 6809 6767 6777 6688 6548 6416 6379 6256 6108 6089 6086 5770 5781 5730 5683 5511 5409 5347 5320 5076 5125 5008 5027 5080 4818 4805 4636 4569 4597 4503 4299 4434 4218 4203 4270 4150 3998 4018 4046 3876 3809 3728 3798 3679 3660 3563 3499 3521 3363 3341 3403 3286 3158 3100 3182 3071 3078 3022 2924 2893 2917 2895 2851 2780 2733 2708 2624 2617 2545 2572 2578 2433 2428 2424 2335 2429 2327 2364 2155 2266 2077 2144 2161 2144 2040 2006 2097 2000 1877 1915 1905 1875 1877 1850 1770 1733 1794 1765 1700 1618 1721 1644 1617 1591 1520 1568 1468 1543 1459 1580 1516 1421 1463 1422 1411 1394 1306 1373 1294 1258 1266 1290 1277 1184 1177 1227 1245 1135 1135 1182 1156 1175 1147 1122 1019 1103 1066 1082 1047 1008 1031 1012 954 988 993 954 1011 923 940 931 855 893 863 860 868 781 875 864 847 838 839 817 839 823 799 762 758 729 675 785 722 731 735 736 703 689 707 651 688 623 625 630 642 676 646 644 632 657 640 594 581 617 627 625 647 609 575 563 543 559 576 600 566 559 544 525 529 531 555 506 501 511 480 519 507 469 488 495 452 476 492 485 434 470 402 434 450 410 437 443 385 416 438 441 418 411 386 391 408 435 398 416 405 362 390 405 354 390 371 350 377 379 396 365 383 347 342 339 353 329 362 350 378 323 346 350 308 318 293 347 358 301 337 304 305 317 304 303 313 294 287 316 306 287 283 291 299 299 270 257 294 298 258 280 279 283 289 259 244 260 281 278 277 255 274 240 224 237 271 238 244 296 230 208 239 245 241 239 210 226 250 259 228 241 243 228 225 249 217 235 188 243 237 234 201 213 199 207 210 202 215 222 246 197 220 223 229 188 197 212 197 186 183 177 202 202 223 189 184 180 204 193 182 189 178 193 184 174 185 184 186 168 154 192 182 170 173 192 159 189 179 163 162 162 163 179 170 171 150 162 154 165 170 150 138 168 144 160 142 150 145 142 145 153 154 154 146 165 164 165 154 147 150 156 152 143 146 138 135 133 151 148 144 116 126 154 131 141 160 121 126 127 132 129 136 148 138 124 121 112 136 136 121 130 119 128 122 126 127 115 93 117 112 117 107 111 135 123 120 121 120 114 111 112 127 134 130 106 110 98 117 120 109 97 91 102 105 111 98 108 112 101 118 83 88 107 109 102 109 105 79 101 107 107 105 94 94 112 106 106 91 106 106 100 81 105 89 110 116 84 85 89 82 102 89 84 81 85 97 84 88 92 96 86 83 83 80 89 84 95 95 82 88 75 85 95 83 79 77 93 87 83 95 87 52 81 81 75 68 65 57 76 64 81 60 81 68 85 72 63 65 72 77 65 81 76 63 66 56 75 70 74 60 83 75 67 58 72 61 76 77 64 72 73 57 80 52 49 51 55 71 49 68 60 60 64 61 70 75 73 82 68 67 56 52 46 48 47 64 55 66 59 67 60 48 56 56 47 58 64 55 65 60 72 59 62 69 65 58 66 58 40 57 58 56 48 45 53 57 51 54 49 57 88 50 47 44 50 50 61 62 49 47 53 40 52 52 56 59 50 43 38 56 49 46 40 39 47 43 44 36 48 47 29 45 59 42 42 56 43 41 47 44 55 47 45 36 48 33 38 43 45 49 45 28 38 52 39 26 45 43 43 42 32 39 34 41 42 51 37 40 34 32 32 38 30 38 25 26 44 31 29 44 46 33 35 29 41 40 41 40 43 25 42 24 34 30 26 41 36 38 26 30 24 39 32 33 29 29 52 46 32 40 48 30 34 52 52 36 34 31 54 37 42 36 31 42 33 30 28 46 36 32 42 32 37 28 39 37 29 29 48 31 22 33 27 25 40 29 33 20 22 33 34 26 24 25 26 27 19 21 32 28 24 30 22 30 28 25 35 22 19 25 18 27 21 28 19 24 26 20 22 16 24 25 20 21 25 22 18 28 20 25 18 14 21 23 21 22 15 13 26 21 17 19 27 20 21 20 20 17 20 25 17 18 14 19 20 15 20 20 22 16 23 16 17 11 17 17 16 16 22 27 18 18 16 19 22 13 20 19 19 19 20 24 11 15 20 18 19 20 19 24 19 15 14 17 11 19 12 18 12 18 24 21 16 20 13 16 12 14 17 18 18 15 21 22 17 19 15 14 19 22 15 16 17 16 20 25 17 12 20 14 13 22 33 20 23 19 21 13 14 13 17 16 15 30 16 22 21 17 34 21 17 19 16 14 17 18 16 28 26 18 14 15 25 21 19 19 18 27 22 19 21 17 18 34 22 14 20 15 19 21 12 21 24 14 9 9 10 21 11 11 10 14 10 14 12 15 18 12 10 13 14 16 11 9 13 12 13 16 12 12 14 13 13 19 11 14 16 12 12 17 11 16 14 19 26 29 16 31 19 29 30 28 26 24 16 28 23 26 25 24 25 26 25 21 25 27 30 37 20 23 25 27 30 27 21 28 47 38 19 24 31 17 29 18 35 20 23 14 13 21 26 34 27 13 26 23 17 14 20 11 18 21 23 6 4 13 12 12 8 8 10 6 10 12 5 10 8 7 16 12 15 14 6 7 11 4 10 10 9 9 10 9 8 9 9 11 10 11 11 6 8 8 7 8 13 7 11 8 16 6 7 9 10 7 11 8 9 11 5 8 5 4 9 7 7 8 5 5 6 10 10 7 7 8 12 8 6 5 5 9 11 7 9 9 6 7 10 6 9 4 13 7 11 9 10 7 6 3 10 7 7 5 6 5 10 5 3 10 7 9 1 8 12 5 5 10 7 9 4 9 9 5 4 9 5 2 6 13 5 4 6 7 7 3 9 9 5 2 6 6 1 4 4 5 11 4 7 6 6 6 9 7 9 10 7 2 5 5 5 3 7 8 11 5 3 2 4 7 4 8 2 3 7 3 3 2 3 2 4 3 8 5 4 7 5 6 4 5 6 5 6 3 6 4 3 4 3 7 3 6 6 4 5 1 6 6 6 4 6 3 1 3 4 7 9 2 4 8 4 5 9 7 4 6 2 5 6 4 3 3 2 1 6 2 6 2 3 6 4 1 2 6 5 2 8 8 5 2 6 9 5 3 4 2 3 4 4 1 4 6 9 6 5 3 4 4 5 1 3 1 4 3 4 3 5 2 2 2 4 2 1 1 4 8 5 4 3 4 2 2 1 3 5 2 4 2 3 4 5 1 4 0 3 2 5 1 4 2 2 5 1 4 4 4 0 4 3 7 5 3 6 3 2 1 3 5 5 2 2 0 4 3 5 2 4 2 4 3 5 0 4 1 4 2 2 3 0 1 0 4 3 2 6 0 3 5 6 0 2 3 5 2 2 4 2 6 3 2 2 2 1 1 3 1 5 2 1 4 0 2 1 4 2 3 2 0 1 1 6 2 1 2 1 2 2 3 2 1 1 1 2 0 1 
];
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
 1203414 971476 231938
 841690 687259 154431
 1247511 1009613 237898
 1155561 926651 228910
 1575349 1275732 299617
 871382 712580 158802
 1231738 995164 236574
 2036435 1674532 361903
 1173070 950938 222132
 997727 820643 177084
 1839246 1513234 326012
 1438966 1165701 273265
 1740327 1431205 309122
 838699 687822 150877
 1319611 1077533 242078
 1762926 1451037 311889
 971076 800653 170423
 1726998 1421370 305628
 1334961 1086991 247970
 1699287 1396265 303022
 947897 781221 166676
 1669657 1372055 297602
 1353479 1100630 252849
 1698279 1390377 307902
 877361 726631 150730
 1792356 1472451 319905
 1579491 1296286 283205
 822837 677947 144890
 1612169 1319646 292523
 1080329 871667 208662
 141242708 119068264 22174444
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
92 836 2 4
15 74 1 1
26 169 2 0
53 146 2 8
47 135 8 13
72 147 25 38
564 191 50 87
7110 211 115 216
76691 231 162 310
253242 345 354 549
401742 443 3983 1283
654393 631 6250 2528
1023858 984 7997 3834
1712461 1870 10053 5581
3028129 3335 12039 8041
5219648 5901 15269 11820
6690123 9744 21857 19260
5803907 15413 33333 31339
3636309 24688 49925 49610
1751557 37207 72206 71518
663855 54476 95716 95901
248204 78323 119474 119780
163785 109525 145243 145746
176553 146087 173147 173996
205792 187226 204712 204330
241352 230476 239009 240271
280313 273710 277561 279008
323098 317656 320547 320817
366902 362815 363591 365824
411084 408031 408731 410178
454632 452292 452433 454325
495399 492027 493105 494999
528983 528977 529568 532195
559749 561376 559555 560347
584464 585017 582678 585798
601229 602913 602983 603709
617138 619647 617831 618297
627443 630316 627686 631306
637845 639289 636803 638850
647392 652072 648860 648729
660882 662112 660971 662071
678306 678185 676906 679932
697991 700923 696951 700000
723876 724922 722651 725122
752014 752755 752691 753839
783324 786088 785575 786144
817486 817202 815670 818240
844757 845559 844635 847405
868991 868344 866542 870703
880258 881195 880039 882375
878980 880904 878248 880895
861995 864681 862840 866280
832244 834935 832289 835367
790515 795032 790481 793848
738296 742137 740358 741629
677111 681624 680512 680680
615927 620444 619239 620369
558358 560499 558712 559971
504247 505856 503849 503819
457282 459557 457529 460275
425458 425809 425501 425697
401158 402096 401121 403789
383645 383048 381971 383081
379635 378766 378987 379480
388264 389452 387536 389018
407417 408456 406998 408977
434497 434274 434476 433809
473087 471953 470469 472340
510644 510670 510397 511893
533884 534701 534074 536426
540005 539075 538521 540257
524327 523789 523211 525553
479308 477962 478667 480452
401370 400874 400620 401334
325567 324379 324064 326558
253849 253016 252850 253443
187506 187878 186624 187461
132942 132422 133189 133347
101706 101984 101010 101950
73614 73404 73738 73367
50434 50022 50204 50399
30855 30605 30883 30550
2559 2691 2598 2666
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
