A = [
2863296 3247586 56137184 2515757 3375927 2752758 2476179 3102052 2662270 2816805 2940899 2631539 2997277 2802246 2791127 3027301 2665578 2975101 3035543 2689321 2782544 2747209 2600995 2661113 2580844 2494956 2638822 2561498 2501435 2482886 2539429 2588326 2460598 2487323 2542777 2543371 2518556 2447169 2458338 2623616 2493898 2489966 2627123 2549333 2572677 2522803 2448473 2606624 2505498 2459218 2493371 2267535 2321679 2295407 2159875 2062898 2118003 2212725 2029340 1949954 2042285 1973751 1942312 1903840 1855937 1891136 1824825 1781216 1795987 1737791 1726695 1737540 1700036 1713215 1731737 1705068 1695478 1696935 1641267 1590281 1576920 1572046 1518887 1494873 1506683 1448867 1386498 1291354 1247972 1244556 1220127 1197733 1199019 1177779 1163658 1158549 1149999 1140842 1123536 1107952 1105516 1088943 1074926 1069402 1060507 1055169 1046964 1035146 1029657 1018100 1009586 1009048 1002760 1000070 993465 988637 992981 982077 966815 969589 972349 958588 952565 950288 943019 933970 928314 918999 911066 903731 894485 883413 877465 868708 869863 857933 845634 851069 839946 822665 818425 814085 804697 798993 788190 782613 777898 767034 756657 749405 740806 735362 727625 715841 706566 698654 695254 686380 675269 670596 663921 657084 643435 637787 633074 624346 620131 613750 609705 603198 592475 591709 590586 586277 597273 579351 571362 574189 554023 546669 537773 533181 534228 523969 522502 521170 511108 510821 508955 507059 504936 498532 499716 494932 489444 485417 480306 481107 477778 472323 469672 469510 463942 460840 460941 458334 459319 453993 449433 445907 437518 430229 427906 420646 424285 422173 418913 424232 419128 416083 415431 410009 405246 399926 388488 380581 369141 358536 346392 336861 327399 320935 318065 309442 305685 302367 299453 296384 292981 291797 288921 284962 281265 277596 274460 270411 267345 263710 260725 257101 252647 248751 244661 242112 237304 234089 230881 227560 224015 221513 218755 215083 212796 209099 206624 203893 200968 198988 196217 192804 191220 189086 186165 183911 180947 179499 177314 174667 172535 169365 166766 165196 162905 160646 159764 157612 155020 152909 151313 149173 147359 145573 143544 142573 139768 138548 136544 134847 133105 131425 129889 127597 126494 125002 122958 121805 119667 117792 116733 115014 113701 112263 110736 109217 107722 106057 104815 103505 101930 100613 99632 98200 96205 95253 94861 92767 91399 90861 89820 87982 87100 86538 84952 83981 81986 81414 80264 79045 78063 77567 76367 75421 74017 73095 72523 71371 70152 69388 68180 67717 67094 66142 64836 64302 63250 62958 62155 60867 59879 59363 58355 57312 56963 56036 55570 54954 53805 53386 52505 51346 51293 50079 49402 49147 48207 47773 47316 46772 46288 45360 44934 43976 42904 42171 41912 41630 40902 40499 39616 39342 39215 37861 37594 37087 36564 36317 35118 35086 34416 34123 33628 33184 32837 32479 31981 31361 31102 30621 30518 29519 29194 28846 28527 28371 27823 27359 27001 26854 26116 25949 25709 25109 24679 24456 23886 23685 23431 23374 22908 22715 22316 21857 21581 21440 21222 20980 20161 20087 19900 19702 19252 19048 18652 18449 18360 17811 17696 17445 17320 16855 16605 16748 16371 16190 15626 15796 15458 15245 15204 14773 14899 14366 14173 14144 13892 13659 13400 13058 13220 12932 12919 12754 12298 12194 12151 12104 11812 11861 11488 11429 11253 10920 10805 10552 10423 10290 10073 10070 9815 9748 9659 9498 9380 9218 9197 9173 8947 8926 8976 8623 8368 8275 8429 8106 8057 7750 7750 7548 7481 7527 7210 7525 7398 7085 7028 6876 6767 6880 6679 6548 6391 6276 6409 6223 6199 5981 6119 5828 5811 5643 5661 5451 5460 5357 5368 5215 5236 5049 4974 4859 5011 4930 4722 4788 4593 4544 4534 4507 4380 4217 4183 4214 4161 4142 3961 3980 3794 3792 3788 3669 3603 3627 3692 3514 3454 3395 3339 3356 3309 3269 3224 3098 3090 3137 2960 3001 2884 2855 2875 2861 2817 2833 2866 2705 2710 2552 2599 2662 2450 2526 2417 2523 2478 2435 2375 2286 2313 2284 2231 2143 2102 2089 2132 2004 2171 2063 1995 1963 1999 1936 1941 1862 1810 1826 1755 1806 1746 1745 1660 1620 1671 1667 1684 1559 1604 1596 1525 1531 1449 1556 1517 1480 1539 1387 1350 1364 1475 1445 1402 1329 1330 1316 1304 1192 1259 1212 1308 1174 1240 1246 1098 1110 1151 1129 1167 1038 1117 1116 1054 1042 995 1050 1056 994 1021 967 923 941 965 940 875 856 882 864 876 893 893 873 796 869 824 789 813 773 763 782 767 742 762 799 724 704 696 718 654 697 680 691 660 623 696 687 601 631 644 597 600 607 583 567 581 562 567 550 594 576 532 493 551 523 513 526 516 490 507 521 508 426 503 458 510 457 475 471 456 455 461 432 457 389 461 426 446 422 425 408 381 408 421 424 405 379 376 396 369 389 398 343 352 321 352 371 388 335 341 351 353 333 327 338 354 292 350 536 294 337 321 277 313 307 289 328 271 264 315 292 282 269 283 259 245 259 229 255 246 274 249 257 288 260 251 224 251 271 254 226 276 290 248 276 244 243 248 236 256 195 223 231 210 210 205 229 216 248 213 214 199 183 230 213 185 219 219 197 211 173 180 185 188 184 186 177 159 173 175 162 175 161 149 186 163 168 154 170 174 171 163 131 137 143 151 146 147 156 146 165 129 156 169 149 145 128 141 151 147 136 148 125 119 138 121 136 124 124 124 116 127 134 125 123 126 129 112 122 126 104 125 110 132 121 107 112 118 98 127 91 119 98 108 136 105 108 108 103 102 109 96 117 128 107 91 107 107 97 94 102 98 102 119 100 96 97 95 114 116 104 91 91 96 112 89 104 101 114 110 85 93 81 88 116 97 90 98 88 79 96 72 94 75 80 86 81 76 71 103 86 102 85 76 97 87 99 86 95 72 91 101 74 88 81 77 69 72 71 86 79 67 63 84 64 82 67 59 71 83 76 84 90 74 71 68 70 83 65 78 61 74 69 53 70 74 72 50 57 60 51 73 72 59 54 67 63 50 60 54 56 53 62 86 54 68 55 60 54 55 73 60 65 59 58 46 58 64 83 65 76 78 73 88 99 94 129 156 231 375 422 458 515 467 489 549 544 544 557 601 440 359 362 350 341 376 329 336 333 282 303 297 275 315 317 322 313 318 351 308 329 320 351 345 308 346 310 294 280 278 294 317 308 324 277 297 362 328 342 352 490 409 436 461 447 466 455 420 435 455 1190 488 441 355 346 261 285 305 229 218 206 203 185 228 176 159 197 178 143 156 125 148 106 123 124 106 126 132 102 106 123 129 111 117 138 112 126 112 138 203 226 213 469 337 1441 1204 1126 703 558 501 531 513 350 242 193 125 92 124 136 119 99 111 118 124 85 90 79 129 151 1057 74 52 70 57 62 52 46 38 36 37 39 28 36 38 39 42 31 34 41 29 44 39 49 69 51 55 48 53 62 53 74 54 58 69 89 83 75 77 77 76 81 73 74 66 94 71 92 90 83 90 98 88 90 103 102 88 71 113 125 82 114 113 105 125 93 90 102 109 113 148 133 106 108 136 119 106 129 109 97 126 139 120 131 115 127 151 144 124 122 98 112 142 128 133 125 118 151 172 158 142 147 134 162 146 136 145 141 137 135 147 140 147 135 158 161 148 131 131 153 147 166 164 159 161 169 164 183 157 149 147 167 126 124 137 132 138 141 145 132 110 119 82 80 68 71 94 76 77 104 93 197 132 191 339 145 110 94 72 61 72 86 75 59 73 92 80 62 57 74 54 83 70 55 68 83 91 88 66 61 60 54 80 100 114 120 90 96 117 124 110 102 85 126 112 121 110 86 110 100 104 98 99 97 86 99 96 83 101 89 85 81 128 116 109 93 103 126 106 138 88 108 101 124 94 85 81 82 70 61 71 65 51 80 298 72 59 56 58 45 49 43 41 46 35 38 37 55 35 40 36 42 34 20 39 41 38 29 31 32 28 29 35 26 29 28 24 23 25 22 36 21 31 30 30 27 25 41 26 20 26 22 17 21 21 19 21 19 20 18 26 20 18 24 22 24 21 19 27 35 26 23 29 20 26 44 33 33 34 21 24 27 18 17 27 12 10 17 18 20 21 14 15 13 17 15 10 15 15 13 24 12 16 19 16 23 24 14 16 28 29 15 27 22 20 22 23 23 24 22 15 23 17 29 25 24 13 24 28 26 38 19 27 33 26 28 34 21 29 36 30 38 31 38 25 35 37 34 34 28 36 45 40 40 36 31 28 34 30 29 33 34 34 35 30 31 31 28 29 51 39 36 51 28 42 46 42 30 41 33 30 41 38 36 38 40 32 25 27 32 31 35 32 37 38 26 43 38 47 39 38 37 30 42 20 35 32 39 42 19 27 21 44 42 30 26 47 20 28 30 28 35 36 37 31 31 37 22 27 26 13 18 14 23 23 19 14 13 18 16 20 14 5 13 13 4 14 6 11 10 12 15 9 6 9 6 10 11 11 7 15 12 27 12 13 14 8 9 9 13 17 9 10 2 17 9 16 15 12 6 13 13 12 7 16 9 12 12 5 7 13 10 6 18 17 18 14 17 7 16 12 12 6 8 15 8 9 11 8 7 16 13 9 7 16 3 15 14 17 11 14 30 8 9 8 13 11 16 8 13 12 15 6 7 13 10 13 9 8 11 6 9 4 8 7 7 7 13 9 6 13 8 8 7 11 12 22 11 11 7 7 9 10 8 8 8 7 9 8 9 10 4 6 9 12 14 15 8 7 10 16 6 10 5 7 8 10 7 8 14 13 9 9 8 8 11 8 4 4 5 6 8 4 7 7 4 2 6 6 13 13 13 9 5 4 8 6 17 7 10 7 8 5 4 3 5 6 10 6 4 9 3 7 7 3 6 11 7 9 12 3 10 12 8 12 9 11 7 13 5 7 7 13 9 10 12 12 10 8 8 6 12 15 15 9 12 13 23 16 14 13 12 12 12 13 18 14 13 13 15 14 17 14 8 10 10 18 6 12 12 8 7 10 7 8 5 8 11 3 11 8 7 8 13 4 10 14 9 9 13 11 8 10 4 7 15 10 14 9 9 13 14 10 8 10 9 10 10 5 7 6 4 13 14 10 4 11 12 8 7 11 5 9 7 9 4 10 9 18 10 6 9 5 8 12 8 6 10 17 6 11 8 6 19 7 9 7 12 4 8 11 9 4 7 9 9 12 10 6 6 12 7 6 8 11 9 
];
B = [
0 0 0
 1897115 725913 1171202
 2735268 1357996 1377272
 1804001 783273 1020728
 1492437 647388 845049
 1235985 523982 712003
 792004 340408 451596
 469772 190041 279731
 499945 215067 284878
 873012 365790 507222
 2048416 1143184 905232
 1582851 774424 808427
 1519890 773141 746749
 1465230 758829 706401
 1379083 725617 653466
 1759673 1024245 735428
 1487629 821942 665687
 1456019 807293 648726
 1410241 785192 625049
 1379788 766641 613147
 1615206 946905 668301
 1419226 804765 614461
 1417732 809691 608041
 1369886 783836 586050
 1342312 769252 573060
 1516858 895933 620925
 1352626 786374 566252
 1356991 787023 569968
 1338720 781829 556891
 1329485 777715 551770
 1446267 856295 589972
 1340348 794263 546085
 1313967 778234 535733
 1312042 777792 534250
 1292781 769844 522937
 1374960 825710 549250
 1292998 774394 518604
 1374492 810223 564269
 1265326 760485 504841
 1273312 765745 507567
 1375959 822494 553465
 1242660 754109 488551
 1287886 773432 514454
 1203732 732914 470818
 1183500 722674 460826
 1301653 788774 512879
 1181219 724712 456507
 1228066 751658 476408
 1164393 720239 444154
 1181849 726354 455495
 1164266 723615 440651
 1164852 724605 440247
 1118358 699914 418444
 1132002 706389 425613
 1079915 682026 397889
 1132632 714412 418220
 1085444 683943 401501
 1051872 667994 383878
 1072219 683541 388678
 1035205 664571 370634
 128627153 111307264 17319889
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
25 23 0 1
6 1 0 0
10 20 0 0
8 20 0 1
22 11 0 0
22 25 1 0
76 37 0 3
296 44 1 2
157797 60 2 1
1370426 90 2 0
3408082 86 5 2
7454783 108 10 10
13234882 134 41 21
20730211 139 197 92
25470914 186 242 155
26963283 279 345 289
21662273 445 673 672
14818524 687 1124 1092
8971489 951 1740 1677
4260905 1316 2210 2208
1438128 1610 2730 2770
299291 2180 3210 3168
30209 2936 3798 3712
5856 3637 4371 4397
6004 4477 5199 5222
6528 5467 5797 5810
7633 6490 6659 6690
8505 7622 7619 7540
9186 8396 8396 8259
9844 9279 8949 9072
10491 10138 9550 9785
11264 11086 9999 10188
11124 10744 10396 10450
11191 11077 10695 10750
11842 11736 10890 10850
12080 11532 11183 11062
11410 12188 11151 11135
11610 11680 11482 11452
11897 11974 11250 11400
12075 12169 11589 11777
12400 12320 11617 11961
12557 12726 12219 12367
13099 13184 13247 13369
13333 13395 13490 13243
14072 14528 13873 13843
14724 14647 14623 14717
15475 15134 15284 15180
15872 15804 16107 16301
16736 16696 16728 16875
17518 17200 17375 17429
17888 17928 17987 18092
17863 17845 18164 18647
18447 18769 18715 18985
18150 18132 18538 18649
17998 18179 18061 18206
17990 18115 18115 18302
17509 17756 18114 18200
17319 17482 17432 17435
16919 17142 17543 17388
16879 17156 17501 17498
17230 16987 17311 16994
17853 17916 17806 17884
18340 18258 18866 18833
19551 19802 19923 19763
21242 21215 21484 21696
23272 23245 23839 23733
26430 26377 26439 26436
31740 31927 30764 30752
32675 32678 33156 32727
37187 37322 37073 37357
40542 40531 40652 40502
45728 45485 47454 47328
50349 50342 50703 50194
53257 53460 53965 53694
54825 54786 54510 54801
57986 57786 57499 57128
54105 54490 54505 54840
45902 45522 45994 45686
44848 44767 44678 44335
42802 42151 42365 42801
24645 24551 24715 24756
14790 14695 15093 14969
1024 964 955 961
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
