A = [
967429 1263738 1503465 848850 1722477 1105408 1033927 1547704 1442089 1581607 957134 1211650 1486766 1104426 1200450 1021743 1167767 1153915 1154876 1106203 1025894 1216908 1114389 1083477 1121501 1034379 1040185 1104085 1127707 1080965 1104232 1111324 1111721 982989 946519 1089165 1159800 1010207 1107730 1163026 1024626 967957 926501 1058773 936601 964100 999133 950510 973735 909340 884629 961794 918902 936879 903707 870463 922558 834491 848038 819290 821861 857561 800185 829597 809492 779541 817212 778586 805509 765756 796133 805325 740960 757601 734717 764415 826175 784907 803233 813269 768044 757754 732840 737545 710115 716240 716123 672537 660439 655193 652462 653329 640518 637209 634135 626477 618679 609757 601979 591708 590032 587856 587066 584271 574060 574374 563969 555527 550683 543820 541535 534326 531178 526834 518968 520231 515683 513850 512247 506655 503333 497189 492452 487565 482741 480744 475623 467945 468993 462568 459554 453776 450629 449519 443027 440720 435403 432305 428681 423451 421126 418962 410931 410892 405928 403920 399018 395491 393123 390666 384030 382488 375490 370782 369793 366339 366341 360837 357161 354727 349452 346622 348998 343755 341826 340113 334188 331665 325941 324161 321718 320225 318426 319243 313223 311238 309904 304808 304068 299185 297570 294959 290837 287357 285433 283154 281600 278050 277682 273050 268654 268810 264860 265352 259783 256512 257124 250070 246830 243687 240907 239409 236010 236015 232977 230767 229090 223719 221595 218991 218973 218384 214157 212487 212675 207437 203799 201339 199658 196475 194460 192015 190858 189414 185391 184566 182723 180222 179790 177859 175752 174125 172764 171314 168511 166872 165779 163029 162688 160918 159818 158435 156532 154395 153428 152727 150593 149483 147432 146339 145649 145239 143142 141487 140627 139607 138530 136041 135862 134575 132733 131919 131032 129929 129043 127635 126613 125077 124486 122026 122516 120796 120389 118831 117660 116134 115986 115030 113870 112237 111783 110333 109736 108725 108086 107059 106273 104495 103929 103037 101915 101188 100780 99262 97952 97246 96743 96169 95337 93510 93394 93205 91870 90836 90477 90102 88548 87931 87179 86118 85339 84873 84908 84120 82751 82077 81336 80508 80175 79608 79301 77887 76968 76890 75932 76146 74729 74590 73297 73010 72181 71569 71272 70250 69677 69406 69106 67958 67702 67015 66848 65655 66244 64632 64971 63541 63540 63310 62584 61846 61951 60820 60884 60198 60585 59172 59328 58381 58225 57617 56845 56373 56205 55790 56108 54990 54594 54686 53843 53542 52959 53186 52717 52132 51651 51247 50838 50515 49895 49719 49261 49191 49040 48692 47916 47278 47054 46465 46032 46312 45970 45517 44700 44394 44642 44629 43900 43564 43384 43317 42933 42916 42160 41517 41623 41072 41346 40305 40640 40351 40299 39247 39639 39466 39155 38626 38237 38352 37888 37265 37392 37432 37040 36752 36475 36862 35612 35779 35134 35400 35200 35331 34714 34133 34382 33940 34209 34065 33185 33463 33067 32771 32813 32581 32156 31913 31210 32001 31087 31309 30772 30758 30406 30187 30445 30141 29839 29989 29480 29476 29124 28387 28746 28806 28686 28188 27947 28060 27838 27530 27827 27118 26989 26939 27229 26959 26342 26679 26485 25985 26452 25844 26072 25452 25826 25470 25951 24956 24907 25397 24910 24890 24502 24217 24496 23999 23741 24227 23862 23431 23610 23447 23359 23398 23043 22937 23532 22901 22729 22710 22499 22830 22047 22358 22149 21737 22110 21945 21783 21570 21528 21277 20949 21389 21006 20568 20709 20767 20515 20585 20133 20056 20119 19991 19900 19981 19968 19759 19335 19511 19334 19328 18853 18977 18863 18788 18609 18702 18621 18399 18275 17938 18322 18051 18091 18071 17760 18030 17807 17703 17221 17314 17326 17499 17292 17462 17038 16922 17184 16787 16613 16725 16334 16513 16548 16235 16425 16328 16181 16187 15925 15739 15859 15672 16079 15505 15188 15578 15193 15521 15423 15019 15002 15059 14963 14902 14870 14673 14772 14325 14435 14389 14454 14239 14415 14263 14013 13922 13843 14442 13981 13596 13332 13841 13378 13379 13538 13474 13167 13391 13001 13266 13106 13026 12958 12803 12747 12649 12828 12570 12520 12297 12348 12593 12335 12355 12119 12259 12112 12089 11750 11777 11674 11869 11698 11857 11519 11332 11661 11332 11502 11254 11042 11483 11125 11243 10971 10925 10837 10756 10916 10570 10618 10631 10639 10428 10274 10435 10385 10413 10434 10268 10172 10060 10014 10127 10070 9871 9956 9898 9791 9840 9884 9789 9609 9763 9650 9705 9572 9439 9617 9262 9027 9206 9143 9218 9406 8802 9094 8951 8918 9051 8677 8797 9040 8616 8955 8906 8572 8551 8378 8510 8483 8634 8508 8496 8130 8164 8235 8411 8055 7979 8187 8115 7968 7866 8045 8065 7839 7898 7632 7504 7609 7605 7715 7656 7696 7480 7607 7429 7309 7285 7405 7159 7205 7307 7250 7158 7145 7064 7022 6974 7016 6934 7116 6780 6923 6765 6753 6951 6657 6666 6681 6589 6685 6655 6487 6726 6468 6436 6330 6406 6379 6238 6368 6168 6106 6257 6122 6208 6011 6067 6224 6079 6055 5968 5895 5863 5994 5981 5939 5703 5697 5667 5863 5671 5640 5703 5645 5627 5680 5529 5667 5608 5477 5473 5164 5528 5485 5455 5252 5232 5191 5267 5151 5189 5198 5221 5245 5185 4973 4769 5179 5053 5077 4878 4978 4994 4942 5033 4754 4836 4751 4710 4855 4904 4718 4643 4827 4669 4500 4519 4582 4667 4613 4554 4494 4429 4470 4534 4380 4528 4327 4403 4285 4358 4313 4280 4146 4151 4243 4207 4209 4066 4177 4228 4220 4154 4104 4068 4043 4018 4002 4110 4006 3866 3835 3977 3747 3995 3862 3892 3756 3791 3703 3819 3693 3657 3678 3784 3736 3727 3579 3582 3569 3659 3577 3528 3579 3634 3455 3489 3431 3545 3480 3440 3419 3457 3427 3294 3446 3340 3335 3196 3312 3265 3146 3364 3190 3177 3119 3080 3133 3157 3026 3139 3033 3212 3022 3031 3055 2929 2956 2948 2993 3138 2971 2903 2963 2884 2972 2891 2887 2933 2829 2922 2799 2720 2622 2767 2866 2690 2779 2781 2782 2728 2637 2553 2694 2598 2691 2648 2620 2618 2670 2647 2540 2510 2536 2466 2471 2447 2580 2499 2497 2299 2464 2373 2422 2361 2345 2309 2394 2372 2472 2430 2261 2465 2354 2436 2192 2310 2350 2176 2213 2179 2284 2123 2166 2165 2209 2135 2222 2127 2174 2181 2025 2083 2033 2107 2150 2084 1959 2084 1987 2026 1903 2050 2023 2048 1967 1964 1982 2000 1947 2078 1922 1882 1869 1925 1900 1957 1882 1876 1856 1896 1779 1786 1843 1832 1757 1780 1846 1865 1716 1675 1746 1757 1725 1786 1721 1731 1719 1933 1676 1747 1727 1817 1838 1739 1669 1758 1729 1808 1783 1833 1814 1837 1679 1599 1623 1588 1680 1659 1731 1731 1648 1644 1694 1653 1599 1564 1586 1559 1578 1534 1522 1549 1471 1505 1530 1497 1479 1447 1479 1521 1453 1446 1440 1437 1460 1434 1419 1372 1322 1424 1334 1330 1389 1346 1340 1327 1262 1382 1732 1309 1332 1263 1367 1317 1263 1231 1305 1295 1251 1289 1265 1199 1190 1246 1239 1270 1174 1130 1237 1155 1103 1143 1155 1129 1088 1205 1147 1137 1098 1197 1143 1151 1104 1135 1200 1150 1081 1104 1199 1207 1341 1055 1073 1083 1050 1023 1111 998 1082 1039 1008 1045 1031 988 976 1083 1011 963 1039 968 1050 932 1009 1024 971 962 924 942 4335 946 959 908 886 924 966 910 955 891 922 872 1000 876 882 866 873 869 865 890 861 859 834 872 874 838 801 858 857 794 830 727 765 840 887 738 794 764 762 811 807 730 773 785 762 774 797 728 760 781 793 753 779 782 766 718 762 784 787 759 702 693 671 706 729 730 734 716 692 663 747 689 667 663 679 676 665 710 661 653 603 642 658 661 685 650 637 675 660 622 625 569 616 650 668 584 650 652 566 593 609 622 638 611 626 601 627 583 626 607 586 558 542 629 558 567 604 563 581 579 530 508 587 582 521 582 483 548 541 534 535 519 528 527 538 584 513 519 489 522 508 552 536 540 495 510 488 512 453 500 453 484 440 486 494 507 428 511 463 462 529 443 416 430 460 449 441 427 453 437 418 449 415 394 431 455 448 471 434 420 410 410 422 418 430 406 424 404 408 403 414 397 397 433 349 430 399 403 438 363 405 386 369 364 374 396 376 345 378 370 377 390 353 386 384 354 330 364 343 381 357 373 361 369 352 339 326 337 321 333 302 343 332 335 349 365 376 304 308 354 346 316 292 307 305 318 300 312 323 321 307 304 307 298 264 275 327 290 315 301 296 289 316 279 284 287 325 287 293 277 249 274 302 297 272 240 256 279 300 252 263 275 242 299 239 300 275 250 236 229 243 246 289 248 243 221 256 206 246 261 267 274 269 230 246 254 226 251 249 232 290 213 237 215 217 249 269 232 235 221 221 205 217 216 251 224 234 202 196 191 233 262 206 248 219 236 229 197 243 208 216 194 174 208 233 192 203 188 200 202 218 179 218 159 223 190 205 204 212 189 195 182 215 191 152 200 203 193 165 176 184 151 178 187 169 160 168 192 143 203 150 157 191 161 148 163 148 156 162 145 165 145 178 180 179 172 159 151 162 131 173 165 159 156 180 153 170 154 158 152 165 129 143 170 147 163 152 154 142 138 140 150 157 149 154 170 131 125 161 135 151 145 130 126 166 150 117 134 125 126 145 129 133 148 141 123 136 126 134 121 142 128 142 118 126 120 135 131 120 129 126 138 121 102 163 119 99 119 115 114 129 121 107 104 133 118 120 127 133 103 111 100 103 106 119 109 103 107 105 83 75 129 106 111 116 102 116 77 100 94 85 96 88 86 103 93 87 109 85 97 90 90 96 76 85 96 89 94 93 92 95 75 88 89 70 94 75 95 99 78 85 68 67 89 81 78 68 90 76 97 71 59 72 69 69 72 75 90 81 95 82 71 52 68 96 57 86 76 64 60 56 67 79 59 71 72 83 59 71 74 63 56 72 62 90 66 80 76 59 79 60 65 66 65 76 52 57 59 58 64 63 82 66 65 62 68 79 64 55 53 68 61 73 47 57 36 66 64 57 58 62 58 61 50 59 67 41 51 51 57 56 54 54 56 41 60 50 56 41 60 65 50 40 52 47 42 50 46 42 49 49 43 52 52 55 52 39 48 63 35 52 43 49 49 43 51 47 43 54 32 48 37 54 42 51 39 47 35 51 47 44 32 40 45 49 42 42 40 37 41 59 50 54 43 57 46 38 37 55 26 54 36 38 46 33 39 40 31 64 39 33 41 43 42 36 39 48 35 42 33 40 45 52 28 46 38 43 36 52 28 35 35 44 35 35 32 39 30 32 30 34 49 27 32 31 30 34 30 27 27 38 29 34 36 30 37 38 36 23 27 28 21 24 39 32 23 40 20 35 33 38 22 27 40 26 28 35 32 29 30 33 22 32 26 28 26 39 23 30 36 24 20 36 17 27 23 38 23 23 37 17 41 28 21 42 15 23 26 17 22 25 20 28 24 27 26 31 22 28 25 25 27 27 20 21 30 
];
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
 317212 296008 21204
 322419 301326 21093
 321621 301053 20568
 305701 286268 19433
 392633 368900 23733
 332078 312466 19612
 327156 307234 19922
 731649 686576 45073
 335766 317066 18700
 387430 365250 22180
 649318 610708 38610
 400404 379194 21210
 587561 553762 33799
 350162 332506 17656
 402769 381523 21246
 610771 576225 34546
 406489 385913 20576
 599702 567095 32607
 406470 386385 20085
 582479 551603 30876
 414117 394107 20010
 568386 538068 30318
 420698 400291 20407
 581239 551643 29596
 420883 401497 19386
 602587 571065 31522
 572564 545249 27315
 409837 391551 18286
 543836 516269 27567
 350012 335236 14776
 68790261 67201688 1588573
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
43 5 2 2
0 24 0 0
1 47 0 1
1 42 0 1
2 56 1 0
1 174 3 4
20 213 28 23
251 327 63 67
50431 542 106 126
503804 865 206 222
1242206 1315 346 333
2295916 1893 722 684
3333266 2915 1566 1553
4482630 4050 4372 4472
5990774 6297 9990 10221
9371600 19231 21154 21462
10067993 29342 43164 43397
8669990 45853 62543 62888
6546066 73221 77227 77507
1873987 102698 101969 103435
181976 132937 122042 123371
175139 151283 143836 144228
170126 184436 161257 161277
177424 201027 176957 177029
176851 219440 184820 185016
176742 226229 186457 187385
170609 222503 183173 183093
164260 211328 174097 175326
152808 193534 161243 162779
140949 170789 147144 148080
128893 147094 132562 132485
118608 127221 119450 119160
109257 113965 109235 109341
105250 105293 103992 104224
103483 101550 101469 102491
103742 101726 101735 102063
106195 103761 103821 104642
111284 107126 108817 109627
117773 114354 115327 115848
124588 122067 123605 123811
134711 130650 131546 132373
144998 141119 142117 142917
155635 152858 154318 154156
166366 162847 164478 164302
175165 172393 172948 174017
183399 180284 181707 181881
186742 185376 185913 186282
188825 187717 188254 187907
187193 185742 185776 186412
181989 181208 180812 182084
172705 172646 172688 173147
160396 159605 160280 160704
144619 145088 145145 145598
129885 129663 129500 130010
111942 112428 112361 113409
96927 96156 95957 96271
81948 81795 81796 81344
68277 67993 68359 67837
57424 57265 57329 57718
48755 49104 49038 49082
42573 42398 42828 42829
38340 38251 38066 38323
35112 35063 35004 34930
33003 32555 32273 32473
31004 30870 30898 31209
30582 30357 30523 30705
30398 30519 30239 30420
30711 30404 30663 30853
31385 31342 31278 31399
32603 32330 32538 32443
33459 33123 33162 33216
34339 34305 34596 34326
33782 33953 33808 34250
31500 31572 30840 31256
27175 27468 27257 27170
23019 22790 22593 22789
17762 17695 17818 17379
12402 12510 12624 12450
10001 9895 9798 9988
6659 6702 6823 6705
4101 4056 4177 3946
1732 1733 1797 1742
65 85 82 58
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
