A = [
963558 891035 6201967 713532 664980 671300 641346 785491 888301 928697 982798 1259828 1437396 1374121 1674551 1790520 1636507 1746645 1834104 1819273 1747581 1196685 1065140 970185 763138 1580897 1599119 1735428 2623513 2632178 2689892 2735830 2766095 2820356 2832509 2807802 2726696 2699629 2665664 2603407 2611999 2605111 2573531 2589160 2563661 2501420 2477127 2428156 2351855 2334997 2311864 2264191 2261614 2250894 2214421 2202104 2160756 2113223 2079622 2050289 2002789 1990517 1971833 1940617 1926381 1908494 1863765 1843041 1811057 1762265 1747380 1721691 1690377 1681412 1663981 1635737 1620944 1597463 1554967 1535848 1514777 1480802 1468300 1453351 1422422 1410525 1394545 1361548 1346341 1324824 1293959 1279881 1263320 1235295 1226230 1211875 1185977 1172892 1157710 1130359 1119062 1099631 1074154 1064710 1048309 1031068 1021493 1004823 985857 971758 955571 934568 927163 909598 891056 881114 868842 851621 840339 829157 810266 798012 786484 770026 763099 753100 737604 725003 714481 699453 690423 680487 666859 655468 646058 636166 627372 618040 604751 595065 584025 574726 565763 558656 546407 538243 530964 519826 513780 504234 495822 487199 479820 470400 463895 456497 447098 441650 435787 424246 422226 411950 404449 398774 391869 383696 379231 373976 366589 361856 355413 347546 343551 338080 330644 325622 320607 313467 309778 304446 299258 294257 289617 283000 279109 274710 270096 266076 261293 257309 253003 248681 243818 240795 235338 231168 227571 224330 220775 216628 212583 209074 206115 202268 198480 195500 191983 188450 185873 181981 178664 176788 172313 169429 167544 164266 161562 159352 156729 153127 151345 148469 146124 143611 141472 137705 136311 133496 131558 129494 127051 124920 122896 120606 118520 117119 115202 113075 110696 108697 106871 105033 103300 101763 99904 98446 96899 94841 93563 91215 90179 88946 86836 85024 84558 82474 81416 80259 78390 77453 76634 74513 73160 71902 71053 69886 68454 67377 66149 65452 64495 63155 61982 61109 59557 58943 58045 56661 56105 55166 54018 53100 51818 50879 50479 49808 48234 47849 46735 46264 45482 44383 44539 43230 42204 42010 41087 39866 39815 39129 38698 37772 36984 36506 35605 35063 34323 33912 33679 32799 32393 31629 31205 30785 30673 29682 29489 29159 28227 28084 27387 26789 26635 26103 25808 25422 25054 24716 24341 23721 23172 22801 22628 22269 21810 21540 20859 20958 20544 20100 19965 19479 19503 19079 18753 18465 18015 17665 17625 17079 17218 16508 16473 16353 16181 15897 15716 15372 15076 14671 14622 14414 14161 13970 13549 13789 13535 13230 12958 12835 12289 11888 12340 12033 11819 11709 11477 11153 11221 10962 10881 10793 10545 10415 10337 10156 10186 9897 9882 9668 9711 9358 9326 9312 9352 9257 8796 8784 8801 8777 8566 8380 8237 8207 8095 8098 8029 7608 7581 7515 7508 7384 7324 7294 7191 6917 6947 6862 6759 6681 6597 6580 6246 6363 6282 6094 6248 6026 5916 5915 5970 5821 5820 5853 5792 5645 5794 5460 5329 5407 5467 5483 5212 5347 5231 5208 4981 5266 4980 5075 4907 4931 4831 4916 4895 4766 4582 4681 4642 4672 4474 4477 4504 4446 4606 4473 4179 4096 3957 4102 4150 4062 4129 4116 4021 3963 4026 3866 3921 3983 3697 3879 3654 3804 3652 3668 3506 3547 3563 3495 3555 3418 3357 3629 3552 3289 3412 3280 3272 3393 3256 3455 3481 3377 3157 3188 3224 3224 2932 3015 3226 3237 3328 3151 3122 3061 3106 3111 3063 2992 2879 2873 2741 2750 2806 2809 2712 2835 2707 2723 2678 2715 2746 2702 2860 2685 2671 2666 2696 2596 2667 2550 2595 2583 2711 2548 2623 2558 2559 2475 2471 2582 2594 2480 2469 2407 2404 2427 2438 2594 2348 2299 2579 2374 2481 2423 2419 2402 2332 2310 2252 2376 2144 2212 2153 2344 2193 2214 2176 2120 2291 2197 2002 2254 2217 2232 2271 2142 2015 2102 1925 2122 1859 1934 2063 1979 2049 1887 2038 1899 1928 1994 1831 1925 1935 1893 1787 1884 1994 1955 1921 1997 1984 1842 1956 1772 1837 1950 1927 1786 1840 1841 1763 1717 1813 1673 1728 1706 1845 1691 1688 1715 1802 1755 1772 1836 1774 1786 1773 1864 1729 1894 1596 1672 1624 1584 1586 1765 1673 1598 1659 1621 1550 1608 1638 1575 1524 1544 1631 1575 1527 1512 1464 1549 1598 1635 1567 1549 1495 1568 1589 1605 1526 1541 1652 1605 1614 1657 1551 1481 1549 1585 1400 1528 1490 1527 1483 1457 1488 1436 1370 1484 1467 1502 1466 1553 1616 1423 1489 1295 1485 1542 1461 1510 1434 1293 1386 1456 1425 1349 1366 1418 1413 1315 1471 1516 1377 1385 1360 1405 1233 1528 1421 1358 1451 1312 1328 1404 1436 1414 1532 1372 1486 1482 1318 1414 1366 1323 1342 1248 1223 1404 1199 1217 1215 1261 1268 1155 1192 1199 1217 1279 1221 1277 1308 1175 1196 1261 1375 1279 1297 1226 1297 1206 1248 1205 1308 1213 1173 1246 1242 1174 1183 1160 1092 1042 1043 1045 996 1096 1172 1090 1129 1118 1072 1150 1112 1063 1101 1023 1082 1037 1011 1045 991 1090 991 976 968 895 993 1054 1028 1040 1001 907 999 982 1031 1021 916 877 1021 963 911 1002 926 975 924 1007 942 848 888 803 901 966 968 924 901 950 980 876 951 919 1014 991 978 1019 975 933 924 876 949 995 862 888 997 872 899 813 869 786 903 852 872 894 974 955 971 859 808 903 891 893 825 940 890 816 825 807 887 969 829 861 813 807 855 858 802 813 789 769 741 761 791 675 768 775 785 812 764 849 751 790 817 788 797 755 800 750 769 868 835 775 876 858 836 719 798 944 822 852 764 765 852 701 767 771 767 848 786 792 717 745 712 723 673 693 721 617 683 676 605 665 653 641 659 647 606 651 645 692 724 779 761 747 754 681 687 626 630 675 743 673 659 744 702 609 636 593 554 533 582 524 614 609 637 659 631 605 582 571 530 513 578 580 584 585 658 578 571 614 561 556 556 571 505 590 564 580 532 599 541 594 586 537 653 557 529 576 514 537 617 518 514 591 509 601 654 467 462 576 560 559 609 480 550 450 516 490 521 533 493 455 451 449 459 501 440 468 467 378 458 386 390 484 481 404 429 468 380 431 382 484 397 362 385 429 466 363 389 421 439 470 423 394 407 416 374 384 459 451 464 419 344 400 482 382 381 350 380 366 415 410 456 444 450 488 404 477 463 452 454 440 434 409 377 449 356 407 418 479 427 418 526 461 449 407 424 466 335 419 426 385 460 401 393 355 346 393 385 385 405 425 402 360 318 313 403 379 327 381 397 404 386 324 367 355 301 307 294 294 283 346 306 345 312 306 353 347 317 354 323 370 333 263 307 292 211 295 266 287 212 231 211 262 227 277 241 263 277 270 334 334 306 328 238 320 299 300 304 296 306 345 322 302 305 312 342 354 410 316 390 280 358 326 318 346 319 356 363 351 358 339 341 303 307 317 307 362 322 331 316 430 359 342 360 323 335 340 284 323 353 289 307 303 299 303 208 350 301 303 313 297 245 285 276 350 288 299 379 286 278 346 266 277 270 229 240 294 248 241 254 281 213 260 302 257 238 233 235 255 237 306 250 281 316 288 282 303 272 362 317 334 289 246 308 298 271 243 246 283 237 307 262 194 250 279 253 298 250 217 262 219 183 171 201 215 209 189 207 182 255 202 170 235 219 213 235 222 213 201 191 237 237 272 236 187 222 205 217 211 186 190 233 202 168 193 162 205 213 197 185 207 182 223 202 195 257 191 247 205 260 207 205 222 186 237 197 185 250 249 249 242 264 296 255 282 260 275 267 279 214 213 242 239 216 245 234 260 242 247 224 228 249 256 179 235 256 193 205 216 204 216 235 221 178 227 242 239 236 272 223 240 196 209 176 204 190 195 135 150 160 145 169 150 190 165 182 173 178 188 185 193 159 164 173 205 185 217 175 189 197 172 188 242 158 185 185 227 187 237 199 193 218 251 176 261 245 215 253 241 213 198 226 202 171 177 164 156 164 164 160 176 173 151 167 174 204 144 152 192 142 153 132 137 121 144 150 159 161 188 157 135 159 183 221 200 176 167 212 223 204 211 165 228 203 142 144 187 220 190 218 200 243 198 189 206 258 212 269 267 219 200 274 194 174 214 226 231 204 240 209 238 213 163 212 220 217 197 193 163 234 182 198 213 259 242 279 267 245 244 184 229 255 278 186 243 244 233 234 163 205 230 205 253 200 200 216 209 237 235 257 273 255 171 206 217 166 219 218 195 174 199 146 184 150 172 180 232 206 158 167 183 131 218 170 200 125 148 206 183 147 164 143 149 133 136 156 102 145 188 154 161 142 223 168 132 128 171 133 133 185 186 187 206 158 158 133 184 149 143 159 151 144 216 175 155 213 151 198 204 194 171 199 190 187 194 139 170 167 143 153 191 132 148 127 127 153 139 178 172 155 172 136 192 206 164 202 144 166 180 164 203 167 198 163 196 194 187 212 193 252 311 234 191 227 212 242 225 245 281 251 279 371 290 259 305 286 282 301 318 358 267 268 295 299 403 286 335 331 287 308 382 300 282 298 309 262 305 246 309 260 236 263 282 206 221 273 222 222 186 203 178 192 187 160 191 165 180 162 163 183 129 226 176 180 169 159 182 151 150 133 182 125 183 162 182 187 155 175 138 141 171 166 138 159 139 155 124 162 138 121 141 169 151 149 178 142 137 170 119 135 120 124 142 146 141 137 112 110 128 212 178 242 160 177 221 217 205 137 169 212 167 151 256 224 179 168 205 157 151 200 107 180 146 153 150 94 121 120 97 105 103 140 72 121 96 122 98 128 128 135 153 105 130 114 136 119 101 124 110 115 143 138 118 116 139 135 142 125 111 121 105 114 112 113 119 147 121 117 142 97 139 157 129 118 147 81 110 113 104 150 128 143 110 83 104 93 75 105 101 99 83 92 102 90 153 107 102 87 127 108 108 134 118 107 79 119 96 132 119 100 135 81 83 105 123 124 109 112 87 139 117 122 95 102 94 143 147 105 135 116 144 148 141 126 136 68 148 89 96 94 62 89 94 107 123 111 96 147 80 119 98 110 98 59 93 100 100 74 77 68 82 78 86 82 114 88 92 80 64 74 75 61 40 58 48 53 42 55 62 57 72 62 50 48 53 40 56 51 50 43 54 57 56 70 52 64 67 81 99 48 77 37 56 61 84 94 84 91 84 74 84 67 100 61 84 90 74 45 80 101 64 96 57 88 88 87 51 85 59 54 98 44 53 49 46 48 80 
];
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
 185188 166793 18395
 91786 80257 11529
 195015 141244 53771
 202476 175430 27046
 93199 81095 12104
 528345 360943 167402
 75953 65426 10527
 176977 160396 16581
 44923 40334 4589
 282432 226314 56118
 94226 86188 8038
 109230 99791 9439
 194715 147505 47210
 132537 121493 11044
 318005 291726 26279
 77774 68442 9332
 175232 134474 40758
 646591 595004 51587
 367088 326953 40135
 192174 155888 36286
 432907 406061 26846
 182445 168255 14190
 103139 91177 11962
 297907 227966 69941
 564379 506821 57558
 188906 170292 18614
 158619 130541 28078
 234356 209233 25123
 239194 219592 19602
 758029 705195 52834
 120660799 111101293 9559506
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
270 1755 44 94
65 244 17 31
124 337 34 46
220 436 61 57
269 418 65 100
284 513 2410 387
1215 777 5880 1463
15088 874 7219 2773
234534 1150 9300 4456
644972 1796 12404 6881
1044067 2343 14121 9630
1638667 4092 18407 13864
2222221 7170 23062 19394
2791108 14547 31889 28881
2953182 28844 44321 41582
2823079 55138 65058 63117
2207861 92302 90448 89870
1370860 138484 122086 121363
669977 200522 160807 159677
308342 274874 198674 198639
220366 346685 235275 236468
228920 407386 270015 272703
256829 442113 304617 305091
288092 460696 333727 333094
320270 469178 361524 361069
356258 476002 388655 387097
391875 481905 419195 418349
428552 496296 448594 449877
465291 512361 480753 481734
501326 539158 515662 517564
539092 568226 550702 547863
574365 599747 584336 582809
607758 629812 614488 614442
635471 662728 645858 646679
663876 688376 674955 673846
689761 709173 699911 699734
712605 729213 721496 720916
730319 746684 739149 739679
748735 764319 755947 755529
761978 777664 769657 770582
774090 789810 781624 782597
784697 796127 788677 790428
789901 801519 795277 794395
786989 801711 793197 794400
779575 789820 785989 785161
767553 773064 770167 770519
733463 742564 738813 739272
690311 695376 690786 691437
634758 640001 636656 637823
575836 579289 576165 576899
503908 507667 504989 507276
440520 443940 441123 442773
384353 386855 386844 386910
342010 341838 341029 342671
313112 312235 313752 313276
293193 294512 292759 293552
280577 280912 280415 280892
276926 277644 276718 277055
282911 282671 282272 283717
291142 292858 291837 292555
312166 313567 313692 313473
319266 319034 318899 320012
324581 325754 326582 325416
324776 324707 323889 325127
311527 311979 312364 312188
287791 288509 287048 287301
242344 243670 242285 242936
192981 193565 193502 192591
140021 141095 141165 140661
89010 89568 89707 89228
37863 38749 38409 37877
6368 6496 6406 6306
0 0 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

];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 
];
