A = [
684282 676663 3533754 557971 540848 506863 483353 476794 464208 438997 431367 424258 415346 408590 403233 396610 390901 386429 383170 379535 376970 372977 369951 368981 375993 508588 506613 512806 645899 646101 655200 661409 662994 671984 674944 670544 662216 656557 650055 642778 641253 637857 636464 634903 634772 628205 622878 616121 610582 606650 600820 597838 595622 595647 592023 588464 584555 578168 575159 567535 563940 560075 556945 556000 551179 549437 546910 541997 537756 532730 527676 523912 520758 516294 511430 510205 506439 502121 496876 492609 488870 485185 482255 479641 475561 471643 467359 464795 460809 456454 452359 447784 444951 441723 438462 437010 432428 429116 427247 421315 417351 414894 408927 407826 406600 402330 399984 398764 391995 390233 385957 382325 377720 375563 372935 368456 366030 363051 360499 357176 354659 350417 346435 341519 338947 337635 334428 332068 329663 325342 322150 321316 318430 315122 311585 308350 306549 302857 300791 297944 295420 292231 290431 288577 285869 283590 279608 277874 274192 272706 270563 267231 264167 262777 259800 257338 255780 253265 249858 248852 244974 242962 238519 236852 233936 232095 230070 228222 225825 223024 221622 219050 215846 214275 212465 210452 207465 205707 204286 201415 200689 197632 195023 194012 192081 189818 188618 185675 183627 182009 180476 179478 176391 174069 172674 170899 169164 166808 166031 163700 161833 159646 158014 156005 154166 152755 150396 148492 147537 145426 144389 142808 141228 139101 137518 136546 135404 132793 131330 130047 128450 126780 125943 123630 121872 120597 119105 118176 116508 114406 114112 112334 111052 109259 107198 107102 105073 103492 102574 100257 100427 98634 96984 96932 95561 95031 93682 92566 91695 89979 88624 88094 86932 85574 84618 83187 82208 80847 79806 79337 78451 76743 76086 75393 73905 72897 71965 70363 70083 68757 68139 67444 66202 65963 65326 63718 63529 62408 61338 60928 59604 58946 58164 58328 57270 56285 55464 54903 54472 53299 52662 51944 50766 50240 49693 49364 48475 47615 47257 47106 45761 45118 45139 45333 44371 43000 43060 41911 41634 40649 40163 39603 39355 38520 38492 37377 36908 36234 35704 35117 35432 33497 33005 32564 32037 32007 31266 30215 29847 29641 29219 28822 28390 27614 27635 26908 26785 26496 26404 26117 26126 25605 25279 25247 24553 23883 23574 23359 23002 22480 22393 24234 21918 21437 21824 21135 23627 20449 20213 19813 19731 19435 19186 18625 18246 18392 17743 17472 17058 17094 16875 16643 16262 16120 15634 15743 15640 15116 14921 14821 14507 14439 14060 13960 14368 13861 13649 13547 13626 13155 13144 12882 13186 12812 12754 12402 11636 11395 11202 10936 10933 10866 10544 10712 10469 10636 10383 10025 9634 9638 9439 9210 9258 9130 9046 8874 8772 8669 8510 8152 8221 7937 8056 7961 7730 7590 7757 7434 7432 7403 7102 7009 7063 6890 6868 6844 6574 6297 6490 6131 6083 5939 5933 5835 5745 5743 5586 5575 5530 5520 5213 5378 5224 5307 5084 5044 5009 4816 4844 4686 4639 4594 4565 4541 4526 4369 4307 4402 4262 4233 4277 4141 4155 4051 3936 3894 3857 3805 3671 3674 3557 3552 3615 3548 3492 3593 3474 3360 3390 3237 3292 3265 3251 3239 3124 3188 3053 2943 2949 2902 2871 2969 2827 2918 2878 2887 2853 2757 2734 2655 2523 2611 2553 2609 2535 2488 2516 2461 2374 2373 2317 2307 2282 2316 2284 2206 2242 2199 2235 2285 2222 2270 2112 2158 2154 2009 2124 2170 2056 2190 2079 1965 2070 2075 2075 2163 2072 2218 2045 1953 2050 1907 1823 1886 1816 1785 1866 1934 1881 1914 1759 1820 1748 1846 1813 1549 1643 1575 1600 1534 1590 1534 1678 1761 1719 1713 1757 1603 1582 1576 1539 1557 1402 1575 1487 1375 1386 1392 1424 1348 1348 1389 1421 1509 1403 1352 1385 1370 1400 1404 1183 1207 1199 1214 1186 1177 1164 1215 1186 1201 1121 1088 1111 1076 1075 1007 1053 1042 1058 1037 1011 985 1075 1008 995 934 928 992 993 982 940 950 967 948 883 949 946 942 899 971 908 919 906 917 851 836 802 858 749 830 779 835 831 855 823 875 849 818 747 725 774 763 769 791 840 792 779 797 797 762 755 702 709 682 733 704 725 670 664 625 664 647 625 671 651 667 641 695 663 627 694 710 650 649 623 663 642 666 623 618 626 682 608 625 691 635 646 685 626 647 633 601 603 580 543 573 603 636 673 635 628 643 630 670 644 632 570 608 631 626 650 714 679 697 782 923 919 840 857 904 673 740 771 871 705 682 900 724 728 671 698 820 715 623 559 603 602 619 558 482 503 522 469 474 506 498 524 535 482 553 578 613 530 603 581 572 561 509 509 505 473 513 544 516 518 492 480 554 448 444 460 475 434 415 397 425 506 439 482 438 501 454 435 463 490 413 376 409 522 409 411 408 393 429 412 379 402 395 425 410 386 410 405 360 340 448 398 408 397 407 431 399 410 414 408 388 408 420 396 375 402 421 436 377 392 378 380 412 365 336 374 368 374 363 321 369 353 325 308 278 336 265 281 290 269 268 302 305 335 308 331 309 305 343 320 319 342 338 327 378 352 375 344 344 350 302 281 273 305 281 284 293 303 279 270 286 294 241 278 282 241 274 247 251 269 266 262 267 287 244 227 247 250 212 256 316 250 255 286 295 589 300 253 258 244 230 239 263 243 245 252 253 201 229 273 212 249 205 214 203 177 196 191 205 198 168 181 233 226 183 181 204 178 177 222 181 189 204 211 204 184 194 152 193 193 167 164 147 184 170 145 154 157 158 152 163 152 164 171 161 195 211 166 154 177 194 158 172 186 193 148 167 160 210 161 180 198 166 184 189 182 204 156 186 154 163 162 163 179 186 125 134 157 154 146 128 122 136 154 131 145 135 149 140 126 136 152 120 134 145 177 156 134 119 122 151 140 127 128 132 131 130 103 109 112 131 155 150 178 141 142 167 136 118 137 160 156 180 159 180 131 147 161 144 137 164 125 131 128 138 144 119 132 136 134 138 148 139 113 134 119 126 121 118 132 122 116 120 116 126 122 142 125 117 134 141 131 130 104 107 119 110 132 107 91 106 122 97 85 113 103 120 95 86 116 126 109 91 97 116 128 126 111 116 130 114 103 124 103 125 103 124 118 118 113 121 96 98 113 116 92 89 99 90 85 95 91 95 88 104 80 72 94 90 101 104 93 114 105 116 113 117 105 94 136 78 131 117 111 115 112 117 101 89 102 118 106 100 116 98 105 91 113 114 109 105 106 109 103 110 91 93 94 99 87 92 98 90 98 88 87 78 107 74 62 64 78 70 60 72 58 77 67 80 65 57 72 64 61 73 55 82 71 67 67 51 64 55 56 52 56 65 59 55 31 54 49 58 47 50 57 66 53 69 65 73 72 69 58 64 58 54 57 62 59 75 51 54 48 78 60 63 52 60 60 47 50 44 64 55 70 50 58 50 61 72 53 50 47 68 68 57 60 66 56 60 67 50 43 50 54 66 56 49 59 54 57 51 63 57 67 58 52 48 56 45 41 56 59 49 51 54 49 39 33 46 57 45 54 56 59 58 47 41 37 34 41 27 36 35 39 24 28 26 37 44 40 32 25 40 43 53 43 37 39 45 39 38 40 32 38 30 38 39 53 41 32 34 34 30 47 36 32 39 49 30 29 41 27 28 26 24 25 26 30 33 38 28 34 22 36 42 26 28 31 30 38 25 52 39 32 40 32 33 37 46 40 38 48 27 36 45 41 39 42 43 41 54 57 50 78 48 52 57 60 60 76 52 60 64 46 48 59 63 49 54 43 47 46 44 47 48 45 49 48 48 47 66 49 50 41 66 66 49 43 53 28 41 50 49 36 41 50 38 45 32 34 30 35 37 27 29 25 37 35 39 42 25 30 25 44 36 33 36 26 26 19 27 30 27 33 25 25 23 16 25 20 21 16 28 21 25 12 30 29 29 20 22 24 24 24 21 29 37 32 39 26 24 29 35 30 31 16 31 32 15 23 20 17 28 20 38 17 28 37 36 21 20 20 17 20 25 31 31 22 27 28 33 37 27 26 20 11 19 22 18 24 27 21 25 16 16 12 20 19 20 14 19 22 14 21 16 19 16 19 18 33 26 21 34 18 11 16 19 14 25 17 16 14 17 19 19 18 19 18 14 17 16 14 21 21 23 16 27 27 31 26 18 30 20 26 27 32 35 23 24 23 19 30 24 23 30 19 30 26 24 29 22 26 24 47 27 14 15 11 21 24 15 31 32 29 29 34 53 49 42 37 28 40 28 27 34 43 9 13 20 19 13 22 23 23 12 16 13 22 20 34 17 10 11 21 20 23 22 20 20 22 15 14 19 19 12 20 30 11 20 21 117 152 145 157 164 112 116 155 47 21 16 14 10 14 24 16 19 8 13 15 17 10 15 19 18 14 12 21 11 30 15 23 22 22 14 31 17 33 22 31 32 23 24 17 18 14 15 17 17 11 11 17 16 19 25 25 14 24 15 15 16 12 15 12 21 9 15 24 17 16 11 20 12 17 15 16 9 14 11 24 15 13 14 17 8 10 17 9 12 7 13 13 13 14 10 14 13 10 11 13 10 14 10 9 15 9 15 13 7 6 11 12 10 15 7 15 10 8 8 7 9 5 10 10 7 13 13 11 8 6 9 10 11 10 9 13 11 13 7 8 5 9 14 11 7 11 8 12 10 10 11 8 10 6 12 9 15 9 11 10 9 9 14 10 10 11 12 11 10 22 19 15 11 16 14 22 12 17 8 9 13 14 9 16 15 17 14 15 13 16 17 23 23 8 20 11 12 9 9 12 18 12 15 12 14 6 13 13 18 15 15 19 9 8 6 16 9 11 17 18 15 11 15 11 14 11 15 10 21 10 10 10 11 13 12 10 9 16 11 13 12 13 10 9 6 14 18 13 10 18 10 18 13 12 8 9 10 8 4 7 4 10 6 12 8 11 13 6 11 7 2 9 12 9 8 16 11 10 6 8 8 8 14 7 9 9 7 6 15 8 16 20 10 17 13 12 7 8 10 14 10 13 10 9 7 5 2 13 5 7 8 12 11 15 8 12 12 15 11 10 14 7 9 
];
B = [
0 0 0
 277290 57688 219602
 131928 28379 103549
 454379 107190 347189
 296292 64578 231714
 177483 38315 139168
 448866 109726 339140
 364466 83652 280814
 207241 45957 161284
 621641 150496 471145
 654023 149274 504749
 118909 26006 92903
 1872321 450803 1421518
 250637 60673 189964
 80720 19226 61494
 422608 121137 301471
 137341 38462 98879
 42840 11047 31793
 469079 135086 333993
 39005 9844 29161
 40837 10911 29926
 9915 2761 7154
 215 49 166
 9327 2635 6692
 698834 210062 488772
 46548 12357 34191
 60481 17124 43357
 726189 222575 503614
 42701 12569 30132
 90928 26894 64034
 1154888 336773 818115
 85499 25894 59605
 151277 45884 105393
 815880 261627 554253
 539057 172540 366517
 890789 286673 604116
 1654011 533718 1120293
 1384318 436447 947871
 829452 263140 566312
 1926486 637009 1289477
 791168 250134 541034
 54519 17338 37181
 1790297 596103 1194194
 29157 9436 19721
 51432 16538 34894
 2429034 824112 1604922
 53460 17317 36143
 631047 201459 429588
 3260613 1154452 2106161
 622334 200720 421614
 22 12 10
 21817428 7927308 13890120
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
46 125 0 2
22 11 0 0
52 16 0 0
80 20 0 1
68 22 1 1
70 30 36 6
145 43 68 7
428 53 104 21
1605 63 113 51
5308 88 171 79
11935 111 235 115
25770 172 288 180
52609 233 422 280
111922 347 569 460
225028 484 810 673
446760 922 1138 1120
727971 1859 1774 1715
846878 3664 2530 2553
709312 6085 3624 3540
438063 8527 4612 4657
198191 10310 5614 5692
53401 10876 6293 6392
13163 9481 6653 6673
10032 8617 7011 7064
9497 8806 7447 7346
9503 9168 7469 7779
9697 8205 7875 7847
9769 8411 8427 8298
10380 9017 9216 9075
10550 9621 9610 9779
11180 10115 10494 10723
12071 11060 11230 11333
12968 12155 12186 12194
14277 13563 13489 13500
15459 14953 14902 14911
17106 16726 17018 16721
19126 18616 18836 18602
21540 21136 21132 21323
24026 23804 24204 23718
27240 27023 27098 27163
30842 30650 31049 30560
35659 35461 35000 35260
40144 40046 40234 40244
45500 45797 45512 45737
51936 52105 52100 51744
59133 59402 59029 59518
66446 66903 66704 66129
73774 74287 74247 74050
81920 82284 82943 82937
91280 90881 90941 90667
99292 99337 99796 99453
106616 106720 106883 106331
114537 113396 113880 113395
120938 120515 121312 120285
129276 128145 129400 128570
136092 135996 135845 135827
145965 146638 145759 145928
155251 155774 154591 155738
165681 165420 166578 164742
174562 174259 175326 174167
183987 184450 183859 182663
186151 185350 185822 185762
178864 178053 179142 177635
155343 155151 155456 154976
114743 115430 115079 113836
62806 62995 63231 62598
25966 27110 27393 25671
14360 14194 14865 13597
11517 11302 11121 10832
10049 10257 11483 9497
7118 7251 7016 7495
4755 4182 4185 4889
347 318 309 299
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
