A = [
1622033 1480101 3934842 1515556 1462649 1357686 1308930 1348093 1468179 1408461 1607294 1565745 1710626 1970400 2203938 2528204 2672778 2843866 2857796 2784992 2573968 2337321 2189891 2168601 2172467 2585165 2627691 2625869 2865012 2474147 2466847 2363654 2015739 2029315 1977123 2030451 2028815 1853733 1904059 1868280 1800535 1847549 1824698 1877774 1932792 1943938 1893932 1854764 1930656 1876495 1790586 1787591 1850337 1848412 1839106 1882863 1818760 1871866 1848207 1745408 1715870 1731953 1749320 1729048 1777747 1839695 1831646 1811054 1797894 1783183 1744616 1746335 1778890 1772207 1794177 1821167 1844853 1810070 1789030 1752663 1707640 1700199 1655107 1653369 1671252 1652986 1630148 1591569 1573532 1554714 1531670 1516603 1513970 1499844 1498694 1503069 1488046 1486950 1485744 1450206 1434687 1433778 1411957 1400583 1406390 1407651 1405492 1406185 1395916 1390490 1368181 1354718 1349366 1340584 1337849 1337721 1351359 1347709 1340888 1329476 1320513 1305830 1295797 1285173 1284116 1282255 1272106 1274356 1269051 1261168 1250002 1240217 1234251 1223704 1213403 1210841 1197622 1195067 1193837 1181835 1175991 1167145 1157736 1146862 1137005 1132085 1133314 1134098 1134800 1135758 1129981 1120137 1113429 1097811 1087744 1075274 1073424 1070041 1062088 1055702 1048609 1042095 1029379 1023997 1018822 1014016 1008354 1002583 998224 997378 988077 984135 977623 973334 963500 958244 954779 947012 943776 939450 937251 931084 925818 926842 914590 909683 903051 898425 892126 892018 893457 886803 884316 882130 876917 871160 869661 866143 862491 860469 854350 852258 848635 844249 841406 831358 832492 829540 822456 816035 812665 803118 793786 787873 781863 775891 767366 762584 764707 758140 758149 755203 748855 752255 743404 736750 728424 720508 712824 706394 700589 694791 692017 686065 677143 674416 669495 664684 658119 652939 649120 645783 641097 636800 633614 630853 625708 622025 616536 612432 605989 600782 599135 597262 592438 588133 583587 579592 574742 570694 565846 562684 558044 554060 549897 546267 541341 537288 534930 530091 524512 522184 517610 513689 510886 507701 504132 500174 496830 492132 487287 484383 478839 475986 474094 470771 466832 461959 458958 456403 451891 448663 443980 440630 437988 433690 430355 427251 422079 418947 413433 409762 406300 401404 398258 395394 391849 388915 383697 382020 377749 372735 368168 365439 360868 356963 353920 350867 348015 344889 340057 336416 332131 328961 324561 320705 318068 314758 310710 307729 304747 301294 297869 292533 288608 285049 281507 277724 273555 272070 267229 265117 260968 257277 253454 249609 246718 243469 240453 236815 234293 229989 227115 224252 219526 216536 213825 210973 206718 203904 201001 197267 193988 191035 187915 185415 181533 178326 176141 173110 170241 166465 163354 160243 158311 154382 151308 149047 145413 143192 140473 138008 135518 133303 131500 127934 125638 123062 120201 117912 115694 113391 110952 109421 106630 104041 102186 100088 97894 95649 93721 92138 90094 88252 86147 84491 82181 80430 78303 76554 75359 73515 71412 69768 68327 66731 64609 63697 62094 60661 58990 57799 56410 54921 53606 52593 50834 50062 48398 47385 46467 45449 43650 43052 41985 40698 39691 38869 37887 36672 35744 35144 34463 33227 31911 31372 30785 29997 29271 28613 27774 27094 26389 25367 25026 24274 23704 22882 22359 21869 20979 20825 20028 19414 18879 18580 17816 17490 17035 16180 16077 15593 15299 14703 14133 13930 13863 13391 12869 12595 12357 11946 11509 11203 10748 10645 10389 9920 9964 9628 9183 9052 8785 8624 8402 8108 7876 7846 7399 7353 7111 6876 6840 6446 6567 6240 6028 6077 5636 5575 5409 5304 5093 4912 4763 4664 4553 4471 4203 4202 4212 4111 4067 3749 3705 3656 3496 3479 3363 3142 3216 3159 2943 3073 2965 2945 2860 2762 2614 2509 2521 2485 2442 2335 2356 2230 2202 2087 2065 2030 2021 1947 1898 1934 1833 1836 1839 1766 1735 1685 1646 1635 1517 1579 1570 1615 1607 1447 1484 1400 1352 1370 1332 1293 1329 1238 1253 1308 1312 1269 1137 1178 1192 1186 1044 1039 1040 1044 1211 1049 1031 1030 985 975 982 904 872 889 855 861 931 829 826 870 943 794 816 774 773 809 805 835 774 761 830 872 673 803 757 717 695 688 688 726 630 633 644 674 619 613 630 644 658 727 644 585 611 814 564 552 599 589 605 574 519 574 586 535 541 533 521 553 524 516 509 594 549 490 515 559 519 523 493 551 446 493 519 492 461 528 482 482 509 495 475 499 470 490 520 488 485 442 437 447 470 495 426 428 470 445 424 475 452 452 450 410 457 391 420 437 438 443 427 400 424 416 407 405 384 460 424 392 379 391 422 392 404 415 406 419 378 366 373 353 368 372 356 369 331 384 344 351 351 394 412 568 464 396 460 453 381 490 484 402 372 375 614 348 367 390 373 435 503 321 369 376 330 387 323 323 312 294 307 304 327 341 325 299 363 321 320 257 305 356 414 358 292 304 286 311 315 290 297 293 341 272 273 280 290 296 285 273 278 249 302 490 285 256 331 260 467 344 271 320 277 354 316 281 307 297 383 312 275 287 263 279 276 269 270 231 237 272 243 251 231 274 252 247 226 259 238 214 254 235 222 256 234 208 220 212 218 208 222 200 219 232 221 210 228 246 225 235 213 170 212 272 192 239 199 340 219 195 250 262 225 230 222 227 204 209 303 229 228 203 206 260 199 198 218 186 191 204 176 189 233 260 202 186 240 211 195 178 213 210 227 185 194 193 178 273 198 190 152 177 234 151 174 175 283 209 179 186 171 204 173 184 199 157 176 187 214 166 174 171 250 202 137 196 165 192 203 160 180 157 222 204 181 202 174 172 176 155 155 153 171 170 169 181 170 155 157 146 154 150 142 169 173 173 173 120 182 154 134 134 160 154 156 162 130 166 157 138 141 119 151 132 131 118 117 150 155 151 125 139 163 154 127 111 135 148 146 97 160 117 154 144 128 134 145 148 171 121 130 122 127 152 120 110 130 152 122 115 115 133 149 132 131 123 149 127 165 103 106 116 102 110 102 91 90 119 95 109 93 115 123 123 115 107 117 109 110 125 108 106 109 103 110 115 87 79 109 210 100 114 96 98 136 102 82 97 112 118 90 105 98 120 111 121 79 87 97 111 101 86 85 92 107 98 95 95 102 104 108 86 98 86 123 85 95 89 90 109 80 95 89 101 87 112 100 85 80 104 93 106 106 89 132 126 100 123 120 105 123 115 205 133 103 108 109 165 140 107 119 110 161 114 110 115 111 150 129 109 156 132 138 165 105 124 128 139 173 109 147 138 185 125 109 107 102 113 93 94 101 95 83 98 93 121 85 102 94 81 83 79 80 75 69 101 80 55 73 119 95 71 50 106 72 69 76 71 91 86 63 56 64 103 75 68 65 69 80 67 61 65 61 92 67 79 59 61 89 55 55 63 61 93 83 89 65 67 105 75 69 62 76 98 63 74 59 52 83 64 66 60 60 70 67 70 63 73 51 80 87 72 54 74 97 85 83 83 80 89 98 59 111 58 67 70 59 124 73 85 89 108 63 67 97 70 112 121 64 102 82 102 124 63 115 137 117 172 104 199 113 105 112 85 163 170 75 133 67 104 86 174 134 65 151 170 115 117 59 144 102 110 116 63 153 139 86 111 57 110 89 62 95 53 102 94 61 127 57 121 99 89 96 77 115 112 103 73 61 100 74 47 64 61 73 83 40 44 50 62 61 52 53 44 40 51 37 52 58 46 49 38 40 46 36 28 66 37 41 42 45 37 47 45 39 36 34 38 35 30 26 32 38 56 42 33 46 42 42 25 60 39 38 42 46 42 34 46 41 49 41 50 43 48 34 44 42 35 20 35 32 36 33 36 29 30 25 32 42 40 21 28 24 31 43 28 32 33 38 33 28 33 44 35 32 22 27 29 31 49 40 31 28 38 39 34 64 45 43 50 17 65 52 30 58 41 45 47 37 42 30 52 46 55 29 30 44 69 33 47 41 92 66 23 29 55 75 45 35 42 47 56 64 47 42 44 44 28 40 40 64 99 53 44 31 37 43 59 47 42 46 116 67 36 31 50 56 38 51 33 52 128 141 30 78 102 124 89 73 29 44 102 26 59 39 45 132 98 47 82 79 142 98 30 26 19 117 38 50 35 57 122 105 54 63 152 178 169 97 44 17 26 66 76 37 38 32 23 39 25 22 63 35 89 28 29 34 63 82 54 48 22 25 43 19 37 28 109 64 30 32 24 28 71 27 38 28 33 59 39 32 37 83 31 46 38 30 53 73 45 35 31 27 61 26 42 39 104 88 52 62 28 42 55 38 37 49 25 92 49 45 82 92 61 56 85 92 303 116 87 50 93 132 109 24 37 26 104 48 33 52 26 34 40 31 23 33 33 41 27 26 20 22 18 15 17 32 20 20 21 21 22 26 16 29 19 15 18 23 19 21 28 28 16 34 36 29 28 17 40 44 20 24 18 61 49 34 32 28 59 56 45 41 25 57 71 30 25 22 72 51 23 16 24 48 29 25 22 27 38 38 28 20 32 47 41 23 30 31 33 38 24 24 50 29 15 25 21 59 18 17 17 24 17 19 9 16 13 8 12 15 14 15 24 18 14 15 8 16 10 12 12 12 11 15 20 8 11 9 17 12 12 10 13 8 20 9 8 11 10 11 6 7 7 16 15 18 8 14 16 11 10 8 13 20 14 9 13 11 12 19 13 12 17 12 15 9 13 12 14 15 9 14 10 16 18 10 12 12 16 17 14 8 24 15 13 13 19 13 19 17 16 15 15 12 16 10 15 9 18 19 12 15 9 19 19 12 16 12 16 11 7 10 7 10 24 10 10 8 9 12 11 8 7 6 13 8 8 10 16 10 7 5 14 12 15 12 9 12 17 9 15 15 13 11 9 15 3 15 8 6 10 9 8 13 6 18 19 15 10 9 11 9 12 17 8 10 17 17 16 11 12 11 6 11 10 13 9 11 11 11 16 16 11 18 19 21 15 22 17 15 16 19 14 15 21 10 14 11 21 21 17 7 13 9 13 9 14 9 15 14 12 12 15 11 11 13 6 10 14 17 9 20 7 9 11 9 5 10 8 18 11 11 16 5 14 12 20 22 14 10 17 18 11 8 7 11 12 9 12 11 11 9 4 16 16 3 7 7 3 15 13 11 8 14 14 9 9 18 15 14 8 10 11 11 9 10 10 15 8 7 16 9 10 22 20 18 12 
];
B = [
0 0 0
 989665 613314 376351
 1230258 803242 427016
 805974 513284 292690
 2378021 1718018 660003
 1000017 695468 304549
 758574 544418 214156
 778481 566521 211960
 496323 359684 136639
 397272 298091 99181
 304321 231723 72598
 553800 424004 129796
 475321 346616 128705
 584541 425486 159055
 2197995 1707023 490972
 781709 575724 205985
 942378 719945 222433
 855684 659970 195714
 764344 587314 177030
 970921 753759 217162
 828044 641567 186477
 1793034 1414469 378565
 944224 733680 210544
 1105597 866963 238634
 933827 732807 201020
 884755 695965 188790
 1073500 844987 228513
 1338865 1060720 278145
 742902 583695 159207
 1427968 1130479 297489
 1177096 931339 245757
 964011 763776 200235
 979765 777304 202461
 1153205 914807 238398
 1344694 1073338 271356
 805080 640118 164962
 1353213 1079244 273969
 1752099 1434165 317934
 922185 734687 187498
 1099595 884210 215385
 1594283 1301593 292690
 1301849 1045547 256302
 1284717 1051410 233307
 1056199 848284 207915
 1223619 987449 236170
 1296958 1065782 231176
 1052227 851400 200827
 1510008 1236377 273631
 1229192 993835 235357
 1234148 1018761 215387
 1083861 881703 202158
 1448646 1191895 256751
 1007389 821839 185550
 1482404 1222033 260371
 972256 794839 177417
 1330450 1105808 224642
 1410399 1164187 246212
 929222 757826 171396
 1393722 1148878 244844
 822793 667056 155737
 133038101 114947368 18090733
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
22 72 0 0
0 5 0 0
3 16 0 0
16 18 0 0
17 23 0 0
25 31 0 0
144 34 0 0
476 58 4 2
2312 87 14 12
6650 124 115 33
12544 164 747 190
26608 336 1256 627
48705 471 2098 1284
85137 824 3416 2524
142533 1566 5484 4585
281328 3145 9227 8094
1110217 6270 14942 14123
6691858 12357 24939 24240
14002718 23338 43904 43921
5359528 37337 71175 71161
498904 54251 101125 101157
150777 77347 130733 130955
166756 109328 159569 160286
198047 150157 189971 191674
230621 197370 224919 225882
271148 246663 265005 266264
314677 297868 307742 307379
359891 347224 353527 353641
405966 395639 397787 399757
450489 439934 443556 443963
491347 481817 485508 486775
527489 519559 519815 521177
556664 551564 551673 552140
582460 576487 579125 580264
604491 599286 598817 602962
623313 618952 617270 619511
638130 636782 637391 637489
654098 654058 653122 654579
672028 672032 672141 671958
691389 689598 689412 691339
710932 710805 708800 710636
735984 735629 733902 734771
763127 762714 761152 761168
793547 792049 794059 794578
827847 828327 824771 828246
863723 863779 862816 865227
900329 901756 899740 901055
932060 932661 932865 935624
956959 957448 957741 957589
974068 974534 974340 977041
973935 975471 973994 977108
962800 965487 962695 966108
935909 936859 934311 937584
900679 899920 901050 901275
849832 850512 849095 852395
792721 793702 793777 794038
732055 732151 732186 731932
667230 669152 668296 668870
607967 606977 605885 608191
555654 556653 554521 556271
515845 517676 516176 515051
489975 489939 490318 490632
467023 469042 467625 468891
462462 462312 463644 464936
472244 472199 472916 471885
489838 490680 491471 493019
518300 518069 517860 519332
568369 571917 564487 568253
604667 602555 603209 605288
634916 635991 636300 639138
652245 654168 654506 655141
656745 656342 657130 658977
614599 616603 613828 615375
532504 531540 531306 532301
444641 444522 443097 444633
353460 354159 353546 354359
262164 261290 261819 262802
181139 181555 181348 181436
132317 131651 132132 132732
93090 93263 92640 93405
61290 61144 60865 61645
38721 38413 38926 38388
3672 3696 3641 3591
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
