A = [
502846 433330 2128724 497439 445692 440843 428518 435234 430128 410542 410815 414311 410813 406795 408657 405876 402670 402933 398507 395462 395590 393797 395369 414476 436536 583156 597375 615631 756757 755579 751041 754257 758814 753489 750510 745853 732164 724697 717848 707215 700597 699146 690501 688177 685608 674512 669585 663333 649637 642741 638297 630490 627486 623871 615671 613420 606135 595010 588256 582691 573322 568089 566575 557374 554486 550547 542537 537869 533264 525016 518169 514586 506962 502203 498354 492599 489139 482496 476877 470420 466208 457629 454446 451084 444989 441611 438910 432701 427607 422379 416469 412431 407035 402527 397602 395905 389648 385661 382603 377285 372390 367291 362889 358521 355141 350884 346970 344956 340210 336740 331336 326494 322673 319525 314960 311919 309622 305504 302261 299536 294729 290839 286666 282530 279772 276867 274090 269889 267443 264821 261075 257714 254181 251910 249144 245377 242101 240735 237109 233879 230922 227457 225052 223080 219310 217430 214863 211950 208505 207163 203839 202014 199196 195842 193360 191069 187626 186988 184662 182271 180375 177401 175446 173131 171016 167864 166397 163836 162566 159404 158696 156543 154376 152438 149417 147725 145979 143754 142352 140593 138318 136526 135223 133263 131533 129702 127938 126396 124552 122980 122049 119741 117928 116943 116079 113375 112276 110581 109287 107656 106292 105552 104382 102489 100369 99859 98623 96213 96028 94889 92612 92227 90821 89022 88438 87466 86031 84700 83593 82330 81373 80310 79316 78508 77080 75899 74862 74178 73237 72174 71333 70202 69199 68610 67384 66994 66264 64827 64578 63319 62269 61570 61289 59525 59349 58453 57743 56710 55891 55190 54345 53858 52854 52584 51933 50905 50438 49925 48814 47822 47241 47205 46032 45530 44836 44581 44015 43091 42469 41915 41505 40845 40062 39635 39186 38448 37971 37567 37119 36795 36023 35397 34970 34211 33960 33708 33534 32812 32103 31700 31399 30833 30696 30048 29477 29124 28840 28604 28009 27742 27289 26876 26553 26021 25891 25351 25272 24458 24401 23902 23832 23721 23184 22691 22567 22331 21557 21392 21127 20879 20698 20295 20013 19785 19560 19280 18828 18705 18077 18229 17957 17671 17397 17223 16765 16392 16327 16290 16211 15769 15579 15026 15003 14673 14686 14472 14116 13868 13617 13623 13282 13297 12916 12624 12626 12393 12565 12165 11901 11615 11295 11336 11023 10854 10744 10692 10674 10509 10231 10078 9824 9709 9604 9602 9273 9196 8931 8944 8783 8658 8601 8357 8195 8146 7929 7966 7844 7750 7474 7455 7425 7173 7244 6939 6954 6931 6622 6801 6516 6443 6348 6213 6283 6216 6054 5776 5824 5641 5768 5565 5424 5525 5425 5396 5122 5076 5034 5013 4878 4907 4784 4737 4688 4673 4300 4541 4408 4324 4261 4304 4177 4151 4095 3916 3891 3872 3860 3860 3653 3779 3669 3509 3601 3489 3444 3348 3299 3196 3210 3170 3034 3097 3024 2954 2995 2995 2845 2822 2758 2723 2761 2640 2585 2535 2491 2447 2414 2350 2372 2382 2387 2294 2228 2188 2153 2140 2115 2150 2000 2062 2064 1945 1858 1914 1884 1853 1863 1840 1866 1813 1679 1641 1719 1676 1680 1675 1538 1569 1548 1541 1449 1470 1467 1401 1415 1351 1398 1310 1243 1226 1260 1316 1287 1242 1157 1220 1157 1137 1106 1130 1094 1089 1092 1055 1076 1037 1000 993 962 953 1004 996 978 913 890 874 883 867 833 815 771 853 769 760 793 838 786 706 785 770 781 689 697 715 676 714 710 699 677 670 709 688 610 597 609 609 630 598 599 575 573 562 553 540 518 498 527 539 454 499 477 503 497 455 470 444 394 438 445 445 406 393 425 389 428 385 370 383 367 409 383 403 372 421 408 396 411 367 366 390 413 388 403 409 404 409 349 418 347 368 432 353 368 350 342 304 355 365 347 335 278 324 269 296 324 287 299 273 306 285 307 301 278 296 289 257 221 238 233 226 229 254 206 217 247 228 227 221 237 210 227 212 216 192 229 241 199 206 249 195 225 155 192 210 221 197 191 189 195 174 172 186 194 177 210 194 204 175 177 209 193 181 196 192 243 190 171 183 202 185 189 157 169 171 182 156 149 188 134 117 131 133 148 170 158 169 174 145 138 143 131 128 129 131 135 170 144 143 140 153 167 138 147 115 125 114 129 123 129 111 95 99 114 111 104 96 100 94 132 104 104 89 107 109 106 108 95 106 98 103 85 100 84 97 105 83 88 128 93 110 114 110 92 108 118 98 103 89 95 100 101 83 89 111 82 90 68 88 109 98 93 102 102 123 107 93 96 117 105 99 104 100 116 96 120 126 87 116 93 106 92 92 90 100 102 122 111 109 91 106 103 124 97 78 91 87 87 94 82 100 99 82 105 78 93 89 83 73 69 80 98 101 94 102 92 77 77 100 70 89 82 89 84 73 88 98 100 98 114 106 118 86 106 94 94 110 83 106 119 94 86 108 88 87 107 92 94 92 99 86 102 101 77 90 95 78 104 110 95 109 80 81 90 81 80 87 92 68 83 73 86 91 72 104 83 86 100 80 86 87 92 88 91 77 95 89 75 74 74 97 72 71 76 69 65 67 72 90 82 69 65 73 68 61 88 60 75 67 78 72 91 55 45 45 47 56 51 62 44 44 47 35 42 37 42 43 50 28 47 33 25 43 38 35 45 29 31 41 28 24 30 51 38 41 54 47 35 34 49 36 39 33 41 35 34 35 34 22 23 27 24 37 33 32 31 17 16 28 18 31 22 31 19 25 32 25 26 35 23 23 29 17 21 15 26 23 28 29 24 21 36 30 14 32 24 23 21 19 20 24 25 19 33 12 23 24 23 26 22 23 25 28 31 37 28 29 28 37 14 12 31 20 25 23 30 26 35 26 37 31 25 22 19 28 18 22 23 18 17 34 29 24 18 22 19 16 11 22 15 9 24 16 17 22 29 18 16 23 18 14 18 23 23 35 16 24 16 12 19 20 24 12 22 28 16 16 22 19 28 22 11 31 19 20 28 18 22 25 24 22 17 20 18 27 30 19 23 25 27 18 23 16 14 12 13 12 16 10 11 16 19 19 17 23 19 20 21 23 17 14 12 20 13 16 8 19 20 17 19 19 17 20 22 13 20 16 13 18 14 18 11 9 20 13 20 10 11 23 10 15 16 18 11 14 19 11 11 16 14 12 9 17 9 13 12 10 10 10 12 15 17 9 12 18 11 11 7 8 8 11 11 10 11 10 7 11 5 12 17 12 7 10 18 8 10 10 15 12 13 8 14 6 15 9 18 3 14 17 11 12 20 8 12 10 9 12 12 6 12 7 14 18 9 17 7 14 9 8 11 7 11 14 10 7 10 5 16 12 14 16 11 22 18 10 16 7 10 12 13 14 11 10 13 10 8 14 9 2 9 14 6 7 9 11 8 6 12 7 11 7 12 10 13 10 8 9 9 9 7 18 13 8 12 14 13 9 7 8 13 12 10 9 2 8 6 7 3 8 7 6 6 11 13 7 14 10 7 5 3 4 8 8 9 12 14 10 11 15 12 17 9 10 17 7 7 6 10 9 11 8 12 7 11 6 11 10 6 7 10 9 5 8 10 14 12 13 6 7 9 7 8 11 8 10 8 13 20 20 15 6 10 6 7 10 8 6 9 12 7 7 9 4 6 7 4 4 4 6 5 5 8 8 2 14 8 10 10 6 4 5 5 4 8 3 3 11 8 15 11 11 4 7 5 5 6 5 2 6 10 3 5 1 2 3 3 7 5 5 6 6 6 7 5 3 4 0 6 7 8 6 5 5 3 6 5 6 4 6 4 6 6 9 4 7 2 6 7 7 5 6 3 7 8 8 3 0 3 8 4 5 2 4 5 3 3 0 4 2 1 3 2 4 3 2 3 5 6 3 3 2 3 5 6 2 3 5 1 3 5 4 1 5 8 2 2 3 6 3 2 4 3 6 6 6 2 4 4 4 4 2 2 2 4 3 1 2 2 5 4 3 5 3 0 6 2 3 3 4 4 6 4 9 2 7 3 7 2 8 3 7 4 3 1 6 8 4 5 5 4 5 2 1 4 6 3 8 5 4 6 6 10 4 7 3 11 5 7 5 5 2 1 1 4 5 3 4 2 4 2 4 2 4 0 5 2 1 2 8 7 2 11 4 8 2 8 8 5 5 7 3 1 3 1 3 1 5 5 5 5 4 3 2 2 2 2 1 5 4 3 3 4 2 2 4 4 1 3 7 3 1 2 3 2 0 3 2 2 2 1 2 1 2 3 0 0 2 3 3 2 1 4 3 1 4 2 4 2 1 1 1 5 2 2 2 1 2 1 1 3 3 2 2 2 2 0 2 3 0 1 1 2 0 2 3 1 1 0 4 0 3 5 4 5 2 2 4 4 3 6 4 1 0 2 3 6 1 7 5 7 2 0 2 2 2 2 0 3 2 3 3 3 1 2 2 3 2 1 5 2 3 1 2 2 0 0 2 1 1 2 1 3 0 3 1 3 2 2 2 1 2 3 4 6 3 3 1 2 1 1 5 4 2 2 1 0 5 4 1 0 3 5 3 1 2 3 1 1 2 3 3 0 2 5 1 3 2 0 1 1 1 0 2 0 2 1 2 1 1 2 1 2 1 0 6 0 1 1 1 5 3 3 0 2 2 2 3 2 1 1 0 4 1 1 1 0 0 0 0 0 0 1 2 2 3 1 3 0 2 0 1 1 1 4 3 1 4 1 1 2 1 1 2 3 0 0 2 2 2 2 2 1 0 0 1 0 0 0 0 2 1 3 0 1 3 5 1 3 2 3 7 4 3 4 5 1 3 0 0 0 1 3 1 1 0 3 1 2 1 1 1 1 2 0 1 2 1 4 1 1 1 2 0 4 3 3 1 1 2 0 3 1 1 2 0 0 0 2 4 1 0 0 1 0 1 1 0 0 0 0 3 0 3 0 1 0 2 1 1 1 0 1 0 2 0 1 2 3 0 2 1 1 2 2 1 2 1 2 2 4 5 
];
B = [
0 0 0
 185959 43072 142887
 85180 18754 66426
 254828 63392 191436
 99547 22687 76860
 95418 21848 73570
 124019 28698 95321
 168249 40770 127479
 80182 17472 62710
 243662 61962 181700
 103410 24411 78999
 106291 24692 81599
 130107 31185 98922
 210980 51474 159506
 97781 22407 75374
 303744 77348 226396
 143366 33224 110142
 167279 38122 129157
 190633 44580 146053
 323303 75850 247453
 262575 59060 203515
 402543 100166 302377
 394437 90178 304259
 308907 71583 237324
 513456 119581 393875
 760940 181660 579280
 63017 15007 48010
 1631686 404444 1227242
 37208 9853 27355
 54287 13870 40417
 58430 15573 42857
 112633 29794 82839
 26827 6758 20069
 368618 99295 269323
 30004 7776 22228
 47419 12404 35015
 48039 12689 35350
 94121 25006 69115
 6678 1617 5061
 408162 111942 296220
 17 8 9
 531 186 345
 3564 1005 2559
 37241 10191 27050
 4573 1236 3337
 4363 1150 3213
 6763 1715 5048
 15043 3937 11106
 681511 185652 495859
 281 92 189
 5345 1551 3794
 4539 1322 3217
 6426 1717 4709
 18161 4824 13337
 711177 196359 514818
 7780 2341 5439
 7123 1989 5134
 5687 1918 3769
 147182 46532 100650
 114781 35816 78965
 32555668 11059104 21496564
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
16 164 5 4
14 27 1 1
16 49 1 1
29 51 1 3
29 65 10 4
34 80 228 21
155 104 625 127
646 146 812 264
3207 205 1227 498
11317 320 1776 910
28445 382 2340 1486
69431 614 3457 2258
144256 858 4863 3491
269838 1407 6744 5493
419237 2355 9480 8011
596476 3778 13345 12091
723368 5943 18206 17189
781172 8866 24265 23431
758987 13373 31878 31081
540623 19443 40813 40293
320710 27425 49827 50167
135127 37230 59993 61387
86580 49918 71383 71363
93824 64430 82732 82935
105759 79736 94402 94678
117875 95843 107914 108186
130273 111246 119486 120015
141256 123150 131362 131859
149172 132171 139958 140281
151720 137955 144733 144305
149187 138735 143065 144041
143486 135142 139000 138993
134447 128815 131605 131302
123476 120073 121029 121201
113007 110473 111350 111456
101631 100075 100744 100433
90080 88766 89158 89485
78065 77527 77711 77916
66916 65776 66052 66482
54701 54679 54634 54613
43679 43502 43509 43344
32778 32792 33012 32665
23059 23007 23375 23340
15646 15425 15464 15406
9262 9595 9635 9276
5198 4970 4979 5152
2332 2448 2343 2438
918 922 917 898
339 319 307 363
64 65 70 79
1 2 1 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
