A = [
5331464 4872212 48563204 2106619 1311142 1216623 1103072 904756 846497 769388 745356 711773 704273 685730 659933 644281 630618 631102 627101 604315 598029 605169 593220 582293 577173 594596 588945 579608 587340 535673 531323 525269 479551 468334 459540 459209 456970 454048 453431 461994 453236 458711 460263 458696 467330 460096 455759 473959 462675 458399 462617 445466 448965 448137 433550 425975 430687 437402 420968 416026 423421 417574 411873 407462 410017 416658 397349 409399 403000 382311 381913 413942 375467 375207 377449 376845 373586 376385 370158 366825 364780 364253 356988 355596 357014 349059 343348 333094 325858 324973 321225 318935 318643 315625 314815 313091 312348 311446 307477 306358 304702 304210 301523 300441 299780 299156 299293 296003 295973 293250 292906 291972 291297 289951 291050 288926 301838 303004 302584 315755 317455 320097 319747 322888 322649 321353 321296 319625 318541 316756 314472 313559 311508 310692 307835 307498 306738 302473 302465 300671 298277 296804 295780 295067 293026 290520 290415 288538 285023 282792 277591 277524 275033 274284 271157 268614 266026 265454 263873 262034 258780 255917 254111 253179 250060 248751 245743 244588 242647 239286 237445 235293 234193 232105 230428 228650 227160 225221 224221 221341 218580 216507 215481 212423 210706 208892 206650 205147 203159 202884 200196 199217 195553 193471 190982 191090 188622 185240 184067 182621 181842 177718 177288 176063 174436 171706 168666 168194 164936 162779 159596 157896 155894 154700 155223 151414 149725 147979 145510 144863 142765 140844 139008 136877 134373 131931 130368 127755 126781 125054 122649 120998 118445 116714 114224 113187 111238 110524 108772 106131 105448 104210 102176 100706 99710 98291 96132 95497 94667 92812 90694 90388 89439 87429 86257 84149 83533 82270 80436 78933 78209 77345 76435 74738 73808 73084 71407 70519 69828 68875 67202 66512 65534 64749 63241 62111 61855 60258 60077 59329 58287 56698 56452 55132 54703 54587 53001 52055 51644 50153 49862 48420 48045 47154 46379 45956 44880 44354 43725 42482 41917 41399 40293 39873 38915 38516 37768 37478 36601 35805 35647 35037 34103 33653 33104 32841 32075 31673 30862 30738 30022 29604 29684 28399 28107 27662 26957 26603 26334 26214 25605 25377 24480 24129 23699 23536 22889 22169 22014 21953 21511 21046 20897 20419 20236 20227 19554 19053 18664 18859 17945 17912 17766 17176 17275 16736 16630 15818 15934 15712 15508 15139 15028 14364 14098 13791 13963 13622 13282 13103 12740 12342 12437 12550 12081 11598 11262 11237 10984 10648 10583 10434 10485 10468 10079 9536 9534 9265 9533 8965 8876 8867 8623 8582 8433 8148 7960 7717 7726 7819 7438 7460 7261 7134 7043 6903 6740 6657 6798 6458 6310 6216 5930 6028 5987 5718 5636 5664 5451 5506 5410 5185 4964 5044 4737 4768 4787 4687 4404 4518 4545 4346 4387 4174 4228 4066 4119 3972 3841 3745 3686 3659 3644 3582 4691 3367 3632 3392 3416 3265 3178 3108 3128 3010 2879 2870 2826 2852 2758 2751 2502 2607 2432 2485 2476 2521 2388 2067 2288 2313 2212 2220 2283 2124 2070 2092 1980 1973 2068 1945 1848 1719 1798 1744 1814 1861 1727 1734 1631 1629 1667 1557 1599 1500 1469 1487 1440 1377 1461 1364 1250 1354 1300 1276 1228 1210 1228 1187 1228 1091 1078 1193 1060 1044 1069 1055 1027 1021 1068 932 942 940 902 1001 971 982 939 892 794 800 829 853 791 821 721 770 798 759 796 733 778 665 786 697 657 707 603 634 610 571 584 617 557 563 576 529 477 501 639 486 477 509 511 556 459 468 496 460 552 466 417 431 446 545 441 439 413 396 408 394 400 431 388 866 321 396 384 367 357 386 306 329 319 313 312 305 323 287 293 264 261 315 259 271 274 294 260 232 259 273 232 286 228 252 269 255 251 243 257 237 235 235 269 248 229 222 204 233 258 209 214 239 201 188 216 195 197 233 191 212 171 216 183 193 164 211 161 197 170 162 163 215 187 183 174 142 155 184 177 169 156 153 149 158 152 174 148 153 157 142 158 129 167 153 161 120 125 125 152 154 124 159 160 161 126 121 108 154 134 184 118 123 135 115 139 125 114 121 138 109 128 149 125 140 147 114 110 122 113 98 135 114 92 97 114 107 112 96 117 117 99 103 112 120 142 106 110 100 147 138 143 109 132 134 179 139 101 159 135 138 137 134 101 134 109 114 108 107 128 114 140 110 126 107 113 123 106 91 101 129 99 111 111 152 82 82 99 76 114 79 94 158 70 96 81 119 84 72 66 73 79 90 83 79 92 87 76 73 80 80 94 58 94 68 94 81 74 86 67 89 87 80 96 75 157 237 97 93 94 111 95 89 78 71 63 70 106 83 78 84 82 103 94 74 77 85 83 83 86 63 71 83 79 60 100 79 81 51 51 62 76 66 44 58 65 79 53 57 82 57 54 55 81 58 57 59 61 68 64 73 110 48 55 63 63 58 54 54 61 52 66 65 50 56 58 49 59 48 58 66 55 78 44 52 48 49 45 52 52 54 58 58 49 62 49 55 59 63 52 66 56 66 60 62 46 61 44 59 50 35 66 54 45 31 53 47 47 54 54 32 46 49 57 57 52 60 49 38 45 46 44 52 38 40 50 56 58 44 57 36 44 60 51 39 62 34 72 57 30 47 43 52 36 49 48 51 53 41 49 65 50 55 34 52 54 47 49 47 53 52 28 36 42 26 56 44 31 29 44 43 33 43 39 49 44 44 36 36 75 41 43 39 50 119 55 60 61 53 69 61 56 39 54 49 55 50 84 63 61 72 67 67 58 75 61 58 52 57 62 69 53 78 49 88 69 75 45 49 55 64 49 62 60 51 71 54 67 66 75 64 53 66 63 36 60 62 50 69 70 76 73 83 271 97 75 100 78 108 109 107 100 108 125 98 134 95 88 337 84 126 98 79 353 90 67 87 65 80 82 66 85 79 62 82 96 67 74 80 69 57 77 76 96 96 73 68 82 73 66 71 78 91 102 85 77 133 111 114 115 110 108 115 109 124 101 600 201 148 124 135 73 79 73 55 46 101 32 44 51 42 34 38 32 29 28 44 43 32 34 39 27 40 45 34 35 27 36 25 18 17 29 17 37 14 28 39 35 575 54 48 58 75 99 99 102 98 100 46 46 42 35 46 46 38 39 39 40 52 41 30 22 25 38 32 47 32 28 35 31 26 14 32 34 20 33 17 31 28 35 34 40 100 35 28 50 55 225 45 34 34 43 159 49 44 38 56 408 36 41 31 43 44 29 36 44 44 72 35 36 53 39 663 19 21 25 50 48 36 37 28 23 95 27 22 50 42 47 30 42 28 24 39 27 42 52 31 23 60 25 29 30 32 34 28 46 49 45 30 37 40 46 34 44 24 32 23 31 31 52 43 39 36 65 55 61 45 40 29 44 38 35 35 46 51 48 53 64 48 51 43 43 60 52 50 55 47 68 68 67 72 61 80 63 77 67 83 87 56 71 70 726 92 109 102 147 1533 113 89 89 62 1669 46 64 36 48 280 25 38 34 36 60 22 33 15 12 34 15 21 8 12 61 25 5 11 33 12 9 11 11 10 9 14 7 5 19 13 15 11 12 16 11 5 40 11 7 16 11 11 17 12 5 11 16 25 3 7 11 11 13 4 9 14 9 31 15 8 14 21 13 25 13 11 11 22 7 20 15 12 25 18 15 20 26 19 673 42 12 23 25 22 18 11 8 11 20 8 15 3 16 9 7 10 17 11 7 13 12 10 6 17 6 16 11 5 5 8 5 2 5 9 9 6 8 6 5 7 7 6 8 16 10 9 6 8 9 9 9 9 12 5 5 7 11 13 12 6 9 6 6 3 11 6 10 6 16 11 8 13 12 2 26 8 17 11 9 14 6 11 9 28 29 14 9 9 15 16 19 13 2 10 20 7 9 12 10 13 15 13 5 41 58 66 66 66 64 42 78 89 94 64 72 69 86 78 92 74 82 167 121 87 83 69 77 80 90 25 15 8 10 32 22 15 15 18 22 21 24 19 24 26 5 18 26 18 39 19 23 15 27 21 24 24 16 44 23 22 28 26 23 25 34 15 21 13 25 31 24 20 24 26 19 26 6 5 6 9 9 13 21 18 11 16 11 12 4 16 10 7 9 11 10 6 16 16 7 9 9 11 16 8 3 7 3 8 8 18 9 8 8 9 16 6 13 1 3 10 9 7 11 25 10 7 9 15 4 11 7 4 10 11 16 5 5 6 7 8 8 1 10 3 1 5 7 7 3 7 6 4 9 4 2 4 11 2 10 5 13 5 6 7 7 4 2 6 2 2 0 5 2 3 1 2 5 4 2 4 2 6 3 4 3 8 3 8 3 8 5 17 1 7 10 17 4 3 4 5 5 2 4 3 4 6 3 2 6 2 6 8 4 2 7 4 7 1 14 3 8 9 5 7 65 2 7 2 7 3 4 2 1 6 19 3 1 4 1 0 4 2 2 4 2 9 1 3 2 2 2 4 1 4 3 2 2 0 3 2 1 5 0 6 4 6 3 2 3 1 1 3 14 39 6 2 4 9 4 6 3 4 2 1 8 6 9 4 6 7 8 6 2 3 3 2 2 16 3 3 3 5 4 7 2 9 3 10 3 3 3 7 4 4 6 7 11 8 2 3 6 5 9 0 3 3 6 2 7 0 6 8 6 3 12 6 7 6 9 3 4 10 1 3 8 3 3 6 3 9 5 12 6 5 2 2 4 3 10 7 3 14 13 9 14 6 19 15 9 10 14 14 17 13 23 6 19 14 16 16 14 11 10 19 11 16 15 22 12 10 16 17 19 15 20 19 8 14 12 15 14 15 21 20 21 10 10 16 10 19 10 11 18 12 24 29 19 22 23 13 11 26 25 26 19 18 15 18 8 12 12 10 28 16 13 12 1 0 3 1 7 5 4 3 3 9 11 2 2 2 6 5 1 0 2 4 2 4 3 0 7 1 6 0 7 5 3 4 1 3 1 2 1 0 1 3 1 0 2 3 4 3 4 2 
];
B = [
0 0 0
 353840 253196 100644
 1001300 859541 141759
 410168 327800 82368
 287188 239102 48086
 165530 134187 31343
 101694 81064 20630
 82289 64748 17541
 133597 113721 19876
 161742 135905 25837
 564048 525010 39038
 228643 198765 29878
 200828 178389 22439
 179706 161409 18297
 160275 143445 16830
 348925 328570 20355
 197290 179613 17677
 178743 161377 17366
 165275 150163 15112
 158696 142865 15831
 296013 277764 18249
 193668 176186 17482
 187891 170797 17094
 175162 157246 17916
 161128 144604 16524
 243313 224460 18853
 173501 156760 16741
 194589 176229 18360
 186308 169486 16822
 173619 156275 17344
 227458 209453 18005
 182761 165870 16891
 179527 162642 16885
 177293 161596 15697
 185850 166980 18870
 207104 190913 16191
 182282 166064 16218
 256341 223114 33227
 177374 162150 15224
 191819 173533 18286
 260332 231228 29104
 188595 171186 17409
 234633 206973 27660
 179463 164299 15164
 184945 167651 17294
 253808 226237 27571
 190522 173250 17272
 241838 214756 27082
 192673 176176 16497
 232278 206330 25948
 202185 185747 16438
 236165 210174 25991
 203052 185725 17327
 234545 209021 25524
 191905 175724 16181
 248702 221651 27051
 228515 204313 24202
 192812 178106 14706
 232393 208084 24309
 179298 167108 12190
 72412257 70931206 1481051
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 99 0 0
7 17 0 0
15 38 0 0
29 21 0 1
14 34 0 0
21 36 2 1
49 87 3 0
123 55 1 1
48234 72 5 1
491437 119 8 2
1210766 144 15 4
2552133 199 42 10
4877987 223 436 97
8674725 446 2008 758
13315545 544 2173 1040
15394217 1097 2248 1569
13175629 1501 3271 2817
9036888 2456 4901 4656
4638153 3936 7113 7285
1681484 5552 9458 9593
380538 7494 11313 11528
51889 9845 13421 13401
17889 12729 15887 16283
18923 16210 18177 18835
21035 19579 20877 21486
23940 23245 23466 23994
27602 26789 27036 27038
30287 30977 30105 30572
34155 34505 34133 34420
36463 37951 36872 37702
40720 41307 39502 40736
42442 45917 42897 43766
45289 48302 44684 47803
46482 49352 46566 48743
54123 49559 47137 47527
49582 50087 46841 47993
47211 53586 47575 49291
45489 47291 46128 45967
45343 46780 46308 46256
46172 45022 44780 47137
49521 44726 45680 44420
46011 44972 44805 44854
46599 50391 45203 45908
46640 46333 47900 46795
48250 47527 49494 50105
56317 50502 49381 48879
49652 49682 49488 50243
49820 49970 49833 49953
49452 49983 50153 51340
49567 49626 52127 49803
47863 47633 47847 48413
44916 45409 45528 46030
42119 42900 42381 42687
38797 39631 39447 41811
35128 36193 35951 35940
31971 32451 32087 32168
28563 29220 28843 29601
25789 26209 25823 26087
23210 23598 23436 23883
21165 21209 22907 21558
19763 19968 19569 20035
19034 19233 19392 19267
17370 19827 18042 17883
16389 16452 16457 16993
15724 15836 15763 15775
15477 15560 15608 15881
15424 15561 15333 15246
21071 32637 20986 16677
14915 15386 15246 15197
14851 14538 14732 14906
14186 14445 14504 14710
13864 14111 14616 14954
13402 13474 13609 13683
12467 12457 12564 12548
10902 10891 11310 11515
10261 10063 10006 10059
8481 8438 8394 8550
6312 6106 6073 6230
5182 5141 4795 4945
3761 3840 3824 3727
2200 2294 2255 2239
1485 1391 1563 1438
93 107 72 108
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
