A = [
674142 655715 13244831 507284 541957 479754 468447 476305 466839 469900 552197 673701 803567 956831 1196829 1413170 1450712 1460123 1413013 1310497 1267640 1236797 1197749 1206038 1260734 1887645 1982663 2143637 2750808 2334207 2311581 2249694 1961486 1989874 1960201 1948874 1883853 1812302 1783919 1741836 1768495 1830996 1822394 1849220 1891145 1847921 1818543 1783902 1723195 1702371 1692035 1662718 1658629 1653545 1622199 1605033 1584673 1537164 1515461 1497669 1462488 1453029 1451492 1421907 1411630 1400362 1367744 1348688 1325783 1291789 1279318 1267066 1239009 1229977 1224928 1195988 1185143 1171381 1139072 1122046 1109718 1084180 1072111 1063938 1040581 1029263 1017051 995008 979171 966669 943316 931723 920655 896212 888339 878514 860111 848613 836279 815053 801829 791663 771027 762499 752346 733291 725203 718400 701109 691625 681705 662440 654682 645796 627926 622417 612920 599161 591979 584369 570582 560520 555267 537811 532923 526528 511960 506840 499318 487968 482655 478352 465550 457094 451698 440533 434064 428180 418035 414162 407739 398830 391050 386437 378522 373154 367546 358733 354008 349290 342540 337972 331804 325789 319776 314990 307219 302443 299927 293793 289629 285442 280846 275584 271324 264175 262239 259868 253135 250426 246871 241117 238062 235044 229832 225591 222906 217515 213521 211358 206552 203910 201158 197070 194318 190811 187580 184790 182059 177724 175318 174240 169725 167056 165125 161801 159761 156879 153194 150962 149158 146535 144101 142492 139274 137020 136050 133027 130344 129303 125965 125051 122593 120632 118384 117226 114257 112647 111442 109341 107601 105577 104365 102369 101544 98885 97309 96108 93974 92641 91015 88906 88138 87538 85236 84400 83019 81289 79636 78678 77740 76225 75218 74083 73201 71969 70249 69316 67835 66906 65930 64872 63525 62832 62049 60542 59691 59090 57728 57039 56366 54895 54440 53125 52652 51795 50973 50275 49454 48613 47986 47059 46529 45908 44712 44494 43497 42830 42673 41853 41182 40287 39367 38737 38224 37952 37335 36306 35962 35486 34851 34418 33940 33367 32654 32469 31906 31674 30671 30222 29923 29061 29446 28531 28420 27805 27029 27023 26537 26050 25349 25137 24903 24498 24389 24086 23226 22835 22923 22235 21979 21764 21584 20791 21003 20472 19991 19680 19490 19427 18865 18801 18657 18179 17903 17820 17431 17167 16899 16777 16356 16352 16051 15521 15692 15302 15245 14790 14551 14613 14119 13794 13821 13686 13325 13365 13373 13056 12864 12768 12344 12399 11971 11999 11592 11579 11202 11190 11526 11116 10767 10564 10667 10530 10164 10539 10142 10069 10173 9689 9659 9487 9271 9285 9153 9193 8999 8816 8775 8721 8485 8474 8448 8294 8207 8240 7742 7983 7759 7632 7536 7502 7294 7362 7293 7272 7138 6942 6894 6840 6715 6647 6728 6522 6431 6482 6282 6343 6143 5983 5924 5950 6034 5932 5863 5780 5652 5459 5522 5650 5431 5418 5382 5364 5189 5149 5176 5148 5083 5058 4883 5097 4946 4637 4671 4655 4583 4620 4632 4527 4536 4585 4485 4597 4482 4376 4305 4267 4118 4207 4249 4133 4184 4173 4047 4013 3994 3901 3772 3838 3817 3860 3680 3757 3787 3748 3744 3670 3617 3637 3598 3656 3560 3553 3514 3600 3595 3366 3282 3326 3329 3310 3370 3376 3340 3244 3239 3237 3157 3243 3114 3123 3171 3097 3030 2989 2987 2975 2962 2991 3077 3035 2931 3031 2960 2817 2911 3021 2912 2943 2802 2783 2662 2719 2699 2796 2805 2721 2829 2727 2748 2774 2651 2711 2670 2607 2532 2426 2593 2530 2464 2509 2516 2515 2483 2509 2425 2445 2443 2423 2362 2369 2348 2357 2375 2300 2366 2307 2386 2303 2357 2316 2279 2199 2175 2272 2231 2229 2261 2229 2319 2250 2132 2174 2164 2174 2043 2097 2145 2122 2045 2028 2078 2050 2219 2004 2047 2087 2086 2066 2120 2002 2039 1980 2009 2065 1957 1945 1940 1950 1893 1925 1937 1972 1886 1855 1784 1862 1921 1871 1828 1875 1797 1938 1946 1878 1789 1830 1845 1900 1775 1806 1804 1826 1829 1761 1771 1786 1865 1850 1689 1756 1731 1693 1721 1656 1534 1665 1725 1668 1649 1722 1612 1692 1581 1538 1616 1676 1535 1573 1617 1628 1538 1495 1609 1529 1569 1534 1592 1453 1537 1615 1555 1403 1526 1477 1559 1549 1465 1462 1479 1511 1497 1432 1469 1468 1452 1575 1387 1501 1445 1421 1367 1420 1458 1368 1352 1445 1491 1429 1382 1425 1403 1397 1409 1343 1391 1329 1342 1418 1357 1400 1388 1261 1410 1272 1332 1438 1349 1261 1284 1248 1342 1300 1311 1166 1246 1273 1201 1297 1174 1263 1224 1214 1258 1227 1196 1283 1203 1131 1229 1135 1267 1173 1155 1111 1220 1135 1194 1214 1172 1184 1161 1227 1144 1121 1151 1252 1248 1126 1183 1104 1106 1172 1186 1068 1099 1165 1074 1163 1194 1163 1150 1140 1083 1089 1158 1152 1033 1223 1049 1118 1021 1017 1020 1024 995 1036 1005 1025 1017 1014 1051 992 1041 983 1035 1014 991 975 974 962 981 955 888 922 936 868 882 903 860 844 807 871 847 824 826 845 906 839 875 806 878 898 860 801 786 871 832 879 903 821 873 823 822 929 838 839 867 868 885 837 868 820 853 806 783 865 855 866 840 821 828 806 857 796 846 846 802 791 771 766 825 776 736 775 819 736 798 798 826 752 799 743 831 790 790 769 808 761 769 786 737 671 759 682 750 778 745 777 740 707 730 693 690 688 681 603 717 687 732 676 691 706 765 682 697 731 693 671 690 693 726 695 685 758 611 686 676 653 619 603 666 660 660 599 616 727 672 762 712 676 692 698 613 633 643 660 594 582 615 619 600 601 605 618 612 573 581 599 611 569 618 553 617 567 565 612 557 569 563 587 568 569 593 612 547 555 587 576 571 529 512 548 545 509 534 528 554 528 507 444 515 515 534 502 503 528 513 517 567 500 518 553 518 508 494 530 482 525 496 557 548 575 547 460 489 513 539 512 487 465 489 565 515 522 547 521 496 499 505 516 537 544 484 554 506 534 546 471 519 527 471 506 453 437 509 477 455 455 458 446 427 424 472 475 417 423 434 456 458 411 433 450 460 396 419 401 383 401 450 428 424 404 421 379 378 380 406 389 416 418 470 424 409 415 415 374 439 436 363 401 416 436 439 405 426 445 405 400 430 406 369 359 398 358 386 419 385 356 408 419 326 373 404 379 369 379 370 343 305 357 333 358 363 363 394 353 387 387 385 395 339 365 420 293 355 371 340 321 318 318 321 375 348 304 353 327 323 316 297 339 265 290 288 323 299 295 304 329 274 310 328 334 274 284 289 288 278 293 293 273 315 267 223 329 238 258 288 249 287 265 315 247 252 266 247 266 259 248 238 241 241 268 281 263 263 264 250 282 241 222 231 262 253 265 277 278 275 254 277 285 270 265 222 248 258 250 233 231 279 274 259 269 264 264 300 229 249 263 255 268 248 285 238 254 270 264 235 282 274 268 247 246 272 262 262 252 257 287 261 269 242 251 272 233 249 263 241 264 257 221 223 240 247 222 246 226 226 197 241 239 231 225 193 201 215 217 199 213 229 227 219 232 201 235 211 214 182 202 212 249 214 217 227 174 208 208 224 224 190 194 196 215 224 189 209 199 189 218 199 221 197 238 185 190 185 186 199 176 218 212 180 204 162 182 172 179 191 181 206 198 193 177 177 178 198 166 187 158 223 159 171 179 209 199 193 182 204 164 181 178 182 186 188 170 208 163 161 166 166 155 174 199 195 182 187 161 134 159 164 157 169 159 190 161 158 158 168 179 188 171 144 137 177 151 172 171 195 164 148 163 166 147 132 140 165 171 163 160 177 164 138 169 168 141 145 159 162 153 159 149 117 120 135 120 150 116 126 136 138 135 128 112 153 144 131 137 159 144 153 137 153 134 135 112 156 129 143 140 141 151 111 125 155 142 142 143 128 141 149 138 145 131 130 143 121 137 98 129 134 132 142 148 130 156 132 140 158 135 121 136 126 134 153 129 144 177 148 150 149 139 135 127 139 165 133 136 141 145 151 134 125 152 157 148 132 130 134 110 132 165 141 132 92 136 129 133 152 136 147 162 135 142 110 131 136 133 111 100 113 124 126 133 115 107 115 115 132 160 120 121 118 129 122 154 145 139 131 116 130 116 127 144 126 114 124 151 143 121 157 145 119 126 141 140 114 141 133 132 160 151 139 127 146 122 117 166 118 139 138 127 110 123 140 130 128 112 108 133 127 97 109 101 110 122 118 117 129 141 117 113 137 105 109 102 95 103 93 106 99 102 85 74 77 93 87 105 117 93 99 106 98 117 85 89 92 74 69 85 82 89 63 93 98 100 92 76 78 85 83 91 88 83 104 88 102 85 94 99 82 72 70 96 82 82 98 97 71 76 94 94 96 76 97 82 91 75 68 67 78 83 92 100 69 82 70 93 79 91 98 96 94 141 109 84 94 89 101 92 94 85 83 94 104 102 102 100 116 81 94 82 107 105 103 91 103 106 96 108 110 112 106 112 95 85 77 133 105 118 105 112 100 81 84 85 70 91 66 69 85 81 82 77 75 65 82 77 83 95 77 88 72 63 79 62 75 74 70 87 55 52 71 88 59 74 63 68 75 68 69 67 61 57 54 52 60 70 77 72 69 67 55 63 54 50 61 73 63 57 53 49 61 43 51 50 43 69 70 56 42 51 56 61 44 54 65 61 57 49 45 68 59 39 56 54 64 58 70 57 53 56 62 44 45 64 50 53 46 65 47 50 57 63 58 56 55 60 46 39 53 52 62 49 58 67 64 37 46 48 64 58 45 53 53 75 62 53 53 63 56 49 71 45 57 47 58 57 46 52 47 54 41 50 39 51 53 60 40 56 45 68 46 53 49 43 49 43 52 47 56 51 43 48 49 39 57 33 36 40 51 50 55 51 48 53 43 38 44 37 40 43 38 51 52 60 53 47 40 37 31 50 31 39 32 33 39 34 31 33 37 39 32 50 43 42 39 41 34 33 38 37 43 23 29 27 39 30 29 40 59 50 40 35 51 48 37 47 42 59 55 33 37 32 44 35 37 43 40 37 37 42 35 36 52 43 45 40 33 47 32 24 39 34 41 37 40 38 41 40 32 47 33 38 29 28 45 35 41 36 40 29 27 36 33 42 36 40 20 27 20 28 39 39 22 29 33 25 34 20 22 33 33 33 35 32 34 26 25 36 32 24 29 27 39 30 24 30 26 33 
];
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
 103733 75613 28120
 69495 49686 19809
 118881 85023 33858
 119129 89616 29513
 75201 58041 17160
 126367 89993 36374
 60844 47586 13258
 70660 54855 15805
 95833 68619 27214
 119992 92415 27577
 58952 46500 12452
 122007 89613 32394
 81786 65317 16469
 56558 43874 12684
 236315 167477 68838
 74901 58808 16093
 80952 64265 16687
 140944 105494 35450
 149505 112811 36694
 145994 114570 31424
 110256 85937 24319
 83608 68685 14923
 163600 129795 33805
 88631 68968 19663
 276477 223276 53201
 133376 103246 30130
 99958 79632 20326
 111048 92166 18882
 190682 143197 47485
 307403 257096 50307
 99256269 85589768 13666501
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
68 558 177 213
18 117 18 78
15 147 44 145
34 227 60 267
54 215 106 392
87 226 349 778
8564 331 1058 2107
95780 394 2041 2991
848845 496 4043 4059
2130001 657 5358 5340
2715433 838 5942 5852
3164618 1144 7017 6939
3788292 1874 8110 7901
4359686 3002 10501 10174
3867424 4769 13827 13310
3168846 7733 19216 18942
2223844 11440 26476 25997
1321025 16520 34014 34749
636981 24027 44650 44688
250879 34151 56071 55956
112732 47150 67256 68372
87054 63290 80994 81248
100458 81218 97487 97910
119295 102131 114564 115045
139997 125714 136056 135990
164603 152244 159715 159384
191122 181486 187324 186906
221890 212750 217088 217214
254702 245653 249485 251190
289107 280243 284695 284783
326095 316859 319105 320276
357847 348874 352273 352825
390495 379338 383343 383597
417310 408564 411760 411792
437779 431540 433625 434859
453837 449909 451159 452585
463830 461690 461753 463787
469390 468974 467607 471395
470878 468253 469559 470574
466438 466396 466848 468493
461089 460508 461323 461934
450904 453134 452075 452468
440060 442392 441489 441298
426032 428067 426180 428006
408339 410796 408221 410731
389217 392416 390315 390811
366903 367476 365621 367543
343131 343241 342588 342865
318745 317781 317788 318048
293396 294871 293794 295455
272108 271486 272217 272762
256243 256123 255552 255120
243364 242526 242467 244107
232582 232894 232961 232711
225302 225720 225441 225764
222240 222159 221251 221881
223602 224051 222990 223723
228901 228650 228869 229266
240250 239937 240701 241098
258871 258137 257742 259379
279129 277091 278533 278561
278430 278127 277183 277610
290826 290730 289485 291765
312540 311524 310524 312023
310337 310303 310226 310352
304219 303448 302179 303950
276554 276993 275485 277243
241026 241264 240074 241767
196652 196490 197476 196593
136275 135685 135292 135801
57995 57445 57542 57848
9252 9258 9096 9169
0 1 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
