A = [
1091390 1078078 6579627 956579 924058 874759 863463 850453 851611 852956 869381 895727 934395 975920 1028250 1085719 1142110 1206621 1272542 1334381 1394332 1456494 1509128 1563681 1613941 1815878 1866024 1902509 2086199 1951386 2003420 2027721 1874861 1917490 1900438 1898397 1883464 1838080 1817062 1787489 1759923 1733275 1704034 1686821 1665219 1646233 1635032 1620623 1606241 1599709 1587276 1576225 1565627 1559362 1549831 1539060 1530000 1521523 1511622 1503846 1495263 1485476 1483094 1474627 1463879 1463518 1457302 1539552 1536800 1532259 1611436 1607314 1600388 1588642 1575985 1562509 1554034 1542833 1529677 1515792 1502383 1491239 1476804 1460991 1452888 1439758 1424687 1411409 1397548 1386913 1369678 1357856 1346308 1329245 1317824 1305233 1286677 1274968 1262166 1248231 1233694 1220427 1205850 1194863 1178665 1165565 1152212 1139372 1124945 1113211 1101428 1089381 1073596 1060618 1049692 1038556 1025567 1012470 1002143 988733 979237 967386 955673 946599 933692 920080 909411 899772 890245 877394 867745 856567 847128 836140 823748 814691 805776 796112 786255 776250 765080 755123 746256 736770 727244 717660 707917 699299 691822 684412 673735 666753 658246 648828 640669 631113 622959 615849 608439 601061 592376 584391 577269 569609 561171 554198 547409 540777 534114 526407 520841 513380 506886 499794 493707 486165 478516 475580 468050 461852 455500 449090 443577 438179 431869 427262 422197 415270 410886 404894 399902 393701 389334 383743 378253 373717 369079 365200 359516 355946 349842 344799 340000 337321 332626 328356 322691 318554 315032 310947 307304 304433 298926 295647 290800 287437 282202 279994 276326 272543 268873 266023 261702 258617 255217 251223 248690 244807 241504 238112 235153 232270 230331 226569 222293 220736 217337 215030 212474 209367 206579 204389 200903 198574 194934 193426 190165 187770 185784 182526 179678 177510 175576 173361 171854 169498 167248 165013 163048 160259 158093 156266 153875 152258 149836 147680 146082 144791 142933 140400 138367 136944 135059 133125 131018 129995 128051 126399 124606 122839 121067 119910 118625 117211 115441 113376 111880 111195 110146 107984 107066 104817 103713 102380 101291 99585 97927 96708 96202 94863 93635 91726 91040 89534 89206 87722 85713 84988 84089 83048 82368 81040 80268 78901 77828 77148 75707 75432 73725 73875 71875 71511 70107 69546 67884 67177 66403 65864 64657 64255 63677 62636 61831 60762 59687 59643 58742 57882 57198 56580 55717 54816 54324 53959 52916 52210 51762 51112 50262 49801 49330 48404 47930 46940 46568 45987 45472 44867 44777 44148 43299 43003 42671 41655 41314 40653 40313 39125 39107 38953 38587 37822 37474 36896 36333 36148 35431 35150 34689 33981 34059 33501 32597 32710 32169 31603 31680 30774 30768 30354 30157 29763 29430 29004 28741 27939 28053 27317 27057 26768 26228 26113 25903 25447 25415 24771 24722 24615 24033 24027 23472 23120 22739 22680 22232 22091 22214 21699 21198 21358 20881 20699 20629 20483 20100 19890 19752 19369 19177 19159 18771 18682 18339 18166 18165 17921 17549 17513 17164 16991 16895 16655 16754 16359 16150 15868 15931 15624 15423 15240 15180 15152 14873 14537 14771 14282 14313 14103 14008 13764 13815 13612 13339 13405 13011 13033 12703 12955 12573 12278 12359 12079 11825 11797 11807 11646 11864 11546 11307 11091 10910 11057 10725 10680 10730 10772 10376 10396 10223 10188 10136 10057 9883 9778 9580 9713 9392 9410 9486 9284 9218 9097 9168 8910 8892 8733 8704 8582 8393 8703 8255 8206 8185 8185 8133 8070 7903 7985 7807 7888 7624 7657 7420 7555 7405 7288 7384 7114 7126 6997 7115 6882 6863 6896 6817 6936 6604 6826 6602 6494 6387 6269 6543 6296 6143 6357 6281 6218 6013 5966 5984 5938 5991 5835 5805 5816 5673 5644 5648 5569 5408 5583 5360 5451 5430 5288 5361 5244 5139 5205 5203 5171 5252 5041 4962 4982 5080 4790 5050 4816 4959 4784 4710 4696 4672 4690 4562 4513 4517 4390 4424 4298 4403 4362 4376 4420 4224 4231 4231 4337 4130 4159 4243 4096 4109 4018 4034 3973 3986 3888 4096 3836 3835 3888 3835 3701 3746 3747 3758 3696 3631 3607 3603 3566 3697 3514 3602 3501 3464 3432 3451 3440 3521 3376 3377 3348 3161 3293 3309 3290 3283 3137 3091 3258 3254 3209 3145 3159 3112 3095 3090 3038 3024 2957 2991 2900 3012 2953 2913 2890 2934 2960 2861 2842 3041 2819 2791 2728 2832 2903 2786 2648 2656 2807 2766 2521 2617 2724 2586 2590 2568 2518 2655 2536 2386 2506 2521 2491 2453 2460 2389 2441 2415 2392 2310 2458 2384 2338 2331 2333 2372 2237 2275 2214 2277 2283 2204 2217 2208 2225 2223 2197 2125 2214 2190 2134 2188 2143 2127 2024 2116 2103 2080 2009 2060 2079 1902 1962 2007 2011 1899 1985 1998 1914 1886 1910 1855 1950 1974 1948 1903 1889 1933 1854 1912 1804 1790 1780 1866 1815 1823 1887 1751 1709 1712 1697 1810 1724 1732 1733 1685 1705 1709 1704 1725 1607 1699 1635 1564 1673 1621 1569 1608 1589 1619 1569 1620 1543 1601 1576 1530 1473 1484 1535 1583 1536 1472 1504 1472 1515 1481 1375 1526 1500 1459 1460 1499 1445 1392 1403 1457 1421 1437 1364 1394 1371 1406 1354 1364 1326 1389 1428 1409 1301 1310 1305 1276 1283 1258 1285 1319 1289 1307 1297 1280 1234 1251 1313 1241 1285 1215 1223 1226 1280 1191 1242 1213 1216 1195 1232 1163 1215 1205 1190 1143 1113 1198 1152 1160 1176 1148 1105 1128 1162 1133 1157 1091 1104 1055 1142 1055 1056 1063 1089 1074 1058 1056 1022 1048 1063 1035 1045 1035 1016 999 982 1007 1003 1001 992 925 1035 986 979 918 1033 1045 932 972 1048 983 972 973 991 912 926 939 924 953 879 876 884 910 845 890 856 869 846 867 911 956 876 854 817 869 852 835 825 830 804 844 852 868 823 815 794 794 788 774 834 807 815 804 792 817 811 753 772 788 724 780 761 783 730 746 730 758 689 691 750 731 705 721 696 724 722 719 710 725 703 649 694 651 737 628 672 659 660 584 677 628 683 646 676 646 646 656 638 624 598 642 631 629 607 630 651 608 632 607 619 572 636 588 571 624 550 602 589 601 558 575 559 534 593 622 623 584 520 572 574 576 538 577 549 586 521 527 553 551 538 593 503 591 555 513 479 537 494 494 493 545 500 522 543 536 499 539 526 503 536 486 551 541 460 468 516 516 467 472 484 472 490 444 491 418 446 418 410 448 439 494 461 455 448 452 448 418 451 486 442 456 427 416 427 417 464 434 413 421 413 446 422 396 409 406 355 384 398 401 378 388 368 358 361 386 373 393 401 352 384 377 332 391 373 360 360 373 365 391 347 370 344 335 332 361 353 325 383 319 334 310 350 338 316 357 327 333 309 302 311 321 314 288 328 290 325 308 269 278 334 330 310 278 353 330 313 290 336 333 294 319 283 272 275 286 288 298 294 308 291 284 279 319 276 276 281 276 279 271 245 281 278 298 256 253 238 275 258 268 276 308 271 277 238 236 208 255 250 250 244 258 224 249 250 271 223 280 242 243 231 208 218 229 258 227 236 241 219 228 215 233 236 223 213 218 204 185 223 215 221 185 216 194 206 183 196 205 219 192 203 194 202 221 198 203 215 215 215 197 190 200 203 195 166 189 186 200 190 181 214 190 187 221 199 190 192 201 198 194 162 168 180 180 182 191 177 185 161 170 184 190 191 163 163 167 175 157 165 173 168 180 182 165 175 182 178 165 187 185 175 168 169 168 174 150 158 148 151 158 146 146 164 169 161 146 141 155 161 134 140 162 143 150 150 150 147 154 170 139 130 151 140 121 132 154 137 129 139 109 158 145 130 119 109 135 123 133 145 138 134 129 111 125 136 144 118 130 135 118 131 129 126 124 137 122 111 138 120 105 120 144 112 128 111 116 109 117 97 117 111 126 102 103 108 120 110 130 109 103 105 112 114 123 113 114 103 110 121 103 103 100 93 99 106 108 90 72 109 102 103 90 90 101 100 95 103 104 90 99 102 94 78 97 96 107 89 100 83 86 90 83 86 95 95 83 100 90 75 69 94 74 83 96 83 89 88 87 92 111 104 87 93 105 69 79 76 88 75 71 58 106 90 75 83 72 76 81 61 77 69 65 65 68 81 89 77 77 66 66 74 68 78 78 75 86 71 74 77 78 83 68 68 75 79 73 77 60 74 56 54 74 73 64 69 71 65 71 54 72 68 59 68 70 55 60 55 71 59 72 66 62 52 69 61 58 66 55 71 59 44 60 63 57 51 55 64 69 54 47 62 53 54 49 62 61 51 60 62 66 59 64 62 61 52 60 52 51 53 62 63 50 53 82 51 44 54 36 66 61 52 48 56 58 49 58 48 57 42 45 65 43 45 46 45 45 32 41 50 39 48 44 41 42 60 54 54 52 45 59 44 46 38 32 45 44 48 42 56 46 47 59 44 50 36 39 53 45 39 36 54 53 60 43 33 43 39 41 42 43 29 40 38 39 53 43 45 41 36 49 36 40 39 37 43 28 44 34 38 28 36 34 35 36 42 31 36 30 38 40 41 45 30 35 31 42 31 27 36 26 31 39 39 26 34 40 37 36 41 36 25 36 38 36 32 30 29 29 36 39 23 33 30 30 32 28 34 25 36 29 40 19 32 23 26 21 30 31 21 35 37 32 21 23 17 26 14 24 25 24 22 19 28 23 26 24 24 22 21 23 32 27 16 17 25 22 24 34 23 22 32 21 31 24 31 20 18 23 28 14 24 18 23 26 30 29 21 19 31 22 11 14 14 21 18 18 20 22 17 14 21 21 22 26 14 20 24 22 18 23 15 28 19 17 13 24 18 17 14 15 29 26 13 14 26 12 15 14 17 17 18 20 18 21 24 20 14 13 18 13 22 21 14 18 19 17 14 17 9 15 19 12 8 14 18 12 12 18 14 18 17 20 7 20 15 17 24 14 9 24 17 12 25 19 13 13 25 21 15 14 14 15 23 12 14 12 17 11 9 18 21 14 14 19 19 19 20 18 16 17 21 20 12 15 7 9 16 15 14 20 17 6 12 11 10 12 10 18 15 17 15 14 10 15 21 14 20 10 14 6 10 11 9 6 8 13 11 17 18 13 3 11 10 7 8 4 11 9 10 7 19 9 10 7 13 9 9 7 14 10 11 8 14 2 9 9 14 16 6 9 9 11 10 8 11 7 9 9 6 7 6 9 9 8 6 12 5 7 13 15 7 5 11 8 8 6 9 13 6 4 13 9 6 8 13 6 8 6 5 7 8 7 3 9 2 11 7 10 6 8 3 5 5 11 6 7 9 13 7 9 7 11 7 9 9 7 9 7 9 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
 636314 490812 145502
 605825 468235 137590
 673575 520183 153392
 669866 517300 152566
 855807 662250 193557
 661656 513018 148638
 758426 588232 170194
 1584158 1231968 352190
 727650 566053 161597
 866314 676044 190270
 1432996 1116738 316258
 899613 700889 198724
 1359610 1060621 298989
 747031 584434 162597
 917598 718580 199018
 1411822 1103746 308076
 906976 711874 195102
 1380613 1081932 298681
 949706 745494 204212
 1375843 1079732 296111
 905211 713262 191949
 1359819 1068987 290832
 1029816 809805 220011
 1369385 1078426 290959
 945476 746709 198767
 1474844 1162059 312785
 1373151 1083272 289879
 942723 746701 196022
 1388216 1096663 291553
 829541 657814 171727
 97895815 79497160 18398655
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
95 210 105 14
16 27 2 3
21 55 2 3
16 66 2 3
19 58 5 5
20 86 4 9
175 116 25 23
1126 116 25 20
19450 123 53 29
176466 162 234 83
568131 199 1935 382
1367181 281 2901 1070
2603500 406 3744 1873
3892827 600 5251 3431
4425030 1007 7141 5673
4356142 1830 10632 9653
3638541 3246 14625 13652
2651523 5302 20633 19965
1675941 8738 28768 28237
840710 13675 38135 38203
328214 20379 49525 49659
119668 30152 62271 62439
83223 43838 76998 76907
93452 62623 93137 92587
110791 84447 112103 111983
131664 110800 133995 133961
156573 139524 158237 158438
183020 169903 185540 186222
211451 201026 216217 215806
240664 231720 244867 245639
267964 259929 272198 272148
293464 284884 296989 296523
315985 306396 317784 318084
328488 325091 335135 335073
338810 336832 347186 346795
348410 348673 356341 357506
355844 356902 364685 365392
364952 364098 371466 373017
372568 373027 381184 381348
382005 383602 389790 389952
395159 395693 401289 401763
408241 409299 414314 415293
424587 425777 430498 431204
442718 443661 447734 448763
461439 463146 468124 465740
482027 482886 484979 486845
498620 500173 503347 503940
513560 514244 516624 516570
522107 523712 524352 525348
524476 525018 525764 526831
519738 521296 523402 522088
511051 511247 511181 510527
492626 492343 493601 492010
468289 469996 467920 468860
438665 440370 438701 439135
407090 406863 406598 407920
372768 373700 372677 372246
340124 340211 338662 339997
308674 307599 307230 308328
279766 279881 279691 279592
255886 256882 255922 255253
239228 238499 239835 239713
225957 226815 226882 228595
217988 217548 217395 218019
219760 218373 218217 218613
228867 229210 227782 227957
244432 245746 244373 245564
264758 265202 264883 264518
294265 294775 295074 295068
330299 330981 330670 330311
378456 378046 375965 378222
403139 402096 403927 403317
428655 428305 428287 427899
443012 441856 443090 442635
437397 436564 435112 436461
396218 394476 395417 395159
329797 329049 328203 329291
229741 230183 228961 230001
119670 119558 118340 118993
42948 43029 42979 42871
6821 6642 6746 6629
53 59 55 51
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
