A = [
5657475 5280288 10486111 5718188 5497682 5312000 5055556 5442560 5262335 5276117 5620013 5911986 6653969 7274366 7734543 8331852 8923938 9765111 10032463 9804137 10301166 10560963 10344867 10320276 10472050 12413510 12562871 12678964 14289220 12003443 12147140 12036510 9842170 10011300 10025094 9964742 9861812 9638676 9572628 9516308 9454664 9462766 9486526 9559555 9524239 9391965 9292838 9290784 9043243 8975216 8978367 8778675 8891694 8886273 8775541 8710370 8672649 8620120 8382439 8222392 8235066 8071584 8044395 8025802 7938518 7974212 7850400 7718549 7660180 7513725 7476863 7430461 7342133 7350329 7387759 7332923 7278215 7230597 7114947 6967898 6861593 6769150 6661526 6574676 6552489 6451249 6353738 6192878 6077120 5993612 5891396 5787633 5727817 5652848 5586876 5557931 5503586 5445324 5383346 5301395 5235336 5148971 5070073 5022096 4964198 4917666 4867967 4820042 4766923 4715838 4643305 4606533 4542740 4491003 4466205 4429603 5001164 5014937 4977731 5534569 5536311 5485611 5427859 5366132 5311995 5260698 5211414 5168222 5124506 5065162 5006834 4933547 4860085 4801154 4736759 4680501 4630679 4593675 4552069 4500277 4450692 4397699 4333314 4264613 4205293 4150076 4105921 4060748 4014816 3988301 3930842 3880972 3833562 3769140 3713865 3663417 3614240 3573110 3537915 3489987 3456705 3414737 3368552 3323266 3270317 3221556 3190051 3144246 3107974 3075132 3032845 3002121 2961749 2923919 2882785 2841851 2804425 2767742 2736927 2699554 2668954 2637776 2609255 2573803 2539322 2506507 2464355 2433387 2409568 2391899 2355048 2323779 2295031 2269233 2239292 2207998 2177362 2147720 2118455 2091116 2070837 2047638 2020020 1997159 1971616 1944159 1922523 1888752 1863437 1844973 1815684 1788066 1768784 1744856 1722915 1701535 1676496 1654359 1631434 1610106 1585182 1561087 1539193 1521383 1496088 1474046 1452281 1428283 1402815 1381952 1360234 1339412 1320100 1300265 1281727 1263723 1244666 1228636 1210285 1193314 1174939 1156233 1141283 1125044 1106418 1091124 1074845 1059347 1043394 1027572 1014118 996180 982160 967859 952670 939795 924944 914025 898425 885019 872226 857921 844957 831832 820511 808536 796511 784716 772911 762489 750629 739313 728127 717563 707153 695090 686061 674545 665998 654957 646157 636627 625365 617107 607617 598641 590051 581476 571628 565047 555960 544576 538710 530847 523092 513989 508119 499946 489653 483896 476315 469949 461003 454724 447211 440794 434034 428197 420951 414440 407574 401633 395280 390508 384381 378177 372920 365770 360413 355087 349292 344473 339320 334204 328590 323299 318485 312708 309097 305540 299484 294935 289981 285367 282066 277320 272060 268121 265095 260421 256419 253369 249031 244581 240672 237811 233767 230646 225519 223118 219590 215855 213071 210342 205949 202754 199476 196784 194375 189875 187577 184781 181951 179269 177143 174262 171146 168193 166518 163103 160896 158487 154821 152850 150641 148464 145721 143593 141989 139795 136623 135144 132468 130940 128513 127004 125140 122874 121197 118490 117053 115336 113299 111449 109888 108590 106359 104903 103177 101911 99505 98608 96851 95003 93553 92541 91326 89223 88388 86204 85348 84709 82655 81351 80257 78969 77507 76976 75443 74657 72882 72477 70625 69866 68769 67500 66853 65906 64557 63867 62627 61337 60586 59253 58750 57814 57229 56006 55017 53991 53097 52193 51695 50799 49940 49413 48678 48057 46738 46191 45132 44854 44465 43420 42700 42018 41632 40676 40219 39499 39178 38552 37624 37006 36783 35866 35691 34886 34249 33722 33498 32680 32201 31563 31251 30808 30258 29885 29375 29038 28415 28400 27703 27171 27161 26292 25901 25512 24942 24660 24346 24146 23709 23136 23075 22713 22407 22052 21653 21449 20833 20384 20625 20107 19773 19133 19163 19044 18658 18308 17943 17670 17561 17321 16972 16637 16483 16035 15819 15833 15434 15236 14868 14722 14610 14485 14039 13834 13793 13375 13347 13216 12905 12723 12630 12262 12204 12007 11847 11750 11561 11320 11189 11055 10804 10722 10612 10389 10171 9984 9712 9665 9641 9511 9298 9103 9077 9145 8759 8867 8546 8543 8435 8247 8229 7977 7865 7797 7802 7764 7530 7367 7251 7161 7138 7065 6872 6751 6758 6779 6528 6542 6238 6266 6250 5980 6075 5866 5917 5866 5860 5587 5595 5641 5374 5402 5378 5160 5160 5118 4976 4935 4943 4760 4681 4683 4620 4518 4508 4357 4427 4424 4288 4200 4258 4183 4039 4046 3967 3970 3910 3800 3793 3795 3723 3656 3650 3574 3580 3453 3459 3425 3368 3374 3289 3351 3192 3105 3156 3038 3032 2932 3061 3068 2956 2802 2875 2725 2883 2790 2722 2738 2708 2735 2731 2724 2493 2552 2564 2548 2443 2451 2577 2484 2280 2420 2262 2302 2340 2313 2228 2250 2242 2196 2124 2140 2127 2133 2107 2053 2047 2058 2032 2021 1987 1962 1974 1925 1860 1937 1904 1912 1816 1884 1834 1840 1864 1768 1754 1813 1703 1707 1666 1673 1690 1649 1571 1602 1538 1616 1617 1593 1573 1509 1509 1505 1580 1509 1477 1490 1412 1458 1485 1414 1459 1525 1407 1333 1445 1358 1386 1392 1382 1340 1291 1307 1301 1235 1287 1344 1260 1239 1250 1191 1210 1223 1218 1161 1163 1177 1260 1154 1150 1078 1068 1149 1064 1086 1137 1113 1110 1140 1021 1076 1139 1019 1077 1031 1007 1045 1018 967 1044 958 995 1015 961 957 987 941 954 927 914 959 902 907 865 942 892 939 951 895 888 890 872 810 898 904 847 829 839 817 842 826 846 875 870 849 831 834 803 776 803 818 783 785 808 811 848 788 738 763 850 735 766 783 797 692 721 801 722 771 743 743 768 709 744 749 724 652 698 669 615 678 667 644 668 678 705 701 643 682 722 699 706 672 715 642 623 665 636 665 607 627 626 609 626 600 595 570 576 563 570 599 618 568 565 602 581 577 550 579 563 580 531 589 570 571 505 492 506 526 563 516 549 495 510 521 505 516 484 474 501 523 524 475 499 488 495 432 405 486 470 471 451 487 507 442 438 497 468 447 465 460 431 455 452 404 477 451 434 448 448 442 412 439 407 440 416 409 413 450 417 416 429 406 387 381 397 369 415 389 387 401 409 427 360 403 395 337 345 380 363 350 356 326 371 367 337 360 338 368 344 373 354 333 358 345 332 314 354 329 336 341 348 339 311 302 323 330 316 334 332 327 312 316 307 305 303 284 340 299 283 284 318 313 284 316 312 317 282 276 294 272 255 281 301 318 318 263 288 274 279 281 292 286 280 315 240 267 265 282 244 254 277 291 261 297 281 250 286 239 260 249 247 265 257 264 238 258 270 254 279 252 247 244 236 260 280 270 274 292 275 295 295 260 244 240 247 243 258 262 269 254 281 289 284 284 277 309 289 301 290 303 332 318 296 284 290 277 306 301 299 264 301 243 290 271 245 257 267 275 274 248 295 286 248 265 262 257 243 259 288 265 302 1100 328 309 257 289 258 234 255 227 244 229 228 219 205 215 206 213 250 202 210 189 203 217 208 203 198 228 243 181 192 190 228 189 192 188 163 202 196 183 163 174 173 170 181 180 158 221 183 187 191 189 197 168 169 168 175 179 168 212 164 215 184 192 193 186 158 164 207 267 1717 168 143 129 146 116 135 129 161 133 141 137 137 149 138 116 144 125 117 132 121 126 121 116 131 133 95 132 112 127 116 113 118 119 117 133 135 110 125 111 130 119 134 136 105 125 120 126 142 132 108 111 121 110 141 118 120 110 115 142 128 135 140 118 133 115 131 129 123 131 138 133 133 136 148 116 138 125 171 136 137 141 156 130 155 141 147 139 162 156 136 149 155 158 150 156 154 140 135 152 156 156 126 155 154 148 147 155 151 138 149 150 144 141 136 149 133 157 158 143 134 149 139 151 138 155 147 153 144 156 144 156 151 130 150 116 134 170 144 120 116 127 118 100 94 94 90 96 104 89 79 75 72 72 97 68 72 73 68 81 76 89 75 81 72 70 60 64 74 81 80 79 63 67 65 81 64 75 62 55 77 58 70 89 70 72 74 73 79 85 81 89 65 76 95 85 76 84 69 74 60 85 80 85 79 77 80 72 72 80 71 71 61 67 77 80 90 71 71 78 65 72 75 72 74 88 54 85 66 65 67 61 60 74 56 73 72 59 70 72 63 48 55 78 74 67 58 74 58 57 62 67 74 57 51 46 57 59 65 55 55 61 43 46 61 56 47 55 58 48 55 60 39 56 59 54 48 68 53 55 42 68 53 49 52 51 50 58 54 52 43 55 50 42 50 48 46 57 47 57 44 66 41 44 47 42 38 50 52 47 55 49 49 40 38 54 44 41 43 21 28 32 35 42 39 43 44 41 33 39 32 41 54 59 52 41 45 40 40 47 39 57 44 40 32 42 37 51 45 49 38 48 44 43 63 47 28 27 33 43 26 28 39 20 26 29 39 29 44 37 35 44 30 38 41 38 40 41 30 32 28 29 43 37 42 42 34 43 31 47 46 33 38 36 40 45 40 35 29 39 41 34 34 32 30 42 38 41 22 27 31 32 41 29 34 33 40 35 35 33 32 20 32 25 32 23 33 36 26 45 35 25 27 25 32 28 31 19 21 30 20 21 22 39 22 33 28 12 19 35 37 33 21 19 34 30 26 28 33 19 32 18 24 28 25 27 27 19 23 22 21 24 22 30 29 18 18 23 13 19 23 24 27 16 22 15 18 22 13 15 18 21 14 17 19 25 16 26 10 24 18 28 20 13 20 14 16 16 17 27 18 12 15 6 13 14 21 27 19 20 16 27 20 4 11 11 15 11 18 18 17 13 16 16 10 19 17 16 10 21 13 17 20 13 10 21 19 21 13 16 11 16 19 14 20 16 14 16 11 11 16 15 8 12 8 18 16 11 12 11 15 6 17 5 15 15 14 7 12 11 10 7 7 10 13 16 16 16 18 12 15 10 11 10 8 18 7 16 8 13 14 11 13 13 14 12 11 16 18 10 14 6 14 8 14 10 9 12 7 10 9 9 17 18 15 11 12 9 6 7 14 12 11 5 12 9 12 8 16 8 8 11 12 7 8 10 12 12 7 10 10 9 5 8 10 9 9 11 4 10 10 8 11 7 7 7 20 8 18 5 10 11 14 9 8 14 8 8 10 13 14 2 7 7 5 7 7 8 5 6 11 14 8 14 8 6 11 4 9 11 7 2 7 8 12 5 7 6 8 10 8 10 9 5 8 14 5 7 12 11 10 13 11 3 8 8 7 7 6 12 9 7 6 8 9 6 3 7 8 9 7 10 7 10 11 6 5 7 8 6 7 4 7 9 8 7 6 10 7 7 6 9 6 9 1 7 11 8 6 12 10 9 4 7 10 6 6 12 4 8 6 9 4 6 3 11 7 8 7 7 3 4 4 7 4 9 4 5 4 6 9 7 6 9 6 8 7 8 2 9 7 5 6 5 3 2 
];
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
 3012717 2482135 530582
 2854357 2343852 510505
 3875015 3199065 675950
 2925690 2421290 504400
 4360561 3602777 757784
 3501519 2910616 590903
 3338501 2757690 580811
 8508746 7014330 1494416
 3840496 3208660 631836
 4468198 3727826 740372
 7829036 6487151 1341885
 4754774 3971120 783654
 6346701 5254555 1092146
 4341846 3641278 700568
 4564435 3821075 743360
 6381296 5302880 1078416
 5133387 4310389 822998
 7344224 6129596 1214628
 3908847 3280287 628560
 9088067 7652597 1435470
 5532837 4684018 848819
 7513555 6315227 1198328
 7519326 6387082 1132244
 10153496 8601379 1552117
 3149483 2635750 513733
 10005285 8479924 1525361
 4599107 3825442 773665
 2939558 2463558 476000
 4580345 3810763 769582
 2229204 1885200 344004
 514084570 457170555 56914015
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
54 185 0 1
20 21 0 0
32 21 0 2
36 30 0 1
13 31 0 2
21 36 72 3
201 56 286 31
2684 76 343 97
302012 99 604 250
2136058 137 901 534
3995766 215 1286 838
7446882 421 1989 1393
12695594 722 4921 2794
21379799 1665 13094 8075
30983318 3534 20517 16273
40142978 11664 37808 34319
42638840 21816 82722 79697
35788670 46673 150602 149351
24485286 83032 234203 233218
12909760 131775 341077 342981
5187414 186629 431106 431991
1758955 264453 526603 526577
819314 382349 613208 616608
736112 520673 705475 709944
791729 694406 806113 811623
880149 881134 922358 921952
984228 1074070 1043945 1047751
1099947 1261760 1179008 1183149
1223116 1425928 1318104 1323739
1340992 1579652 1447138 1456264
1441219 1702966 1559910 1565676
1522374 1794727 1645442 1653389
1586926 1860382 1711873 1718307
1628842 1901142 1747011 1757524
1654473 1904388 1768980 1775135
1661715 1890794 1768497 1772091
1656269 1855860 1746703 1749250
1657469 1822006 1729305 1735917
1655556 1789100 1713920 1720669
1651656 1766749 1703868 1708642
1657296 1744540 1696941 1700552
1667072 1741119 1700331 1707022
1694868 1752178 1719601 1725964
1732639 1777535 1753814 1758214
1791513 1826770 1807010 1814204
1873235 1899738 1880936 1888263
1971941 1997333 1980176 1988573
2081921 2100881 2087617 2096191
2203273 2220583 2206126 2216166
2333780 2346500 2334083 2340312
2450516 2461804 2449643 2462381
2540984 2559817 2545456 2554696
2605310 2616351 2602441 2614289
2633701 2649840 2637521 2646192
2623673 2634329 2623216 2633121
2552087 2568798 2551645 2563285
2440590 2451461 2441508 2451304
2290497 2298343 2290166 2297366
2105708 2115705 2105793 2111352
1905160 1911219 1907509 1911140
1718135 1726022 1719144 1724998
1539064 1542072 1537009 1544199
1361722 1364089 1359985 1364859
1204683 1207875 1206190 1208171
1104148 1105065 1104951 1107522
1048257 1051697 1048814 1051629
1036773 1038144 1036108 1038170
981480 984941 980736 986428
950451 950079 949647 951461
953963 953487 951307 955855
924921 923725 923369 926468
877765 876591 875538 878154
800267 800559 799795 803192
703697 702288 701183 704156
605110 607076 604207 607054
492115 491895 491426 492141
355383 356049 357073 358265
250833 250357 251178 251447
196256 195463 194765 197221
130974 130938 129859 130897
69971 70217 70205 70388
29295 29266 28813 29304
1481 1528 1504 1481
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
