A = [
1311939 1287503 6953049 1294048 1270948 1178442 1191417 1180728 1246763 1191739 1249798 1314450 1439276 1577406 1765511 1972203 2038611 2137123 2183685 2103991 2001740 1945172 1898918 1869751 1866942 2218712 2247784 2236765 2495125 2152786 2179995 2139197 1808341 1832633 1821806 1830290 1796681 1748486 1736251 1728407 1738102 1731669 1718570 1777875 1784052 1766351 1774969 1743832 1786210 1778822 1749454 1749600 1776485 1782620 1759939 1759640 1723068 1747819 1736669 1668499 1660336 1675390 1671956 1660499 1665725 1678682 1658460 1654218 1652251 1634098 1662579 1679138 1691534 1701632 1714770 1719930 1707171 1696901 1664507 1641769 1625129 1605609 1591171 1585469 1578265 1563005 1543535 1507299 1490515 1479237 1466759 1456823 1450990 1444783 1438604 1437846 1425872 1418658 1413312 1394773 1378319 1377329 1365849 1357259 1358046 1358571 1353692 1347289 1338197 1330714 1315506 1304470 1301544 1294417 1292336 1290844 1291767 1284641 1278402 1270621 1261994 1253010 1245979 1238737 1236991 1231797 1226391 1221477 1213588 1205890 1198397 1188195 1180738 1175955 1170904 1166152 1161126 1156115 1152101 1144440 1136226 1131311 1121739 1116879 1112219 1104255 1101611 1098280 1094839 1090221 1085244 1075247 1070688 1062931 1057872 1049552 1046524 1043310 1035578 1028690 1024700 1017096 1006127 1001107 994801 991290 988158 982980 979406 973054 969949 961320 955113 950878 944596 941090 938907 933461 928458 922617 916179 910759 907011 905176 899147 896551 890433 887458 881950 879878 879351 872831 868003 865060 860989 855382 852661 849262 846333 841832 837638 836186 830966 827448 822862 820999 816413 814258 809547 805037 798266 791780 784552 778441 774616 771775 764996 761695 761524 757918 754932 751614 748354 748670 742031 736367 729125 719259 713665 706118 698720 693526 690220 686647 678918 673688 669711 664923 659476 655220 651891 646694 642599 638849 636043 630848 627818 623320 618402 615971 610874 605752 604125 599560 593604 590787 585747 583732 580504 575002 571870 567237 564263 559511 555480 552961 548250 543419 540341 535895 531699 528852 525908 522043 518370 516303 509461 509426 504839 500843 496634 492465 490558 485826 482073 478957 476840 471483 468781 465697 461165 458998 454278 452986 449456 444355 440987 437663 433990 430380 426477 422886 420155 416353 412103 409374 405957 401880 398484 395268 391619 389516 385782 381397 379407 374214 371390 368425 364170 360831 356536 353286 351010 346949 344297 340868 336631 335179 331547 327779 324666 320704 317757 313744 310961 307696 303906 301079 297629 295213 291839 288259 283389 281187 277502 274433 271680 268717 264944 262107 259421 255492 252632 250262 246011 244038 240803 237288 234870 231898 227940 225022 221971 219546 216631 212435 209348 207583 204578 201700 198549 195101 192540 190455 187025 183777 180503 178492 176486 173123 171203 168094 164958 162723 160303 157718 155107 152359 150262 147378 145604 142416 140830 138468 135500 133525 131059 128754 126299 124114 121949 120633 118084 116144 113643 112479 109136 107583 105680 103590 102398 100561 98108 96289 94716 92393 91002 89473 86957 85351 83812 82697 80465 79290 77896 76561 74729 73007 71951 70113 69097 67705 65661 64774 63716 62334 60637 60025 58056 57432 56524 54555 53931 52405 51624 50431 49154 48048 46852 46588 44721 44136 43337 42073 41455 40395 39814 38584 38162 37536 36058 35737 34628 33664 32814 32312 31535 31082 30645 29803 28842 28353 27838 27230 26340 26105 25224 24421 23856 23270 22698 22457 21614 21304 20831 20731 19930 19260 18881 18445 18174 17778 17385 16875 16450 16138 15764 15407 14921 14592 14030 13994 13607 13217 12799 12613 12272 12138 11541 11457 11046 10602 10547 10426 10084 9810 9501 9186 9125 8864 8820 8634 8186 8055 7827 7638 7454 7259 7153 6998 6774 6652 6400 6273 6098 6088 5866 5617 5558 5427 5340 5222 4956 4903 4831 4690 4698 4419 4324 4392 4210 4147 4014 3933 3879 3825 3719 3496 3472 3506 3353 3224 3177 3094 2980 3048 2832 2841 2817 2812 2678 2610 2533 2454 2450 2305 2356 2260 2303 2210 2083 2142 2034 1986 2027 1915 1911 1877 1936 1831 1691 1742 1635 1659 1564 1585 1508 1457 1495 1480 1489 1405 1410 1417 1343 1262 1398 1274 1294 1294 1240 1101 1155 1077 1130 1153 1083 1090 1042 1026 1001 997 978 1053 959 927 927 840 927 862 912 873 905 891 826 835 723 812 773 761 753 747 690 812 690 667 748 692 693 650 663 705 612 641 657 666 646 632 664 667 644 581 591 565 617 619 610 596 609 541 625 585 590 564 563 544 534 565 544 530 553 514 529 502 533 500 491 519 524 516 438 495 471 476 510 487 462 481 428 447 505 470 449 415 431 425 421 468 408 461 440 460 451 453 416 415 436 470 428 415 417 435 418 425 405 417 418 419 386 377 374 397 384 447 417 498 390 378 470 443 428 438 439 372 394 383 478 438 376 423 431 471 426 350 348 389 402 414 338 388 335 330 349 386 318 361 344 303 329 335 313 324 318 400 355 335 300 354 281 347 378 314 309 316 301 318 301 305 293 321 279 356 289 298 302 375 299 299 310 343 384 314 308 289 243 329 342 293 282 296 346 299 259 339 299 294 298 302 273 260 235 258 263 241 283 255 252 231 237 233 258 235 243 259 271 263 244 244 236 256 239 247 245 237 260 234 221 229 237 220 246 231 197 227 203 223 226 212 242 293 237 221 243 222 247 260 230 231 206 212 276 185 225 210 243 233 238 233 222 200 179 226 213 218 219 211 220 225 241 217 182 178 208 219 237 216 188 189 195 216 191 219 177 184 205 185 189 202 211 199 179 203 192 182 176 198 175 203 171 196 189 180 213 199 192 180 172 173 184 210 209 194 182 166 205 178 180 179 175 179 145 175 165 214 171 165 161 171 140 159 171 158 154 183 160 176 176 171 172 156 163 138 138 153 154 156 138 149 157 155 135 164 164 154 163 143 141 109 127 118 141 139 117 151 135 136 141 137 139 146 147 117 136 131 143 155 151 155 129 142 134 147 118 131 154 141 127 130 133 130 126 145 133 137 157 132 133 143 143 142 134 124 126 125 142 111 128 105 117 135 101 119 108 102 110 120 126 123 119 130 141 139 112 101 95 107 147 93 100 94 119 176 122 126 101 108 149 109 119 115 129 104 105 118 100 96 116 129 101 99 109 114 99 84 88 96 121 107 104 94 94 101 116 82 99 89 108 121 120 108 86 118 111 83 81 88 103 98 107 88 81 90 94 94 83 93 145 117 108 108 99 118 107 102 132 97 82 74 102 130 105 84 93 94 112 106 97 107 109 97 119 127 154 115 112 123 102 117 138 107 126 100 153 133 129 111 131 114 99 73 88 78 86 81 70 73 64 248 89 81 101 80 73 84 77 69 79 79 60 62 81 82 104 57 73 83 74 73 76 85 62 79 83 78 80 94 80 68 83 62 75 68 70 62 79 80 72 68 67 65 85 67 64 72 72 83 74 77 78 73 89 63 68 60 58 103 79 77 51 62 69 66 57 62 72 79 65 67 57 64 48 62 95 71 62 65 71 80 66 56 90 80 71 53 57 66 73 80 68 83 84 60 76 78 82 62 83 68 79 74 69 68 97 64 90 69 75 84 71 119 119 115 112 89 104 80 145 128 103 129 91 81 92 126 127 82 105 125 103 100 75 107 90 83 107 102 111 110 91 97 66 95 98 80 79 97 97 97 73 111 85 93 94 80 85 74 113 90 74 73 99 80 73 63 67 68 49 66 50 67 89 58 56 49 56 44 43 40 35 40 48 38 49 45 39 43 44 29 32 42 33 38 38 40 50 24 28 38 33 37 29 42 36 36 35 35 36 37 37 46 36 44 34 40 37 36 35 42 42 30 43 34 33 35 31 43 28 29 19 39 36 30 45 30 47 39 32 36 30 35 33 31 33 33 26 37 17 29 28 33 33 36 24 26 34 27 31 33 30 29 23 32 40 36 32 44 42 50 49 52 61 55 39 54 49 42 46 41 73 46 42 54 40 51 50 34 54 49 60 53 47 41 35 63 72 25 39 65 56 47 35 64 64 65 68 42 62 54 53 67 53 51 72 89 49 54 54 68 66 65 72 82 75 86 89 51 71 72 65 32 95 48 56 83 100 74 77 83 76 83 104 46 56 98 41 52 43 57 91 77 95 87 81 102 99 80 56 59 97 30 74 37 73 97 90 78 110 81 128 129 119 84 73 47 58 39 19 19 27 34 35 34 36 66 35 52 55 41 43 59 51 60 48 24 24 55 37 27 34 62 56 35 43 52 44 50 43 72 43 41 40 44 48 37 59 56 37 43 32 43 55 29 29 32 35 58 44 32 38 70 55 79 74 43 38 47 40 41 42 35 56 46 43 71 120 97 110 108 121 179 122 41 43 33 60 54 33 18 38 56 46 27 39 27 27 45 33 21 57 33 51 27 33 22 20 17 13 15 20 22 25 21 18 18 29 13 29 21 19 15 12 25 14 21 19 24 16 30 20 24 17 29 41 24 39 39 32 44 27 32 36 41 46 43 41 26 47 41 37 32 35 39 28 18 34 30 47 34 34 19 39 36 32 19 29 27 53 42 16 36 31 35 29 39 38 31 37 20 18 32 34 25 11 11 17 27 11 16 15 14 13 15 20 16 13 13 15 13 19 16 18 12 14 9 10 11 8 12 7 7 13 10 19 15 12 10 16 13 13 14 15 13 15 12 12 12 14 10 12 9 11 9 4 13 13 10 12 7 11 21 5 24 14 13 13 14 16 18 12 16 14 17 14 8 18 22 15 19 11 8 16 14 13 20 18 13 16 7 23 13 20 13 15 15 10 14 13 13 6 16 16 14 10 13 14 13 14 17 14 11 9 9 14 14 7 11 11 12 8 9 13 19 15 13 11 16 15 7 9 5 6 10 10 10 12 16 19 9 5 12 8 8 5 7 9 8 16 7 14 11 11 11 7 13 13 13 17 6 9 12 11 7 12 14 13 12 13 16 10 14 11 15 9 4 12 12 11 16 7 7 9 10 15 17 12 18 18 22 25 21 19 16 24 21 11 15 13 14 19 15 17 13 13 13 13 14 14 16 8 12 7 7 6 7 12 12 8 12 12 5 8 8 17 13 6 12 16 19 7 10 17 8 20 9 18 18 14 8 11 18 8 11 15 12 3 11 14 10 13 14 14 10 6 12 6 5 13 10 13 6 6 11 11 12 16 6 11 15 12 12 12 14 17 10 6 10 8 6 11 9 12 14 11 8 9 15 14 22 23 16 
];
B = [
0 0 0
 791367 522455 268912
 1063945 731746 332199
 584940 395002 189938
 2225526 1621953 603573
 805155 588828 216327
 526639 389406 137233
 640264 480484 159780
 400790 302597 98193
 310144 238630 71514
 257600 198349 59251
 498889 386106 112783
 497454 381200 116254
 363907 274204 89703
 2084226 1636466 447760
 666795 517751 149044
 776015 615169 160846
 522352 415641 106711
 768455 609765 158690
 784674 625735 158939
 535310 425785 109525
 1634439 1311162 323277
 910085 728201 181884
 914295 735152 179143
 568347 458270 110077
 906600 732506 174094
 863753 698654 165099
 1405230 1138540 266690
 608020 490840 117180
 963997 778562 185435
 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 = [
14 113 0 0
1 8 0 0
4 23 0 0
9 19 0 0
4 19 0 0
13 16 1 0
57 50 4 0
125 43 3 0
558 68 7 2
1629 85 37 8
3128 116 917 130
6359 183 1426 434
11530 328 1996 820
20506 577 3002 1535
41381 1163 4378 2753
113552 2398 6636 5018
554552 5161 10175 8695
3695459 10221 16378 15418
10254063 19537 29496 29144
6492315 30401 51393 51867
1117139 44565 78609 78987
168195 63761 106855 107774
144601 89508 134877 134729
166303 125153 161252 162070
193517 167168 190772 191391
224951 209597 224377 224754
260364 254843 260725 259950
297864 300543 298918 300559
338156 342162 338305 339637
377890 386541 379671 381310
417018 424716 419106 421266
454352 461859 455772 457162
488031 494354 488363 490938
517185 525864 518719 520633
544684 553108 545481 546572
567810 577346 570461 572457
591225 600786 594873 595094
612597 622084 617298 617363
638701 643626 638867 641467
660794 667527 662879 663658
685338 691739 688554 690659
715482 719764 716092 717590
746559 750531 747003 749643
780770 785436 781730 784326
820310 823550 820062 822946
863026 864498 861072 864170
902709 904799 903207 903167
939511 941969 939448 941346
971321 973340 971148 971698
992989 993395 992641 992877
999828 1002877 1001461 1004041
991269 993904 993479 992313
968908 974273 970468 973317
937706 940729 939184 939701
891581 892919 890409 894366
830456 836681 833705 834128
770616 774509 771226 773462
705468 707750 703582 707284
643378 645927 643739 647079
590020 590604 588778 591809
550241 552011 551199 551023
522222 523943 521857 522002
500345 500559 501624 502018
497041 498156 496135 497927
506802 507177 507705 508392
527973 527158 527093 528155
557886 557500 556289 558757
608880 611603 607372 608180
651358 652170 649296 653684
687401 689345 685765 690895
707606 707591 707352 708261
709264 711543 710546 711866
667516 669334 667293 669394
580294 581547 580228 581155
489107 488348 485821 488126
391549 391395 390244 392314
292310 290389 290340 292721
201807 201610 201639 201864
147979 147803 147853 147763
103546 103061 102833 102953
68202 68645 68348 68314
41662 41732 41625 41674
3610 3514 3571 3520
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
