A = [
1487192 1352244 2347818 1372365 1307180 1220363 1180653 1196706 1343918 1283838 1471746 1398079 1522631 1766724 1992541 2342774 2539601 2696580 2710417 2679920 2417466 2140805 1965570 1936022 1951670 2356095 2395348 2405615 2629213 2268546 2260602 2144218 1839616 1864226 1795448 1844269 1855967 1677739 1725540 1678557 1614020 1672811 1642707 1689203 1763643 1762879 1710535 1678239 1748987 1695032 1601720 1613014 1680598 1673965 1667003 1710530 1651045 1700414 1678072 1575336 1555379 1569536 1587945 1575846 1623965 1686930 1677818 1657745 1637678 1626196 1577155 1572619 1608096 1603506 1626559 1649237 1671149 1636314 1614301 1577029 1526391 1535595 1484434 1485953 1511021 1496085 1473762 1438670 1428664 1410078 1384783 1370710 1367986 1356416 1355252 1362416 1349010 1347273 1348296 1315704 1299494 1293832 1276867 1266037 1272773 1278905 1271306 1273966 1267782 1259661 1239775 1226641 1221484 1213209 1211859 1209222 1225979 1221648 1212499 1203338 1196943 1183754 1170831 1162048 1159214 1158624 1153566 1153231 1149694 1144034 1132681 1126289 1120452 1108886 1097794 1097226 1083589 1082607 1085202 1072353 1069387 1059098 1049006 1041051 1030155 1025395 1024625 1027916 1026418 1028461 1025507 1013955 1011977 993155 985525 976546 970555 969121 960688 956661 951725 944238 932350 928215 921543 917773 913328 908760 904590 904792 897573 892669 887393 883222 874623 868392 865283 857593 857643 852018 850125 845612 839920 840763 829767 826205 820578 815164 812258 808151 808872 804899 801748 800570 797182 790143 787322 784083 780061 778543 773517 771404 770274 765184 761363 753854 753703 750584 742210 737231 733554 728624 719340 715083 709138 702528 694834 690848 690203 685586 686475 684867 680578 683324 676161 670203 662146 655311 648414 642771 636496 632014 628115 622780 616848 613324 606864 604111 599095 592351 588743 585351 583595 579238 576263 572932 569444 566670 560317 556044 551089 546584 544558 541609 537636 533024 531537 527227 523586 518956 513783 511771 508793 503407 500728 496206 493091 490587 485335 482778 477505 473828 471256 467923 463030 460317 456761 454667 451971 446634 443197 440270 434467 433361 429189 426293 424491 419650 416957 414493 410242 406346 402083 400421 398279 394105 389575 387500 383234 380396 376744 372172 368787 363338 361284 357309 356642 352564 348581 346798 342023 337909 333782 330334 327609 324426 320370 317046 315401 313088 309021 304336 302033 298046 293618 289647 288898 284973 282636 278914 276939 273037 270496 266267 261816 259201 255926 252485 249541 246436 243768 240929 237184 233421 230898 227571 225569 221947 219573 217164 213431 210426 207749 205431 201842 198517 194816 193450 189494 187925 184693 182468 179961 177358 173968 170263 168241 165516 163391 160782 156950 154681 152564 149056 147503 144838 141571 139568 137128 134860 131600 130007 127409 125340 123188 121437 118803 116561 114020 112669 110383 108806 106820 104770 102381 100173 98382 95965 94288 92787 90800 89265 87737 86062 84115 82593 80599 78862 77170 75853 73756 72406 70868 69126 68318 66186 64575 63606 62539 60843 59776 57990 56410 55673 54468 52990 51855 51167 50070 48244 47726 46509 45237 44173 43605 42487 41181 40966 39617 38289 38011 36928 35800 35447 34450 33878 33020 31945 31199 30583 29636 29153 28223 27365 27092 26528 25738 25385 24259 24104 23445 22745 22057 21811 21254 20639 20334 19554 19143 18660 17921 17916 17242 16992 16458 15951 15597 15216 15026 14397 14366 13870 13674 13147 12859 12605 12256 11749 11629 11173 11012 10878 10382 10108 9965 9685 9344 9288 8996 8845 8559 8233 8395 7880 7720 7606 7610 7326 7047 6718 6377 6483 6207 6029 5987 5710 5629 5496 5369 5158 5075 4937 4818 4729 4686 4580 4390 4281 4138 3893 3983 3852 3890 3767 3530 3438 3495 3349 3168 3202 3035 2983 2998 3027 2853 2798 2714 2630 2501 2503 2357 2317 2389 2279 2266 2215 2118 2116 2030 1940 1962 1971 1900 1842 1836 1839 1882 1734 1725 1687 1597 1562 1568 1550 1466 1471 1350 1451 1558 1348 1352 1319 1179 1298 1203 1214 1130 1110 1369 1090 1100 1119 1102 1017 1050 1035 943 1039 948 936 1030 909 921 1003 999 888 818 820 819 809 841 910 802 772 843 888 741 781 748 722 714 632 645 738 630 686 608 626 613 622 623 588 622 663 591 582 645 777 562 586 615 608 561 593 525 548 525 526 530 538 535 500 464 510 503 571 489 505 500 522 506 475 461 455 492 508 469 477 486 442 437 471 449 469 474 419 423 449 417 428 413 419 451 469 399 436 416 415 414 403 425 403 364 412 415 411 397 407 404 406 407 395 372 359 372 360 350 358 399 362 381 381 344 397 367 365 377 390 342 376 376 298 361 301 365 326 288 321 312 323 302 305 322 382 341 536 433 326 403 360 337 364 359 308 362 294 605 314 273 320 298 436 426 287 325 326 328 332 284 265 319 310 278 287 291 290 289 272 268 272 269 242 264 317 349 365 250 277 259 262 280 265 269 273 263 238 244 222 261 257 247 266 254 256 298 451 253 255 243 225 369 297 243 252 243 317 255 236 229 205 341 267 225 251 226 231 243 224 215 214 225 213 212 228 241 232 201 206 176 196 249 191 255 199 212 211 203 195 231 195 207 217 193 207 223 199 190 207 217 206 241 189 187 179 184 221 171 157 206 361 217 174 184 207 213 217 178 200 146 172 338 168 182 164 186 219 167 192 177 172 157 195 151 162 197 255 176 172 214 193 187 168 177 176 186 156 171 159 165 284 179 168 147 152 177 135 124 135 221 218 151 171 174 156 162 167 153 138 150 197 145 145 133 136 220 174 123 138 153 180 154 149 140 131 200 170 126 148 144 182 142 132 123 146 168 140 127 171 142 150 135 114 124 129 146 151 151 150 157 130 158 144 113 127 151 145 114 112 131 129 129 116 131 112 137 130 108 118 105 128 118 109 115 122 117 115 124 111 108 114 125 101 143 106 115 133 123 112 97 123 131 110 130 128 126 123 108 103 106 112 129 111 106 119 143 106 95 94 117 154 110 104 95 90 107 101 104 104 86 109 99 96 90 86 105 96 119 100 103 99 87 93 102 97 91 104 125 86 86 84 102 192 93 100 91 70 131 89 89 96 128 98 91 91 80 95 99 88 89 78 92 94 86 81 75 96 93 69 81 63 86 83 79 72 70 81 96 57 80 66 55 81 99 91 71 74 65 81 91 69 88 80 111 78 94 74 114 94 89 102 102 97 89 86 156 97 76 75 90 117 123 96 105 94 133 116 85 98 97 139 107 101 132 130 127 138 107 106 123 131 170 91 134 116 166 117 121 77 90 123 101 88 98 85 64 65 69 86 86 86 78 76 65 57 48 71 62 90 65 58 68 84 79 56 50 63 67 62 58 67 70 87 70 70 54 93 77 73 57 65 83 68 49 61 53 76 49 49 35 59 77 60 57 61 67 66 52 64 65 49 84 75 55 57 54 91 59 70 59 46 75 53 62 61 64 54 74 71 53 61 61 70 69 67 48 68 68 75 84 73 65 83 101 41 87 62 81 85 55 98 63 75 67 114 55 65 101 54 89 83 74 85 89 117 82 73 115 144 99 173 89 166 103 92 93 51 146 154 75 166 53 60 74 138 121 44 121 137 81 106 48 114 86 94 122 59 137 134 84 77 43 97 88 39 89 50 97 83 47 104 66 106 69 88 83 55 113 90 60 81 63 70 75 35 60 68 57 56 43 56 54 53 51 40 36 52 55 48 49 47 41 42 59 41 40 48 44 47 37 46 57 56 37 37 45 44 43 38 29 47 49 30 47 32 39 36 35 40 40 45 40 43 51 43 40 41 38 29 53 34 48 45 34 53 33 32 36 33 44 38 27 39 18 34 41 25 35 34 28 31 28 41 33 30 14 27 24 27 13 29 31 28 32 27 23 32 32 20 27 36 32 46 30 29 34 38 44 49 52 28 50 52 37 46 49 23 43 38 48 44 36 35 38 43 41 38 36 42 34 60 28 44 39 71 60 35 35 55 60 34 32 47 45 36 70 29 49 42 44 38 32 41 60 80 25 48 34 45 42 56 42 67 39 124 61 43 34 36 51 18 49 29 49 115 111 35 79 138 128 107 85 44 28 119 36 44 36 50 138 93 45 74 64 143 128 40 41 45 135 27 47 34 43 113 78 58 100 163 192 189 70 23 31 30 68 68 18 25 25 21 29 21 21 51 37 119 24 31 33 82 78 43 36 31 28 37 22 22 28 119 59 25 38 39 33 69 17 30 28 25 44 45 22 26 71 36 36 32 24 39 68 28 22 20 18 69 40 39 27 89 72 42 47 22 34 44 40 25 39 28 76 28 51 64 105 61 49 62 78 310 90 82 30 57 92 93 20 42 31 101 70 22 23 25 25 44 35 16 35 29 57 22 18 20 21 23 16 10 21 24 22 21 18 24 21 18 21 15 20 12 18 18 25 26 22 11 35 24 22 30 19 43 44 21 27 32 43 38 27 35 27 45 46 38 33 33 60 46 16 24 22 47 43 27 23 29 40 35 22 22 28 36 24 13 18 36 43 30 21 24 26 33 27 21 22 63 23 11 15 16 62 12 16 11 25 20 16 12 20 18 11 14 12 9 17 12 20 13 12 4 12 14 11 5 13 4 16 13 14 9 10 8 15 13 4 13 10 11 8 6 12 12 12 10 12 7 21 12 15 6 10 8 6 12 11 13 11 8 6 14 15 13 9 22 13 14 19 14 5 9 8 11 23 7 9 18 16 18 9 11 11 12 14 12 7 17 14 14 14 8 17 20 9 14 17 10 12 13 4 5 13 21 15 10 7 6 15 12 10 7 11 12 13 5 12 10 13 12 2 11 15 8 16 8 8 12 6 6 10 7 5 7 5 11 8 9 15 4 8 5 6 7 10 9 5 20 19 10 13 8 15 9 12 12 8 6 7 9 7 9 9 14 5 11 5 12 6 12 10 8 10 8 15 12 10 13 3 13 15 9 10 11 13 9 3 11 17 31 16 8 15 13 16 15 12 10 16 21 14 26 12 13 14 21 9 10 10 9 7 13 7 7 18 11 10 8 7 18 12 8 6 9 17 11 3 7 8 23 13 11 9 8 8 16 10 10 2 14 10 9 13 5 15 10 10 12 10 7 9 14 6 9 6 10 6 8 5 4 8 9 11 19 7 8 10 10 6 15 11 10 11 10 15 12 9 10 7 3 12 4 11 6 12 21 12 6 15 6 11 13 
];
B = [
0 0 0
 832898 544365 288533
 1038033 710760 327273
 690273 463450 226823
 2015130 1509419 505711
 884509 642915 241594
 654511 490449 164062
 657198 498281 158917
 425237 321045 104192
 346061 267982 78079
 267228 208899 58329
 471877 373666 98211
 407405 312192 95213
 498957 384227 114730
 1850358 1491824 358534
 695738 541121 154617
 807257 645943 161314
 745657 600883 144774
 652855 525013 127842
 828982 672437 156545
 721859 585066 136793
 1506447 1234333 272114
 827437 672311 155126
 966763 788582 178181
 823296 673173 150123
 764815 625585 139230
 925562 759026 166536
 1141375 939585 201790
 660682 539950 120732
 1241259 1021425 219834
 1031796 848004 183792
 856491 703976 152515
 868140 714821 153319
 1012916 833855 179061
 1164370 963960 200410
 742064 611181 130883
 1191885 984957 206928
 1562330 1312330 250000
 832778 688286 144492
 997168 827265 169903
 1418820 1190888 227932
 1144737 951263 193474
 1156099 970469 185630
 960759 797815 162944
 1086077 905149 180928
 1179848 993261 186587
 965745 806389 159356
 1354662 1140234 214428
 1094598 914070 180528
 1129575 955202 174373
 1004816 842323 162493
 1305063 1102545 202518
 919074 772297 146777
 1350084 1142706 207378
 898727 755533 143194
 1219980 1036940 183040
 1289163 1092191 196972
 863139 725116 138023
 1260550 1067889 192661
 764048 640375 123673
 121641837 106640830 15001007
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
15 60 0 0
1 5 0 0
9 18 0 0
11 15 0 0
16 8 0 0
23 15 0 0
91 44 1 1
192 51 10 4
966 73 14 9
2731 130 92 39
4927 164 434 169
10622 229 974 560
19957 454 1620 1257
37861 723 2924 2341
74431 1418 4925 4280
213515 3092 8396 7935
1193752 5989 14152 13561
6327779 11598 23778 23669
12190834 21769 42006 42242
5463962 34959 67864 67543
688948 51419 95938 95500
151448 73005 124556 124417
159825 104205 151314 151767
188268 141820 180518 180697
220013 186730 214432 214361
258092 233254 251771 252462
300053 281657 291668 293377
342245 327251 335026 335037
385814 371128 377346 378426
426276 415691 419687 420135
465692 452811 458471 458783
495661 485814 489797 491199
523069 515360 517783 519230
545980 540485 541461 542990
564581 559997 560191 562383
579721 575674 576462 577273
593392 591043 591058 592152
606337 606313 606554 607344
623682 622173 622735 621829
639870 637830 639238 639241
658219 658743 658292 658203
679389 678879 679234 679558
705902 704726 702901 703957
732382 733132 733941 732989
763835 765738 764194 764749
799261 797808 797672 798942
833247 831984 833076 833509
860330 862055 861579 863489
884733 886100 884899 885714
900742 899781 898738 900075
902860 900067 901472 901234
890906 888432 887609 892765
864474 866430 864625 864954
832741 831615 830737 832658
786932 785352 786991 786805
733138 733010 732306 732582
675673 675263 675615 675949
616875 616448 614710 617299
559421 558957 557845 560159
510819 509909 509024 511477
475054 473807 472932 475224
449983 449746 448850 449422
428172 428987 428952 426465
423189 423655 422275 423900
431885 431888 432013 432586
447390 447435 448193 448293
473110 471736 471622 473323
516985 519639 514755 518735
550737 550563 550077 552237
579758 580115 577960 581090
595267 595682 594910 595446
596087 598630 595252 597190
555585 557398 557444 558305
480937 480933 480136 480148
400989 400911 399420 401659
318962 317887 317545 318742
234926 234919 234131 235154
161543 160791 161063 161456
116965 117125 116433 116762
81437 81507 81567 81842
53556 53725 53396 53216
33443 33569 33558 33700
3250 3169 3129 3112
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
