A = [
295903 611708 824659 382298 710879 514436 498650 515692 523505 504247 503075 514901 496448 482734 492318 486431 479280 487115 485482 478271 481499 467769 460985 451583 435480 444944 448024 438406 437592 447490 437830 427097 429058 413934 411776 414301 409968 405288 412465 408608 402859 401372 397221 384658 383300 381321 376493 377639 375622 372164 375654 368761 358039 356669 348509 343202 350769 341840 338533 341045 336007 328252 328759 321308 313829 314129 311120 306949 305664 301860 296280 297841 290979 284153 284642 280605 274188 276036 273318 267232 268740 262170 256946 257436 252201 246479 248531 242253 240190 239298 235653 231363 232042 226237 222819 222822 218085 213829 216287 212976 209644 207691 204668 201683 200351 197089 193551 193119 190576 188207 187812 184434 181675 180749 177545 175811 175757 171827 168650 169723 166509 164210 162788 160704 157539 157723 155085 152304 151929 149616 147658 147255 144633 142640 142976 139341 138217 138048 134982 133437 133461 130995 128674 128852 126294 124424 124683 122257 120792 120495 118367 116862 115890 113718 112891 111682 110392 108895 108000 106653 105169 105315 102659 101794 100175 99974 97787 98078 97204 95813 94923 93230 91893 90847 90220 88744 88551 87066 86422 86020 84909 83362 83778 82267 80691 80850 79908 78403 78277 76444 76158 75827 74847 73691 73454 71927 71486 70937 70300 69569 69197 68913 67526 67895 66574 65167 64705 64923 63973 63664 63199 62155 61700 61419 60556 60650 59495 59137 58337 57827 57095 57528 56499 56180 55745 55054 54589 54137 53700 53186 53052 52286 52190 51579 51272 50571 50505 49919 50029 49482 49120 48472 47912 48150 47381 47166 46498 46311 45739 45761 45185 45241 44601 44425 43625 44138 43302 43408 42572 42104 42521 41119 41447 41220 40799 40723 40285 39796 39294 39787 39386 39084 38681 38371 37801 37667 37626 37188 37178 36768 36829 36039 35615 35996 35600 35284 34723 34769 34638 34143 34900 34051 33541 33653 33351 33128 33112 32406 32407 32363 32162 31880 32067 31583 31141 31049 30718 30605 30722 30423 29798 30052 30126 29375 29531 29023 28834 29095 28650 28562 28344 28230 28212 27685 27523 27249 27443 27620 26895 27034 26532 26890 26580 26361 26405 26214 26537 25882 26293 25404 25535 25432 24770 24984 24863 24773 24664 24665 24328 24205 23948 24068 23861 23614 23302 23447 23442 23338 22952 22943 22691 22559 22521 22393 22051 21880 22011 21822 22133 21686 21896 21329 21512 21411 21673 20977 21411 20731 20880 20473 20703 20537 20710 20283 19664 19853 19940 19856 19762 19927 19530 19348 19376 19321 19230 19144 19312 19049 18949 18637 18410 18496 18316 17881 18201 18208 17859 17922 17854 17996 17432 17688 17496 17349 17543 17116 16982 17135 16746 16888 16629 16685 16928 16541 16292 16443 16247 16217 16278 16215 15974 15954 15936 15930 15935 15671 15554 15506 15429 15091 15057 15320 15047 14958 14970 14706 14707 14442 14378 14758 14175 14206 14419 14031 14367 13932 14070 13788 14020 13624 13770 13366 13594 13364 13431 13395 13440 13385 13150 12916 13232 13160 12926 12954 12646 12731 12851 12656 12617 12539 12500 12522 12308 12108 12173 12079 12027 11910 11950 11860 11912 11809 11845 11673 11704 11760 11607 11593 11831 11571 11095 11298 11200 11264 11218 11009 11196 10764 10886 10726 10922 10460 10665 10650 10416 10746 10626 10573 10407 10459 10380 10163 10347 10204 10209 9933 10093 10071 9907 9705 9684 9836 9549 9704 9813 9704 9499 9601 9551 9363 9244 9320 9354 9259 9108 9270 9007 9190 9117 8941 8864 8975 8920 8870 8876 8961 8706 8571 8837 8738 8574 8537 8590 8517 8559 8617 8333 8418 8089 8290 8227 8002 8115 8058 7803 8014 7843 7807 7823 7761 7771 7722 7616 7863 7591 7894 7543 7557 7562 7507 7498 7425 7438 7161 7630 7308 7257 7116 7477 7477 7179 7109 7003 6953 6963 6986 6986 6771 6822 6910 6889 6805 6783 6581 6703 6428 6606 6571 6478 6580 6458 6250 6404 6458 6413 6407 6313 6421 6299 6305 6077 6229 6177 6165 6225 6071 6170 5876 5994 6005 5942 5960 5946 5772 5919 5718 5668 5694 5738 5502 5621 5467 5582 5594 5499 5408 5418 5433 5395 5508 5408 5244 5329 5499 5311 5328 5343 5379 5197 5256 5161 5232 5039 5146 5033 5112 5021 4998 5037 4889 5050 5003 4809 4929 4830 4861 4959 4731 4912 4786 4748 4526 4634 4746 4767 4778 4680 4761 4906 4720 4561 4505 4546 4579 4466 4455 4368 4496 4358 4440 4352 4538 4354 4270 4224 4352 4205 4250 4089 4151 4155 4188 4192 4171 4133 4091 4111 3899 4046 4031 4062 4061 3955 4016 3891 3986 3918 3858 3878 3830 3712 3813 3774 3670 3606 3587 3695 3569 3666 3614 3546 3640 3680 3505 3566 3477 3476 3497 3438 3421 3361 3554 3396 3308 3326 3395 3302 3265 3306 3329 3366 3376 3362 3339 3273 3264 3267 3215 3237 3168 3109 3062 3096 3167 3148 2952 2972 3106 3228 3095 3005 2965 2973 3026 3072 2990 2841 3003 2881 2833 2839 2888 2860 2900 2854 2787 2865 2848 2756 2853 2821 2882 2771 2776 2683 2731 2649 2726 2689 2734 2661 2641 2664 2587 2554 2663 2667 2538 2678 2644 2587 2627 2596 2652 2588 2550 2482 2477 2572 2402 2460 2476 2497 2431 2345 2338 2433 2370 2456 2396 2370 2470 2340 2183 2255 2355 2292 2308 2240 2350 2383 2333 2253 2339 2286 2295 2287 2238 2246 2395 2110 2266 2272 2276 2216 2291 2250 2113 2194 2154 2103 2068 2066 2078 2097 2111 1963 2156 2084 2055 2134 2088 2000 1962 1996 2011 1907 1873 1959 1954 1990 1931 1971 1826 1989 1922 2023 2015 1944 1867 1941 1922 1947 1780 1846 1784 1831 1838 1794 1814 1732 1897 1755 1809 1816 1792 1770 1816 1789 1764 1791 1793 1721 1753 1671 1687 1765 1729 1688 1645 1616 1604 1584 1652 1610 1575 1664 1666 1649 1576 1583 1616 1563 1511 1589 1483 1506 1565 1510 1506 1598 1494 1480 1498 1508 1476 1444 1475 1427 1390 1521 1492 1388 1525 1403 1399 1343 1394 1382 1376 1399 1498 1392 1463 1269 1390 1341 1267 1342 1261 1309 1219 1312 1297 1287 1273 1335 1259 1281 1246 1261 1264 1215 1212 1199 1295 1303 1229 1313 1363 1223 1241 1216 1140 1204 1196 1254 1234 1126 1116 1144 1210 1113 1257 1138 1116 1186 1177 1081 1128 1089 1106 1141 1121 1095 1115 1098 1087 1102 1035 1113 1082 1063 1105 1045 1068 984 1076 1049 1015 1001 1013 1036 1020 957 1009 952 975 949 990 961 1013 992 1001 922 985 919 1017 995 909 981 921 944 978 980 960 956 964 912 860 889 901 914 934 870 928 877 900 918 859 890 827 896 865 850 887 919 837 842 842 846 791 808 816 753 745 883 851 850 828 810 739 865 777 755 786 805 740 753 763 754 751 793 746 719 825 730 719 696 773 815 719 687 757 714 671 779 738 751 680 728 715 667 728 730 686 743 709 672 716 735 735 713 726 677 658 674 695 648 657 671 668 632 647 653 659 645 707 609 660 686 694 642 656 653 687 616 631 627 623 612 593 603 536 648 599 707 579 607 608 601 612 570 678 647 622 598 580 585 560 547 579 558 546 573 509 569 543 543 529 584 527 549 526 598 524 519 551 480 621 567 516 598 541 584 508 498 524 491 537 517 499 470 543 492 484 455 472 501 450 440 495 492 447 466 468 507 490 482 485 471 439 484 503 478 436 487 454 471 422 498 416 426 433 455 450 454 385 448 446 484 439 448 428 386 445 408 408 385 419 429 395 432 376 407 395 389 417 391 451 405 406 431 410 377 375 333 372 429 386 397 401 435 437 372 424 359 341 359 381 369 426 344 378 370 394 379 385 367 335 398 358 388 352 370 390 358 341 358 356 364 331 340 356 360 350 362 372 329 340 347 330 308 339 326 337 332 323 357 344 329 281 312 308 285 330 322 305 304 305 305 273 300 309 275 304 279 287 323 241 306 268 348 293 269 294 263 273 292 297 234 279 275 263 291 269 284 258 294 263 297 300 267 288 268 305 272 296 286 263 287 255 290 276 244 268 261 283 267 279 234 258 248 244 252 242 234 275 242 246 258 268 241 257 251 252 250 228 262 273 230 241 221 238 239 225 263 240 260 254 254 242 242 250 257 290 241 224 210 269 236 269 240 219 259 239 221 212 233 247 213 268 211 210 175 193 223 220 206 232 189 210 198 214 221 219 215 204 195 207 199 181 201 175 179 178 201 190 199 196 197 207 200 205 209 173 204 164 177 206 173 197 204 176 199 174 174 188 199 186 169 164 196 182 183 184 160 164 167 159 172 168 209 198 180 211 165 178 180 172 164 150 168 198 197 180 186 199 166 160 157 184 173 188 152 180 174 158 174 171 159 153 150 156 173 162 147 144 167 161 158 184 153 160 154 169 161 167 157 179 139 168 144 162 147 167 152 155 132 162 150 160 145 146 167 150 158 120 147 129 129 132 122 143 136 131 151 128 119 132 120 146 144 149 104 136 121 125 111 137 127 133 140 141 124 138 123 132 110 127 115 169 137 128 142 129 139 130 105 134 135 115 143 132 140 130 122 140 128 142 115 122 102 136 116 122 152 126 118 136 136 142 134 129 124 123 120 108 117 101 147 133 102 107 110 107 113 114 102 125 119 117 120 123 112 103 114 120 107 110 91 95 130 112 112 120 107 103 127 114 106 90 93 79 95 120 90 109 85 106 95 87 109 101 96 100 96 110 87 100 110 125 106 96 111 103 90 114 102 116 115 75 90 84 104 127 95 91 104 118 100 85 97 91 119 99 109 105 79 72 100 109 78 79 104 84 79 104 73 84 87 78 80 87 78 83 84 81 94 80 73 75 66 92 83 75 86 78 67 93 72 87 65 61 67 77 73 83 64 78 52 81 72 89 60 64 58 94 57 65 64 85 78 70 49 72 72 78 79 56 73 77 65 72 80 53 66 66 63 71 73 58 67 67 60 63 62 56 56 60 68 64 83 63 63 61 72 70 52 65 71 52 62 65 75 55 59 56 66 61 62 63 63 52 91 61 64 63 56 55 56 62 52 55 59 47 68 57 83 54 73 60 45 51 55 48 59 57 56 56 59 48 53 51 38 68 56 50 59 69 49 60 62 41 62 69 46 53 66 73 70 58 48 53 63 61 63 64 51 58 51 65 61 53 59 75 52 44 64 61 50 60 64 74 54 51 69 52 47 53 54 55 50 71 55 54 45 55 52 49 49 43 38 48 42 44 50 36 70 51 34 58 50 51 40 55 61 51 62 31 48 48 54 54 46 49 45 55 41 57 46 53 45 39 46 56 49 63 57 55 32 49 47 49 49 54 47 44 55 35 40 49 51 63 42 52 62 51 59 37 51 33 60 46 52 50 56 51 51 51 
];
B = [
0 0 0
 130373 51544 78829
 65271 25131 40140
 257434 125260 132174
 56998 21536 35462
 58620 23020 35600
 83746 33942 49804
 104920 48736 56184
 80367 32805 47562
 224064 118705 105359
 59178 25225 33953
 69399 29568 39831
 74636 34252 40384
 139721 68177 71544
 68772 30880 37892
 236649 132574 104075
 70405 34731 35674
 77726 38815 38911
 83762 42420 41342
 162899 85374 77525
 84461 46332 38129
 268863 152298 116565
 126817 68864 57953
 102009 55498 46511
 233656 121768 111888
 344125 195722 148403
 50948 24139 26809
 1168719 685813 482906
 18069 12053 6016
 40941 24243 16698
 30511 19514 10997
 58055 38744 19311
 19089 10813 8276
 215381 143080 72301
 16249 9998 6251
 38112 23180 14932
 27227 17456 9771
 53139 35246 17893
 6762 3232 3530
 250447 167051 83396
 49 34 15
 478 323 155
 4411 2380 2031
 37975 24228 13747
 4412 2670 1742
 3911 2349 1562
 7167 3904 3263
 15974 8607 7367
 423303 285046 138257
 476 307 169
 4870 3149 1721
 4087 2586 1501
 5841 3534 2307
 21749 12750 8999
 430005 297013 132992
 8117 5704 2413
 7467 5056 2411
 10623 8208 2415
 228106 160458 67648
 140047 101473 38574
 24054259 19380170 4674089
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
184 178 8 3
158 49 4 1
216 121 1 0
212 155 6 4
137 166 10 5
363 278 15 12
5230 410 176 147
33946 496 429 454
167233 831 1058 1055
519728 1276 2210 2201
1085268 1901 3564 3540
1551910 3131 5742 5641
1947281 4815 8478 8385
2522436 7242 13204 13146
2917954 11270 18369 18079
2445583 18189 23095 22811
1651096 23970 28874 28911
888619 25481 32701 32749
360956 26754 35831 36242
146711 36327 48865 49271
100632 52842 60567 60444
83444 58032 67736 67325
99553 64433 76963 77125
100961 76309 84018 83766
109077 80307 90129 90225
108671 84011 92252 92163
107058 85450 91762 91554
103005 83009 87674 87941
94419 78426 81348 81341
85095 71398 73610 73133
74991 65203 65451 65110
66185 59624 57826 58007
58545 53942 51377 51540
54530 50052 47438 47397
50177 47631 44624 44912
47755 45736 43558 42746
46931 44832 41386 41520
43527 42717 39586 40129
40497 39803 37836 37820
38597 38057 35778 36082
35938 35840 33861 33599
32802 32893 31877 31599
30206 29725 28954 28936
27191 26680 26273 26336
23937 23891 23677 23579
20920 20899 21071 21201
18521 18916 18773 18915
16216 16341 16330 16341
14140 14162 13962 13894
11657 11654 11933 12035
9542 9464 9671 9704
7217 7268 7219 7264
5323 5378 5223 5345
3627 3635 3737 3635
2300 2336 2326 2259
1314 1311 1360 1314
671 612 671 683
264 233 258 250
65 81 74 73
18 29 21 17
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
