A = [
1410184 1401734 5334103 1387871 1412882 1304916 1290758 1300572 1286660 1255612 1250404 1258902 1265923 1261594 1274941 1276024 1281093 1295737 1288085 1282041 1285296 1274636 1271537 1279917 1330879 2096836 2115969 2157712 2929142 2861337 2958473 2977941 2899524 2947255 2999882 2982874 2905706 2919361 2896245 2857938 2834690 2821062 2802415 2786388 2779460 2744553 2715427 2691433 2656583 2625649 2595234 2575471 2557029 2533491 2512619 2499379 2461599 2434835 2407328 2375936 2346208 2320868 2294564 2276141 2249693 2224249 2200366 2175537 2156151 2124526 2097446 2071414 2046211 2021269 1999368 1976868 1954850 1927134 1905264 1884330 1859303 1833488 1813483 1788726 1762344 1739674 1718793 1697118 1675639 1652357 1630935 1607522 1585318 1566845 1551940 1528510 1506691 1482982 1466067 1445087 1426557 1406394 1388320 1370834 1351400 1333930 1321405 1302388 1280053 1265589 1245251 1226606 1207471 1190706 1170564 1156126 1142680 1124356 1115422 1094400 1074531 1058228 1041609 1024896 1004202 988220 975250 963701 945104 935298 925117 912781 895410 884172 868801 851665 879059 829172 816608 803126 789827 776075 767577 756444 744863 734769 724087 708700 695835 686482 677511 664109 653040 645597 631273 622130 614780 602586 591744 581461 574192 563189 552518 544268 535172 525288 517318 507391 498104 488780 481384 473480 467081 458612 452700 443649 435517 428828 420898 414282 408791 399821 393757 387100 383012 375866 368984 362893 356568 350366 344929 338039 333053 329413 322165 316558 312083 307496 301702 294873 290615 286742 279906 275743 271208 266472 262168 257582 253519 249215 244058 238937 234861 229724 226755 223460 219031 215540 210883 208839 204839 200835 198139 194950 190425 187080 184605 182204 179306 174866 172501 169098 165728 162602 159703 156764 152979 151020 146953 144865 143039 141130 139331 137324 135566 133231 131332 128936 126178 124971 121549 119476 117447 116226 114473 111003 109309 108491 105255 103713 102731 99860 99129 98262 94883 93609 91169 89546 88128 87319 86164 84644 83561 82941 81683 79776 78071 75992 75256 75439 75075 72411 72221 70234 69311 68678 66607 65912 66081 64127 62716 61627 61130 60821 59207 58413 57019 55815 55836 56563 55099 53928 53168 52510 52841 49943 49566 51908 49089 47928 46819 46555 45285 45193 44588 44132 43931 42005 40693 39435 42616 37283 37046 35622 34803 36979 35437 33962 31742 31498 30864 30298 29728 29272 28868 28437 28225 27835 27921 27415 28561 28277 27975 27847 27077 27087 26191 25401 25268 24535 24396 25088 24966 23835 23626 23557 24890 22540 23933 22289 22659 22174 21782 21484 20099 20962 20502 20159 19447 19160 19487 18572 18242 18622 18454 18139 18414 17853 17288 17123 16576 16329 16046 15861 19109 17901 17460 17448 17030 17478 17870 17503 18927 16853 17357 16272 12914 12916 12877 12793 12707 12811 12160 12476 12090 12911 11667 11881 11746 11914 11483 11495 11129 11428 11513 10903 11060 10893 10460 10362 10869 10052 9956 9817 9854 9789 9635 9570 9829 9848 9262 8987 9226 9130 8757 8907 8698 8515 8347 8505 7816 7948 7794 7561 7591 7492 7685 7396 7225 7162 7259 7195 7032 6938 6785 6918 6725 6784 6563 6519 6590 6394 6222 6325 6437 6116 6144 6025 6043 6106 6184 5887 6052 5855 5826 5740 5695 5644 5549 5508 5467 5571 5524 5445 5402 5451 5285 5290 5317 5487 5477 5217 5345 5259 5433 5412 5327 5294 4994 5202 5059 5140 4966 5328 5165 5158 5028 4934 4838 4930 4802 4780 4716 4833 4828 4732 4689 4545 4454 4458 4527 4564 4333 4303 4623 4408 4354 4500 4456 4422 4458 4291 4293 4354 4374 4267 4041 4265 4168 4266 3926 3824 4017 4330 4322 4163 4013 4371 4222 4259 4131 4198 4067 4362 4119 4006 4055 4210 4288 4010 3649 3721 3781 3993 3679 3629 3674 3836 3828 3728 3813 3875 3637 3731 3828 3414 3519 3283 3420 3381 3533 3404 3208 3250 3124 3203 3104 3101 3237 3177 3304 3152 3304 3351 3197 2980 3206 2949 3049 3017 2979 2972 2810 2940 2990 2916 2846 2982 2780 2815 2912 2787 2934 2906 2740 2846 2845 2741 2747 2779 2719 2748 2703 2565 2578 2783 2659 2763 2539 2496 2642 2745 2730 2471 2507 2528 2638 2618 2376 2428 2457 2250 2461 2291 2307 2294 2119 2277 2298 2124 2084 2075 1986 2183 2152 2162 2226 2049 2037 2149 2026 1986 1942 1925 2062 2173 2160 2169 2095 2385 1854 1915 1893 1866 1792 1803 1798 1751 1690 1756 1652 1714 1718 1710 1833 1661 1707 1670 1710 1753 1710 1722 1708 1787 1761 1869 1906 1904 1977 1894 1790 1901 1809 1816 2105 1883 1825 1740 1762 1851 1920 1919 1833 1872 1824 1731 1765 1941 1951 1956 1808 1747 1863 2063 2064 1966 1878 1745 2107 1969 2057 2194 1902 2605 2214 2485 3616 2838 2246 2445 2111 2156 2111 2346 1857 1774 2640 2165 2371 2088 2270 2115 2287 2135 2176 2415 1584 1936 1719 1786 1471 1434 1429 1541 1370 1388 1478 1397 1407 1354 1601 1493 1453 1453 1442 1334 1298 1194 1215 1274 1194 1168 1223 1218 1189 1214 1226 1267 1245 1177 1207 1227 1243 1290 1386 1296 1252 1318 1284 1217 1292 1164 1129 1111 1120 1130 1058 1158 1120 1010 1020 1114 1099 1120 1050 1061 1124 1148 1112 1032 1195 1081 1005 941 978 1020 1148 1094 1046 1156 1070 1056 1119 1040 1133 1020 1200 1270 1389 1273 1272 1327 1274 1351 1288 1434 1287 1291 1257 1310 1273 1353 1469 1174 1202 1291 1187 1039 986 929 1022 907 965 953 958 990 887 924 942 1224 1005 913 949 1008 1011 974 1173 1041 1341 1278 1192 1147 1159 1218 1142 1081 992 962 937 920 786 858 879 799 706 743 1062 710 874 802 733 829 797 782 760 757 881 830 729 752 717 735 713 702 735 711 728 729 788 854 653 663 682 628 620 610 715 633 619 614 703 573 642 604 648 538 533 505 563 512 462 504 503 505 577 473 502 474 526 464 469 475 500 487 457 434 481 484 465 457 557 461 536 513 549 507 534 502 480 454 451 461 430 444 391 410 409 389 425 414 428 413 362 386 366 397 406 441 373 413 431 366 411 406 370 410 478 429 465 482 497 508 482 362 389 317 336 384 370 369 354 382 390 386 395 362 354 365 355 354 394 362 439 353 367 339 416 292 513 436 434 572 494 418 500 454 414 405 392 432 489 440 558 370 444 403 431 463 486 485 346 345 357 333 332 363 472 492 502 561 425 449 499 419 358 345 410 347 368 348 376 376 396 322 339 331 298 335 308 333 349 316 291 251 324 302 299 279 299 299 307 322 301 334 326 309 295 302 311 291 278 283 329 306 284 294 334 294 306 247 288 242 263 248 271 275 280 273 267 310 264 248 251 255 265 266 256 297 249 252 278 271 259 273 258 284 278 226 272 233 220 217 281 257 259 217 210 212 229 222 212 188 294 291 282 272 296 307 318 325 294 297 316 321 366 408 369 329 311 371 380 320 320 321 319 348 351 297 422 304 336 392 325 327 297 359 504 453 494 569 282 304 324 330 298 318 274 314 318 308 264 269 313 185 216 196 170 178 203 144 194 183 199 175 151 188 168 206 195 188 173 187 181 153 209 161 171 176 141 148 168 165 164 163 163 147 174 149 133 143 167 138 124 151 145 148 147 135 149 128 142 139 130 157 114 123 150 154 122 131 142 142 144 140 145 145 113 136 128 129 140 152 147 132 135 129 138 137 132 134 124 137 129 137 145 129 131 131 138 226 221 201 252 256 198 231 246 207 196 214 175 256 211 194 233 206 198 213 224 218 210 203 234 199 175 201 155 153 186 189 192 186 182 123 89 105 120 113 130 117 90 89 82 109 106 96 87 87 96 128 97 114 108 117 105 82 105 103 83 120 98 88 93 103 108 109 119 109 96 113 109 93 90 101 96 104 89 97 86 78 86 70 67 88 97 85 85 82 94 84 78 62 80 86 68 81 64 48 77 89 90 86 121 94 92 107 83 66 90 59 70 76 81 67 78 121 139 134 118 131 172 132 148 130 123 155 143 121 105 102 98 123 69 79 74 72 95 63 69 88 89 82 68 75 76 85 90 69 73 97 102 87 79 103 98 86 79 96 79 66 74 61 66 66 65 67 59 67 87 59 71 72 87 79 71 66 67 78 83 61 77 81 70 67 61 68 73 85 68 75 70 53 54 73 52 52 52 72 56 56 56 56 62 47 57 62 68 56 74 55 63 64 72 58 71 85 65 58 69 85 80 73 63 92 86 80 74 77 67 79 80 80 71 78 92 57 59 131 127 118 129 133 107 117 78 62 49 56 59 67 60 56 54 47 62 56 70 69 61 52 51 67 71 54 51 66 55 63 52 55 56 51 54 62 62 49 59 41 50 44 57 66 74 71 57 71 62 62 63 65 59 72 46 62 52 49 52 54 40 43 47 61 76 77 72 63 72 68 60 77 60 77 67 81 87 75 90 79 77 69 77 82 76 71 72 79 76 50 56 70 63 67 61 63 57 44 56 50 60 70 61 54 65 91 82 83 62 65 100 89 75 102 114 103 61 70 78 73 84 89 80 105 110 103 133 100 99 92 96 96 127 125 114 95 177 103 123 108 110 109 131 137 98 109 107 92 690 510 743 1187 1105 740 743 565 819 414 40 52 35 44 118 135 114 117 117 128 109 99 154 143 113 53 61 58 47 45 39 44 66 69 56 64 59 68 101 72 71 60 73 63 62 54 55 61 76 57 51 55 51 54 47 76 56 53 69 48 40 49 62 49 58 52 52 42 51 47 51 39 43 65 69 59 36 53 50 37 37 46 54 55 52 47 42 30 44 35 33 39 32 48 41 33 31 31 42 24 25 43 51 34 41 26 40 32 38 37 30 31 38 33 28 36 45 43 32 38 25 36 33 34 49 36 29 34 28 35 34 29 45 47 34 34 27 44 40 41 31 41 33 34 22 35 31 29 35 30 41 21 34 30 37 35 37 36 37 28 41 28 32 23 53 27 35 41 30 44 40 44 33 60 31 43 38 44 30 39 44 35 46 51 36 62 44 35 37 41 48 58 41 30 46 40 46 41 46 42 32 44 54 35 31 38 17 47 36 37 31 35 36 43 32 32 33 23 38 47 32 46 49 40 40 49 43 37 40 38 34 29 49 32 47 33 32 33 41 29 38 47 34 37 40 46 33 52 48 39 30 44 42 32 41 36 28 49 30 36 28 34 24 25 30 20 26 21 43 21 23 26 30 32 23 38 33 18 16 28 15 25 17 32 30 31 38 34 25 43 36 44 33 35 34 34 38 36 36 48 26 28 24 30 24 31 16 29 24 33 30 19 31 23 32 36 31 35 22 24 25 31 38 28 
];
B = [
0 0 0
 571698 110241 461457
 311774 60726 251048
 978572 214410 764162
 304317 62475 241842
 325289 66603 258686
 445596 88972 356624
 499733 114319 385414
 386921 78698 308223
 961351 221737 739614
 355889 84390 271499
 401019 94879 306140
 486979 131268 355711
 642213 153632 488581
 308558 77525 231033
 933203 237206 695997
 334793 76864 257929
 352666 89055 263611
 370150 97426 272724
 748417 182564 565853
 399807 95676 304131
 1111060 295103 815957
 678260 161685 516575
 594580 141810 452770
 1268109 280199 987910
 1720726 417657 1303069
 282419 74347 208072
 4980791 1284793 3695998
 155498 57196 98302
 329969 108617 221352
 216966 79051 137915
 343762 121736 222026
 147286 50219 97067
 1088281 366999 721282
 122261 47512 74749
 272887 96498 176389
 177438 66144 111294
 301817 111763 190054
 72618 27154 45464
 1303195 456419 846776
 30685 14001 16684
 57481 24753 32728
 73109 29596 43513
 291150 103663 187487
 114057 46285 67772
 57368 24239 33129
 81796 31067 50729
 149835 58040 91795
 2266713 834515 1432198
 57632 28333 29299
 71577 30905 40672
 63892 28569 35323
 95198 41141 54057
 175880 68817 107063
 2481345 950490 1530855
 101896 43588 58308
 76167 32771 43396
 100100 46060 54040
 1182890 459354 723536
 1066906 438466 628440
 117706970 52630482 65076488
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
115 222 10 2
62 32 3 0
59 51 0 5
27 77 5 3
18 96 6 6
41 108 86 9
1450 184 232 47
9337 208 351 112
41965 324 593 284
129014 462 930 564
689693 628 1327 943
1043780 1229 1940 1532
1386249 2322 2875 2344
1769946 4669 4087 3809
1931674 8449 5653 5337
1890968 15005 7826 7737
1509526 22325 10403 10099
957131 30486 12818 12516
451762 38182 15119 14956
140694 44229 17647 17679
41797 47847 19892 20316
31527 48877 22352 22792
32122 45573 25758 24916
32973 40279 28522 28104
34185 36647 31167 31109
36805 35539 33749 33738
39573 36599 36572 37064
42286 39413 40326 40202
46320 43389 44635 44570
49820 47810 49050 49107
54737 52754 53783 53870
59876 57724 58958 58686
66199 64408 64799 65000
72937 71925 72431 72291
81519 80446 79735 80529
90623 89902 90232 89735
102088 100999 100617 100909
114247 114662 113685 114482
128302 128447 127921 128237
144275 144058 143919 143506
163046 163019 162959 161997
183366 183777 184290 183344
206500 206425 206461 206015
231735 231970 231776 232696
261540 261552 262010 261031
292700 293016 293324 293019
326667 326881 327344 326688
362014 361757 363019 362338
397904 399135 398363 398700
432605 433692 434187 433483
462939 463077 463727 463365
489515 489655 489671 488447
511389 511028 511757 510843
532418 530879 532847 531183
549969 550670 551279 551361
572139 570359 570183 570844
595326 595212 593759 593537
617075 618665 619616 615871
640000 640113 642420 639716
654543 653876 654698 652189
657330 656893 656568 655841
631337 630823 631823 630115
568821 569264 569103 568276
456693 455038 455654 456488
302956 303687 304489 304543
144993 144575 145027 145190
39538 39578 39728 39520
4213 4210 4254 4161
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
