A = [
972067 966274 6300667 857480 825952 774280 761917 748912 750818 754428 769510 796495 835201 877368 927815 982960 1038843 1099028 1161056 1220672 1277279 1336041 1386717 1437020 1483211 1673496 1721772 1750531 1923799 1793272 1845987 1867433 1721358 1760266 1745478 1741665 1724682 1678491 1658142 1626084 1599957 1581961 1550625 1533159 1516519 1494587 1487105 1475162 1463674 1461635 1449071 1437782 1433962 1423731 1419082 1411016 1401159 1395775 1387518 1377274 1373073 1362617 1363503 1356647 1349235 1348289 1342316 1421506 1422205 1415234 1495033 1488694 1486395 1473482 1462532 1453738 1441775 1430092 1418728 1408192 1395365 1384758 1372986 1361131 1349629 1337889 1326129 1313128 1301238 1290127 1277039 1263224 1251843 1238560 1228701 1215886 1202117 1189764 1175562 1164473 1151960 1140285 1124069 1113634 1099369 1089702 1075656 1063872 1050221 1041044 1027947 1016978 1004065 993325 981526 970488 961093 948367 937250 927029 916787 906344 895301 885353 873516 861014 853449 842294 831142 822993 811354 801506 791831 782855 773188 763627 754778 743707 736258 727198 716754 707935 698432 689296 681256 673441 663661 655298 647029 638805 630560 623796 615111 606902 598865 592881 584827 576075 568740 562273 554977 548887 540338 533173 526419 519530 511663 506613 499763 494185 485781 480379 473718 466795 461412 455369 449350 442724 438740 431504 425914 420840 415071 408722 403192 398806 393674 388012 383288 378274 373137 370136 363016 358723 353668 349108 344883 340248 335662 331320 327480 322292 318325 314656 309546 305144 302295 297785 293618 288350 285845 282670 277988 274184 270946 267410 263941 259817 257273 254091 249998 246218 242969 238297 236248 232840 229165 227009 223874 221106 218126 214824 211961 210035 207515 204583 201814 198072 195321 193898 190263 187671 186098 182981 180480 177592 175705 174085 171045 168572 165679 163840 161806 159852 157678 155939 153121 150928 149623 147075 144720 142531 141468 139266 136770 135600 133853 132014 130288 129218 126891 124826 122989 121848 119815 117992 116761 114871 113341 112008 110263 109363 107485 106287 104685 102503 101562 100756 99068 97814 96064 95289 93693 92836 91374 89792 88781 87723 86478 85378 83691 83325 82325 81085 79708 79029 77186 76741 75210 74831 73744 72500 71755 70515 69967 68946 68003 67009 66183 65776 64156 63355 62480 62366 60592 60111 59522 58442 57417 56887 56020 54840 54787 53994 53432 52548 51787 51522 51025 50132 48936 48691 48092 47630 46382 45886 45704 44856 44635 43699 43173 42502 42231 41884 41090 40749 40144 39324 39308 38534 37897 38092 37167 36374 35730 35451 34978 34773 34426 33714 33305 32946 32485 32320 31374 31194 30681 30393 29894 29958 29294 28928 28311 28214 27853 27737 27191 26614 26414 26129 25951 25401 24880 25017 24705 24519 24029 23533 23051 22987 22872 22752 22187 21821 21585 21414 21095 20924 20664 20059 19999 20102 19407 19259 19371 18836 18508 18411 18119 18150 17730 17759 17588 17324 16964 16899 16698 16527 16400 16309 15756 15484 15439 15199 15096 15161 14719 14807 14504 14588 14036 14043 14140 13811 13551 13680 13286 13308 13051 12996 12623 12604 12587 12267 12329 12143 11983 11918 11707 11467 11546 11355 11185 10948 10997 10879 10691 10784 10650 10223 10421 10219 10240 9921 9937 10095 9809 9505 9578 9419 9491 9285 9119 9174 8940 8880 8915 8626 8746 8585 8471 8509 8382 8263 8092 8114 7944 7884 7912 7965 7801 7573 7573 7451 7504 7257 7396 7294 7214 7192 6914 6871 6921 6928 6653 6698 6580 6596 6643 6552 6485 6403 6397 6303 6149 6140 6234 6016 5938 5998 6057 5946 5882 5815 5800 5814 5654 5733 5662 5471 5580 5528 5377 5310 5402 5298 5313 5273 5231 5079 5128 5119 5097 5093 4819 4975 5014 4891 4844 4853 4624 4751 4637 4650 4663 4540 4622 4453 4507 4465 4429 4432 4337 4259 4466 4280 4360 4355 4080 4089 4057 4085 4119 3942 4088 4047 4141 3983 3991 4026 3846 3826 3915 3868 3792 3819 3874 3832 3691 3708 3679 3632 3666 3637 3569 3534 3570 3475 3549 3446 3423 3366 3368 3321 3366 3335 3450 3227 3286 3192 3322 3239 3141 3268 3210 3182 3141 3060 3163 3104 2982 3087 3096 2945 3013 2982 2961 3016 2977 2892 2885 2850 2835 2768 2877 2846 2769 2778 2803 2814 2697 2779 2682 2643 2682 2726 2652 2628 2557 2626 2534 2591 2654 2594 2596 2640 2529 2486 2419 2501 2486 2416 2524 2429 2404 2383 2449 2352 2415 2420 2339 2349 2360 2327 2256 2254 2338 2234 2307 2211 2173 2199 2146 2188 2161 2176 2232 2164 2157 2113 2080 2124 2090 1990 2077 2117 2034 2012 1949 2005 1955 1963 1876 1964 1898 1947 1934 1906 1919 1965 1877 1906 1892 1853 1844 1851 1883 1801 1794 1859 1818 1777 1811 1765 1807 1787 1744 1723 1708 1745 1711 1754 1650 1787 1666 1738 1719 1665 1602 1607 1676 1615 1608 1611 1568 1615 1570 1562 1645 1554 1583 1635 1605 1513 1569 1609 1497 1551 1514 1480 1500 1495 1510 1499 1466 1499 1433 1460 1481 1463 1504 1421 1401 1386 1391 1370 1390 1446 1385 1362 1347 1410 1396 1346 1387 1301 1340 1358 1357 1306 1288 1336 1361 1278 1304 1299 1303 1269 1303 1235 1292 1286 1199 1209 1190 1223 1205 1236 1206 1235 1161 1236 1185 1143 1160 1132 1156 1173 1154 1139 1147 1131 1116 1130 1129 1063 1117 1036 1132 1150 1186 1078 1074 1112 1028 1065 1088 1066 1097 1059 1069 1037 1070 1038 1002 1015 1065 993 1016 1039 952 978 1002 1055 1008 935 900 987 999 987 955 977 985 950 935 949 923 949 935 937 924 975 883 955 883 941 892 895 869 937 840 897 924 869 847 814 873 861 840 829 902 765 858 814 821 814 771 795 799 831 834 825 791 821 798 798 730 752 825 769 758 817 743 739 773 737 773 762 787 703 698 748 735 743 694 733 753 694 678 675 669 677 687 686 669 688 634 702 670 674 649 701 692 654 657 685 700 679 637 693 622 654 613 621 649 607 635 600 601 642 629 605 626 592 592 606 598 583 564 579 560 556 563 583 585 578 485 590 572 555 533 556 531 555 607 557 490 524 575 544 547 530 507 534 539 547 559 543 548 524 500 525 524 488 493 492 520 502 502 501 504 525 522 505 465 489 512 507 491 486 491 492 512 481 507 502 483 469 477 457 479 454 457 464 497 460 489 437 408 468 474 462 381 454 420 418 430 427 406 397 406 382 410 395 418 388 365 422 440 408 398 381 365 428 382 378 356 377 372 386 385 405 393 369 366 335 383 348 354 343 356 361 370 378 366 388 339 363 347 338 356 342 302 334 340 311 340 298 321 321 327 313 317 320 327 336 315 300 283 338 320 295 314 334 298 309 298 316 295 292 310 273 303 280 297 278 280 297 280 292 277 287 308 278 263 309 267 287 282 268 255 266 239 279 266 251 260 281 282 253 286 263 275 263 279 263 296 250 252 242 261 252 223 273 236 243 259 258 236 233 251 269 227 232 248 236 255 232 223 248 235 233 251 208 232 214 233 227 223 220 212 232 229 212 192 235 206 195 231 210 188 228 205 243 191 190 190 173 203 196 190 203 183 191 178 188 203 187 212 173 208 179 177 202 190 217 211 193 184 194 191 184 184 201 201 174 175 190 182 159 164 174 166 180 177 180 168 180 168 163 157 152 153 190 166 166 169 159 153 160 169 186 135 160 164 144 172 163 168 158 165 153 159 157 155 160 159 167 156 150 161 162 162 145 127 150 176 150 132 129 135 132 127 151 148 142 128 145 151 146 123 129 135 144 130 132 146 137 155 126 136 139 127 162 128 126 152 146 113 129 125 137 119 131 136 129 116 117 125 143 129 128 134 139 111 123 114 115 103 115 113 131 100 97 116 102 93 117 107 103 112 95 99 98 110 114 101 100 89 106 88 108 106 108 116 100 92 89 90 83 97 105 93 92 109 97 96 114 109 102 95 109 78 84 94 97 99 108 92 112 114 86 100 85 83 81 83 88 73 103 94 77 78 102 91 89 89 71 109 67 92 68 93 84 77 81 90 78 75 68 83 74 78 75 94 74 84 70 88 75 79 90 95 73 78 72 68 75 61 75 58 73 62 64 66 65 76 70 84 73 73 96 70 70 81 73 92 75 68 75 64 71 82 61 49 65 72 75 52 69 68 74 84 69 62 79 48 67 63 79 53 68 58 55 59 61 70 69 70 64 67 51 74 48 69 64 53 59 65 73 56 52 63 73 58 57 57 61 61 67 58 48 59 50 47 68 65 71 45 48 61 57 68 55 41 53 51 42 62 45 59 45 53 47 39 64 41 42 50 44 48 41 57 39 34 62 57 63 50 49 47 43 53 50 39 38 47 48 45 30 43 49 41 46 45 50 46 41 46 31 40 43 58 41 42 57 38 37 37 51 28 41 40 35 50 51 48 29 33 35 41 41 41 48 40 41 32 41 36 33 38 51 31 49 29 37 39 45 39 28 40 39 34 32 35 39 37 41 32 25 35 32 23 28 39 40 43 33 35 27 40 45 36 34 23 40 33 31 32 29 27 31 30 26 28 24 39 32 34 23 30 27 37 41 29 40 32 31 36 21 34 32 27 34 30 21 30 30 34 37 24 32 24 32 34 24 36 42 20 39 22 19 28 27 30 26 25 35 28 28 29 20 27 27 24 21 22 32 21 31 23 21 27 21 24 20 25 24 28 26 31 24 17 25 23 26 16 20 28 13 31 13 18 23 23 30 18 23 19 14 26 26 27 17 20 27 32 21 15 25 23 17 14 13 24 15 20 14 19 21 26 24 13 16 21 17 16 19 23 14 25 13 12 11 15 20 24 21 19 16 17 18 10 14 13 19 20 10 15 12 20 19 13 14 13 24 10 16 12 6 15 11 21 16 12 9 14 9 7 16 19 22 15 14 13 17 14 19 17 18 9 12 8 15 13 19 15 16 14 18 17 10 11 14 18 14 19 17 17 10 11 17 12 15 12 15 10 16 24 12 19 12 7 18 16 15 13 8 14 11 16 11 18 16 14 15 13 17 11 19 5 12 12 13 14 16 11 12 17 7 9 4 15 11 10 7 8 18 8 10 12 4 11 12 5 10 8 13 16 10 8 11 11 8 7 5 9 8 13 7 14 12 2 13 7 12 8 6 11 6 9 8 5 9 13 4 9 11 13 5 12 5 10 5 12 8 8 7 11 9 5 13 9 10 8 6 9 4 5 9 3 9 9 4 11 8 6 6 6 4 5 14 6 8 8 5 6 7 8 11 8 8 4 5 5 8 7 7 8 6 6 7 5 11 7 12 5 7 6 2 11 6 12 7 13 9 4 6 6 7 
];
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
 603223 467724 135499
 573826 446606 127220
 637007 495981 141026
 633626 493433 140193
 804265 627280 176985
 628724 492257 136467
 715076 559184 155892
 1485718 1164643 321075
 688267 539474 148793
 817175 642756 174419
 1342823 1055940 286883
 849503 668035 181468
 1278507 1005691 272816
 705626 556413 149213
 863858 681473 182385
 1323502 1043589 279913
 852191 673931 178260
 1292891 1021730 271161
 894176 706821 187355
 1287724 1018861 268863
 853553 677902 175651
 1273232 1009014 264218
 965392 765753 199639
 1280832 1016765 264067
 883644 703401 180243
 1378429 1095351 283078
 1281338 1018765 262573
 881193 702590 178603
 1295939 1032123 263816
 779216 622529 156687
 89984604 73558835 16425769
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
76 175 99 6
15 36 1 3
10 52 2 0
14 62 1 7
14 60 6 5
24 69 6 6
151 115 24 12
867 112 14 10
16188 145 41 26
157048 162 219 58
528569 217 1471 328
1297186 299 2286 912
2473230 404 2960 1680
3679212 585 4303 2964
4156113 1030 6332 5136
4073946 1887 9204 8344
3373908 3295 13094 12410
2410042 5113 18197 17932
1455331 8484 24951 25080
664786 12969 33735 33297
218802 19559 43073 43009
78988 28612 53815 53983
69894 41121 66714 66669
81486 57499 80706 80589
97436 76964 97503 97843
116753 100451 118212 118102
138899 126046 141006 140761
163871 153445 166328 165977
191108 181252 193198 193609
218101 208973 220839 222683
243397 234857 247862 246476
268401 258024 269364 270371
290130 279108 289660 290275
302166 297079 307450 307096
313082 309899 319075 319309
321761 319296 329228 328581
330650 329321 336475 337118
338315 337238 344550 344863
346656 345554 352932 352537
355988 355002 361636 360819
366461 366342 372512 373235
379374 379574 384660 386063
395889 395611 400066 400370
411941 412526 416535 417379
429696 430341 435591 434389
448657 448351 452781 451658
465982 466441 469051 468016
479073 478773 481582 481261
487824 487609 489425 491608
490936 493132 492150 493753
489190 487098 490096 490539
480489 480096 479527 480016
463791 464103 465481 464887
441185 441923 440948 442577
413146 415174 414003 414790
385148 384794 383782 383584
353201 353413 352020 352605
323142 321137 321070 321116
292688 292093 292144 291856
265021 265329 265212 265961
243219 243430 242210 242765
226878 226898 226236 227327
215521 214520 215041 215827
205356 205191 205974 206353
206477 206765 206940 207072
215256 215988 215675 216046
231697 231728 230780 231138
250068 249910 249556 250042
279210 278956 279017 279480
312230 312636 312152 313163
356745 357453 357071 357812
381460 381695 380076 380863
404650 405225 404526 405293
417743 416653 417404 418810
412311 412657 412312 411626
371486 373140 372550 372260
309974 310152 310312 310799
216248 215514 215628 216866
111572 111127 110843 111617
39689 39660 39824 39703
6118 6248 6430 6182
43 38 34 44
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
