A = [
1129529 1103750 6004073 1114541 1091892 1013369 1028414 1023049 1072133 1027237 1081859 1139726 1252868 1381088 1554419 1739657 1811215 1897474 1929685 1863011 1764445 1700907 1658589 1625575 1622962 1899700 1921579 1905878 2099415 1796593 1804204 1766301 1464200 1490338 1479030 1472747 1454900 1413510 1398561 1396943 1400458 1395077 1392433 1430021 1444917 1423180 1462237 1453008 1459265 1485142 1472273 1473727 1495000 1498784 1487651 1490493 1471338 1477612 1461066 1425008 1417044 1419831 1415090 1412279 1416590 1426028 1414034 1411239 1413855 1401008 1422942 1439383 1451281 1460968 1472187 1479451 1470859 1461748 1443131 1429482 1417291 1404635 1396494 1396445 1391688 1381322 1370288 1346696 1334007 1323324 1313426 1304485 1299836 1296203 1291019 1290542 1281188 1275350 1269538 1254899 1241055 1238601 1228405 1222405 1222482 1221887 1218045 1210836 1203370 1195088 1183199 1174507 1170173 1164808 1163287 1160399 1160216 1154174 1147574 1140460 1132897 1123890 1118447 1112255 1110235 1105041 1101282 1094716 1088303 1082406 1074731 1066492 1058798 1055152 1050911 1045633 1041704 1036808 1032962 1026765 1019213 1013702 1006060 1002029 998744 991328 988319 984623 981811 976336 972060 962621 958494 953146 946740 941526 938154 934279 928586 922575 917333 911652 903901 897990 893073 889330 886414 882497 878574 873511 870712 862892 857283 852702 848333 844162 841382 836786 832373 826614 821551 815779 813146 810219 805270 802779 797393 794900 790646 788193 786247 780515 776795 773996 769197 764770 762228 758822 755924 752323 748812 747152 741879 738257 734111 732140 727763 725957 721036 717301 712187 707431 701421 696444 693353 689817 684880 682013 681267 678291 675039 672585 669297 668600 663417 658831 653103 644969 639788 633996 627200 622966 619858 616593 611119 606351 602240 598597 593951 589709 586831 581546 578721 575241 572721 567823 564643 560290 556068 553741 549281 544955 543101 538752 533590 531167 526490 523776 520598 515850 513262 509477 506160 501865 498428 496304 492091 488050 484800 480365 477080 474010 471117 468233 464581 462750 456151 455303 451144 447228 443919 439531 438202 434221 430476 427968 425128 420832 418217 415013 410780 408942 405061 403212 399760 395494 392327 388925 386633 382199 379441 375952 373493 369863 366088 363592 360420 356450 354145 351033 347520 345344 341896 338127 335930 332134 328705 326042 322524 319578 315521 313036 310632 306887 304541 301609 297582 296041 292770 289320 286897 282989 280066 276670 274334 270796 267403 265335 262281 259385 256968 253396 249695 247270 243975 241375 238797 236045 232924 230017 227410 224075 221916 219339 215629 213945 210829 207577 205743 203001 199543 197046 194212 192251 189535 185842 182840 181379 178624 176186 173377 170474 167969 166317 163252 160705 157762 155797 154416 151249 149932 146643 143797 142018 139778 137559 135385 132920 131318 128670 127026 124515 122772 120614 117951 116351 114276 112299 110014 108422 106352 105259 102782 101222 98911 97987 94998 93605 91942 90169 89278 87534 85437 83970 82586 80633 79278 78033 75888 74497 73014 72130 70026 69030 67888 66804 65020 63521 62439 60872 60085 58777 57161 56426 55511 54088 52638 52292 50504 49812 49158 47276 46814 45561 44820 43771 42551 41739 40631 40346 38708 38193 37595 36387 35994 35080 34515 33441 33015 32365 31344 30911 30009 29100 28283 27951 27270 26907 26374 25604 24943 24441 23937 23513 22742 22558 21781 21083 20620 20068 19516 19447 18596 18297 17833 17785 17072 16471 16105 15728 15597 15248 14923 14422 14045 13774 13429 13158 12750 12444 12103 11922 11562 11327 10893 10696 10446 10362 9773 9754 9434 9048 8962 8909 8653 8403 8118 7848 7779 7575 7442 7290 6991 6805 6615 6415 6316 6219 6086 5952 5767 5657 5422 5288 5218 5166 4975 4804 4709 4609 4544 4403 4168 4145 4069 3970 3994 3772 3643 3689 3545 3498 3384 3291 3237 3230 3154 2919 2886 2927 2790 2697 2638 2592 2487 2553 2279 2325 2317 2308 2229 2151 2099 2005 2008 1902 1918 1810 1840 1771 1725 1735 1671 1589 1640 1577 1550 1513 1518 1472 1366 1368 1280 1349 1256 1287 1208 1170 1184 1181 1174 1132 1125 1065 1028 956 1106 993 1009 1015 947 864 898 850 827 853 833 837 787 811 783 742 758 821 752 727 735 646 720 696 716 676 642 638 606 639 555 561 592 586 545 563 521 610 521 525 572 543 540 496 497 527 484 497 485 484 461 471 498 504 480 435 451 437 439 479 423 467 433 392 453 429 444 409 385 404 390 411 396 405 432 383 392 359 371 365 359 373 394 364 322 360 333 353 350 344 325 348 308 313 369 307 318 298 312 298 316 340 308 333 312 336 346 345 294 293 311 349 306 285 307 315 286 303 289 310 313 298 285 282 266 303 267 287 273 272 269 268 265 259 250 241 267 240 263 273 252 277 261 260 270 251 245 227 241 219 246 244 239 253 230 239 239 269 216 261 245 214 215 246 221 241 226 232 191 199 207 243 194 237 227 213 221 222 213 226 218 211 215 225 201 229 206 192 210 198 184 197 181 196 202 200 191 197 164 183 196 199 189 179 196 180 177 193 179 185 200 186 190 171 170 166 182 178 187 185 181 147 164 148 185 165 171 185 180 179 163 161 173 171 165 158 169 163 172 163 148 165 169 153 168 162 133 154 140 135 146 142 152 153 143 148 138 135 145 160 137 141 137 138 155 127 147 129 147 127 148 142 148 139 110 156 139 140 122 124 139 126 127 122 116 119 148 133 136 139 131 121 125 115 126 136 118 114 118 108 120 123 114 123 126 128 110 108 99 120 109 135 108 125 102 106 116 122 106 117 102 107 124 122 122 117 107 92 117 98 103 101 100 113 81 105 104 124 111 107 93 99 76 91 91 93 107 125 95 105 100 87 97 90 91 91 89 94 85 85 73 95 105 94 77 88 96 93 83 97 86 72 82 72 90 88 70 96 77 83 96 84 87 94 84 64 82 79 84 94 82 87 87 77 74 79 72 68 89 89 70 75 81 82 68 82 64 78 82 67 75 75 72 71 60 78 70 74 74 60 67 68 69 74 63 60 70 70 59 68 74 59 61 73 77 72 61 61 54 66 64 61 61 52 59 71 67 63 48 51 66 62 70 66 62 50 63 72 58 50 69 56 64 60 63 67 52 44 50 58 64 55 59 56 53 55 65 45 52 43 63 65 67 58 43 57 63 44 48 49 43 55 49 46 47 55 56 49 33 42 58 47 57 41 43 57 41 43 45 40 31 44 51 67 46 43 45 45 41 41 34 45 44 35 46 30 44 35 43 35 37 39 48 39 41 43 52 55 57 36 44 44 51 37 41 35 43 38 37 36 33 60 47 42 44 41 41 36 41 34 39 46 35 29 34 43 45 30 41 26 39 43 39 43 34 36 48 47 45 34 41 26 42 37 32 39 36 36 48 40 46 37 34 27 33 31 34 30 35 34 35 33 41 32 35 27 26 25 26 43 36 32 22 34 32 29 26 37 36 33 28 34 22 29 20 24 40 32 33 26 25 30 28 17 33 31 30 26 16 20 23 30 30 27 26 26 16 25 33 27 26 21 29 19 28 16 29 20 24 19 28 29 24 33 32 31 28 28 23 27 35 36 32 36 23 24 26 38 31 27 31 42 24 30 31 23 40 27 31 37 42 27 22 17 15 25 34 21 9 26 18 28 22 26 26 14 21 20 22 16 23 16 12 20 19 19 11 15 25 15 14 27 19 20 18 17 14 14 17 14 16 16 18 20 15 16 20 21 15 18 18 15 9 20 16 18 15 17 23 8 14 12 18 14 9 21 12 16 19 11 15 12 14 21 11 19 18 15 21 13 16 15 14 12 18 9 14 15 15 22 10 12 14 17 9 12 18 15 17 15 11 12 9 10 12 8 13 16 9 10 4 10 10 8 15 14 10 12 11 11 12 12 13 13 11 12 16 6 9 14 14 13 16 9 8 21 8 16 13 12 14 13 30 20 19 27 23 23 28 11 20 22 31 27 26 20 18 31 34 13 19 31 34 23 16 30 39 37 41 21 28 32 25 35 32 28 33 53 18 21 22 34 39 39 33 42 43 47 57 23 34 36 34 13 48 20 23 38 51 33 33 48 32 49 21 14 13 14 14 8 10 8 6 8 13 7 10 13 8 9 12 7 15 8 11 9 13 12 7 14 14 7 14 7 16 9 8 10 11 10 2 9 10 18 15 15 16 28 15 21 30 18 23 24 30 33 25 7 10 22 9 15 15 29 26 11 15 24 26 22 16 14 14 15 11 22 23 15 22 21 18 17 16 16 32 12 14 8 9 23 14 15 15 30 16 18 36 17 14 16 13 15 16 8 11 7 9 9 9 4 7 9 8 10 10 10 7 9 9 8 14 8 9 6 9 9 9 12 5 11 4 6 11 10 6 11 11 6 9 9 5 4 6 5 6 10 6 5 13 4 12 8 9 8 5 11 4 4 4 5 3 7 6 6 3 3 9 7 8 12 3 10 7 12 8 6 7 12 10 10 7 8 9 7 8 5 4 2 6 7 13 6 5 1 6 10 8 5 3 4 12 5 2 7 5 9 7 7 10 2 9 7 4 5 4 4 4 5 5 12 2 5 4 6 7 2 9 6 7 6 10 4 6 7 7 6 4 2 3 6 5 6 2 2 2 2 8 9 4 0 8 6 3 3 3 3 5 1 3 4 4 3 3 2 4 2 1 4 6 6 5 2 5 7 2 4 4 5 6 3 3 6 1 4 5 6 5 5 8 9 6 5 3 4 4 6 7 5 3 3 2 3 11 4 3 9 1 1 2 6 3 4 1 2 5 4 2 3 4 3 3 5 3 3 1 1 3 5 3 3 4 1 4 3 5 4 3 5 4 6 1 3 3 1 2 4 1 3 0 5 7 1 3 4 4 2 3 2 3 2 4 2 1 6 3 4 0 5 2 2 2 1 2 3 4 2 4 2 4 6 4 3 2 1 3 2 2 1 2 5 5 4 2 3 1 3 2 3 3 4 3 4 5 3 5 3 4 3 2 3 3 3 5 2 7 3 6 6 3 3 5 3 3 4 4 2 2 1 5 1 1 3 4 2 1 3 5 6 2 3 3 4 4 2 0 1 2 0 2 6 1 1 2 2 2 2 3 4 0 2 4 0 1 4 1 4 0 1 2 3 4 1 6 1 0 1 3 4 3 2 2 2 3 2 2 2 1 3 2 3 4 1 0 3 3 1 0 0 1 0 0 3 2 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
 989490 803388 186102
 598269 486754 111515
 1012028 822552 189476
 950023 768817 181206
 1320441 1076687 243754
 656330 535328 121002
 1014907 824476 190431
 1536779 1266594 270185
 971144 790404 180740
 716807 588882 127925
 1400653 1154283 246370
 1209612 988129 221483
 1332456 1096373 236083
 631214 516793 114421
 1070991 878443 192548
 1357009 1119587 237422
 704142 581442 122700
 1342803 1108264 234539
 1117220 914492 202728
 1310127 1081327 228800
 706245 583212 123033
 1305305 1077952 227353
 1099293 902166 197127
 1319688 1089341 230347
 640115 530812 109303
 1411325 1166469 244856
 1245744 1030638 215106
 600230 496563 103667
 1282299 1057887 224412
 919000 750741 168259
 136569156 115903015 20666141
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
10 102 0 0
1 8 0 0
2 15 0 0
4 13 0 0
2 15 0 0
3 13 0 0
24 36 2 0
69 32 3 0
388 45 6 0
1071 62 26 5
1872 86 819 108
3915 132 1300 394
7714 255 1840 747
14114 487 2802 1401
29708 995 4006 2505
88833 2094 6075 4544
478122 4541 9289 7912
3312085 9072 14924 14028
9229212 17308 26770 26300
5841107 26974 46432 46795
1000513 39591 70692 71154
150198 56820 95975 96827
129144 79623 120749 120657
148341 111513 144931 145171
172955 148779 170812 171383
200813 187122 200630 200817
232182 227403 232972 232471
265745 267534 266756 268133
301120 304387 302022 302282
336222 342970 338135 338889
369902 377045 372551 374250
402527 409445 404670 405821
432841 437796 433862 435680
458031 466210 460198 461059
482087 489518 484064 484711
503198 511928 506480 507801
524700 533489 528856 528314
544076 552423 548781 548025
567116 571662 567630 569768
586794 592524 588730 589221
608981 614144 611849 612939
635403 639101 635913 636590
662819 665939 663699 665380
693103 697683 694534 695989
728022 731057 728333 730212
766045 767086 765267 767070
801345 803609 802294 802123
833918 836297 834058 835813
863060 864856 862995 862640
881860 881768 881690 881446
888205 890634 889748 891013
880549 882591 882734 880537
860537 865035 862455 864407
832834 835444 834327 833699
791564 792828 791608 794087
737621 743400 740660 740783
684606 688143 684913 686673
625559 627764 624410 627414
569196 572388 570417 572866
521682 522616 520637 522607
485800 486719 486864 486130
459975 461212 459911 459003
439958 439513 440934 440801
435270 436413 435348 436209
443083 443872 444170 444551
461245 461015 460275 461012
486777 486238 485741 487433
524064 523773 524550 524008
567877 568532 566461 569835
600903 602748 599897 603854
618490 618313 618222 618380
614826 616622 616363 616645
577584 579207 577639 579219
501920 502960 501795 502067
424008 422897 420602 422803
337577 337543 336531 337989
252403 250736 250719 252637
174860 174558 174636 174814
129693 129415 129477 129549
90689 90382 90311 90039
60363 60765 60315 60440
36679 36646 36614 36637
3131 3031 3140 3044
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
