A = [
210771 202947 740934 204251 203072 188468 186467 190196 190731 186195 187812 194372 196354 198565 203103 205392 209384 217856 217042 215222 220581 218863 219198 222070 234605 365474 366118 370284 499372 480848 500119 501006 478949 488091 501766 497880 481549 483968 480067 470672 466979 467017 464348 457246 458196 451401 445459 444124 433909 426320 422324 420644 415176 410751 405760 405247 395950 389801 383792 378932 373260 369948 364237 359413 355568 350890 347466 343331 338419 333647 327131 322959 317951 313332 308009 304513 300889 294672 290624 288460 284202 277757 273822 270560 265423 260849 256812 253276 249061 244499 240939 237752 232564 228655 227132 222597 218484 214869 211578 207453 202992 201170 198040 195888 191361 189198 187150 182688 178963 177220 173093 170282 166411 164241 160247 158644 155778 152489 150219 147830 145542 141795 139370 135992 132565 131066 130099 126816 123068 122434 120312 118829 116080 113789 112581 109910 109376 106081 103898 101191 98596 97653 96021 95045 92828 90880 89589 87483 85538 83655 82520 81040 79068 78216 75515 74205 73013 71566 69908 68540 67142 65803 63931 62602 62156 60171 59628 58361 56252 55632 54395 53686 53086 51752 50846 49436 48365 47581 46505 45399 44993 43741 42670 41832 42040 40371 39494 38896 37603 37784 36542 36140 35268 34845 34039 33189 33042 32369 32021 30595 30375 29564 28901 28320 27563 27253 26998 26454 25728 25471 24979 23848 23490 22768 22863 22300 21640 21286 21022 20845 20407 19733 19516 18761 18371 17939 17516 17816 17445 16720 16496 16303 15990 15329 15199 14979 14490 14463 13927 13530 13595 13617 13183 12968 12955 12645 12602 12347 12167 12195 11625 11427 11216 11121 11029 10601 10259 10347 9838 9968 9910 9524 9256 9681 9131 8919 8851 8731 8564 8772 8623 8497 8225 8168 8073 8016 7779 7490 7903 8198 8290 7802 7838 7763 7783 7581 7220 7037 7106 6979 7011 7019 6812 6906 6664 6458 6412 6264 6501 6687 6381 6272 6199 6315 6183 5662 5767 6428 5867 5695 5537 5578 5654 5695 5481 5406 5616 4980 4632 4562 5091 4223 4213 3998 3754 4248 4086 3691 3433 3642 3375 3353 3353 3377 3277 3288 3445 3293 3391 3404 3567 3611 3652 3683 3534 3543 3280 3136 3189 3031 3170 3305 3274 3046 3187 3058 3377 3184 3423 3176 3178 3281 3155 3431 2949 3238 3362 3129 2789 2657 2978 2805 2640 2815 2834 2949 2943 2664 2632 2480 2286 2412 2203 2241 2876 2659 2562 2520 2657 2765 2861 2902 3181 2853 3016 2755 2098 2067 2039 2093 2014 2355 2010 2216 2245 2455 2088 2014 1995 2201 1948 2117 1971 2134 2110 1971 2090 1897 1883 1891 1898 1690 1721 1704 1724 1717 1768 1842 1996 1873 1690 1500 1593 1647 1620 1550 1632 1499 1491 1610 1295 1316 1278 1283 1283 1218 1244 1435 1290 1201 1287 1325 1381 1272 1104 1192 1125 1124 1123 1051 1165 1028 1040 1076 1199 1077 1262 1076 1099 1153 1383 1137 1228 1050 1018 921 967 899 937 935 879 979 949 937 962 987 974 950 927 1007 972 970 994 1007 1053 1020 1015 1022 912 912 961 941 938 966 948 968 881 902 878 798 810 908 822 939 880 1007 822 832 781 844 773 825 758 773 876 861 800 883 816 816 916 868 826 827 885 899 804 803 807 883 784 681 735 844 873 858 810 900 869 838 848 876 843 893 904 855 823 809 932 840 672 694 673 771 699 677 658 746 723 715 807 784 715 730 674 635 604 627 589 618 652 591 633 698 603 560 550 554 601 604 666 525 614 683 618 532 562 536 531 536 500 515 481 511 513 483 476 548 500 521 566 650 621 604 479 557 497 600 538 558 516 554 527 493 531 584 535 543 451 423 503 533 538 495 503 504 495 513 406 416 448 348 454 399 372 395 380 450 477 405 498 314 312 374 357 384 375 353 334 345 315 340 380 320 336 350 428 390 350 312 305 311 316 311 289 262 319 267 292 286 308 296 260 288 277 278 275 280 272 301 291 326 301 330 331 335 407 384 391 306 339 334 340 312 370 290 341 359 286 317 378 401 326 369 346 391 334 392 351 409 359 375 384 418 403 380 329 317 404 381 367 393 401 653 602 744 1383 940 686 748 535 553 514 685 430 442 845 539 729 588 639 516 697 598 565 716 331 506 399 404 286 275 234 294 242 281 306 261 290 285 346 326 302 329 310 262 419 332 267 187 206 193 234 234 238 232 332 342 347 220 227 248 269 282 287 251 278 246 259 250 250 244 191 197 217 193 223 249 220 202 198 214 218 211 194 185 221 221 204 174 233 161 182 182 166 145 154 150 203 213 172 156 193 172 203 167 195 296 260 256 298 286 308 280 255 300 281 263 242 236 232 290 317 199 214 290 191 167 180 166 183 140 188 158 153 206 180 166 181 249 183 203 155 180 198 198 243 177 257 266 244 247 253 232 209 232 204 192 178 186 155 151 119 131 138 136 191 123 161 148 136 113 140 120 115 156 150 148 139 110 138 105 105 115 118 135 110 137 143 177 129 110 128 115 90 106 118 92 79 99 97 110 97 89 81 92 92 88 107 94 72 130 96 92 106 73 96 80 94 109 77 68 61 83 82 71 61 69 78 89 97 69 83 79 81 97 101 84 80 75 71 70 97 68 83 65 50 53 55 68 77 57 53 68 53 51 58 59 55 73 41 51 60 38 58 56 80 72 90 89 73 78 64 57 62 50 41 47 59 47 43 38 35 50 51 52 50 42 44 53 56 47 58 56 62 58 45 46 103 91 114 125 108 104 95 95 97 91 104 94 102 92 100 81 85 86 97 87 81 101 45 59 54 44 48 63 133 96 108 161 119 156 234 50 54 48 63 63 56 47 58 51 47 43 49 64 39 37 27 40 42 34 49 43 37 39 37 31 34 34 49 44 51 45 49 44 46 51 43 36 46 44 59 60 66 73 106 52 65 62 47 49 50 36 48 56 55 39 45 53 45 42 38 32 30 27 34 25 37 26 44 34 38 45 43 28 27 37 34 43 30 28 24 20 23 34 30 38 22 33 26 26 28 52 43 46 47 67 68 56 58 58 46 60 69 93 67 65 69 85 74 49 50 72 81 68 78 57 113 73 87 99 96 71 91 106 123 98 118 149 65 73 70 77 89 55 61 60 54 67 44 46 82 33 45 22 35 18 53 33 57 40 40 47 37 45 36 27 30 36 22 30 30 27 27 25 33 24 35 25 34 24 34 31 21 26 29 14 27 16 28 28 15 18 13 23 18 28 24 25 18 15 21 27 19 16 14 18 19 14 21 16 18 26 23 22 17 20 21 16 19 18 20 20 19 24 24 15 25 18 22 29 20 20 24 23 28 22 18 32 46 44 67 54 43 64 54 51 46 59 35 42 42 47 49 50 36 49 45 29 44 35 45 35 37 44 34 27 33 35 38 31 42 14 13 17 16 8 11 17 14 15 14 14 16 15 14 14 15 13 20 18 12 14 15 11 20 24 11 21 15 15 20 14 27 12 14 16 18 11 11 14 13 15 14 18 14 12 10 12 8 11 17 17 19 18 12 19 21 12 25 5 12 14 14 10 14 8 20 6 5 9 20 23 18 15 8 10 17 6 11 6 12 8 13 12 16 10 11 19 9 12 20 20 17 16 18 7 20 16 15 16 14 23 14 9 13 5 10 13 12 8 17 8 7 17 11 13 11 11 14 8 6 8 14 15 12 8 13 8 6 8 4 4 8 5 7 11 16 9 7 6 11 10 7 11 5 11 6 9 10 9 6 7 8 11 3 15 12 13 15 10 8 5 6 13 10 9 7 7 8 10 11 13 10 6 12 8 14 5 9 7 11 11 11 10 3 7 9 8 11 16 15 5 9 10 13 8 7 10 13 6 7 7 10 9 8 17 29 15 16 26 18 20 12 11 11 12 17 11 7 11 5 12 6 11 4 9 8 8 6 5 7 6 4 7 9 9 7 9 10 11 8 11 9 17 7 9 14 8 7 11 11 12 12 11 10 9 12 11 6 8 6 7 8 9 8 9 10 7 11 10 7 14 8 9 9 15 5 15 8 4 10 8 10 12 15 12 13 6 10 12 6 6 5 6 4 3 6 9 10 7 8 6 7 11 20 7 8 7 5 5 9 13 9 9 15 7 11 7 8 17 8 11 10 17 16 9 18 18 27 19 16 18 19 22 13 31 22 18 27 23 15 28 33 22 16 22 23 21 34 26 20 27 23 24 367 275 427 562 585 398 369 248 343 116 6 6 5 7 7 6 6 7 4 4 8 14 5 7 10 5 7 6 4 9 8 5 9 6 10 11 16 20 57 11 12 7 8 6 11 12 8 11 10 5 13 4 4 12 9 17 7 4 16 15 9 8 8 6 7 6 12 17 16 4 9 12 11 17 10 14 9 9 12 13 15 3 9 7 2 3 3 3 10 5 9 5 7 7 13 14 10 7 10 11 4 7 6 9 3 14 7 4 4 9 5 7 5 3 6 2 3 7 1 5 12 5 5 8 5 8 4 3 7 7 6 5 2 10 11 2 3 5 9 6 8 6 5 8 8 6 8 4 5 5 6 6 3 9 7 4 5 4 9 4 3 3 5 5 5 3 3 8 6 8 5 6 11 6 12 4 4 4 6 8 9 4 7 6 8 3 5 5 4 3 1 8 5 5 5 7 5 9 4 4 9 11 6 7 7 6 5 8 12 3 4 5 4 8 5 7 2 6 7 5 6 9 11 5 15 9 8 4 5 9 5 6 7 4 3 11 9 2 7 5 8 4 3 4 3 4 7 4 4 8 5 11 5 6 4 7 5 5 3 5 4 6 5 3 4 7 5 6 3 7 4 1 6 7 4 4 2 2 0 4 4 5 2 3 6 6 1 8 7 11 7 8 9 7 11 2 18 6 4 14 8 8 4 5 4 6 5 3 0 9 8 3 12 5 7 4 3 6 8 9 4 2 4 4 
];
B = [
0 0 0
 88021 12855 75166
 46938 6835 40103
 164514 27800 136714
 50354 8132 42222
 53623 8459 45164
 74458 11986 62472
 85141 15036 70105
 63682 11336 52346
 167750 31363 136387
 57095 14790 42305
 66258 18862 47396
 87674 28947 58727
 106472 22886 83586
 52937 15425 37512
 149627 27765 121862
 51749 8314 43435
 50917 8420 42497
 53212 7509 45703
 108592 16149 92443
 57831 8817 49014
 168362 25474 142888
 96946 13259 83687
 92178 16619 75559
 180861 22496 158365
 263322 38432 224890
 42520 9784 32736
 770628 113025 657603
 24893 8038 16855
 51783 14811 36972
 32784 7837 24947
 51270 9808 41462
 24165 7414 16751
 165882 30970 134912
 18400 5447 12953
 36741 8770 27971
 24563 5431 19132
 42699 7503 35196
 11842 4464 7378
 192426 31105 161321
 5402 3115 2287
 9996 5072 4924
 11392 3969 7423
 33665 5648 28017
 21026 10030 10996
 7791 3150 4641
 11292 3675 7617
 21582 6474 15108
 315397 44068 271329
 9634 5250 4384
 10214 4255 5959
 8557 3670 4887
 16012 7613 8399
 23248 5072 18176
 335189 48219 286970
 14929 5833 9096
 9864 3458 6406
 13848 4761 9087
 142139 19880 122259
 114555 18050 96505
 17361766 3276986 14084780
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
19 30 8 2
11 17 0 0
8 16 0 0
25 16 1 1
47 21 2 3
64 15 27 0
587 20 92 3
2612 28 109 25
11033 54 138 71
38646 74 177 120
279456 104 278 166
408191 200 541 244
485051 325 1126 418
546992 613 1331 604
504834 1093 1590 835
393029 2028 1677 1465
245014 3106 2220 2022
117125 4573 3384 2816
44609 5872 4226 5047
17196 7270 4350 4528
9639 7712 6748 6469
6973 9017 8931 7620
7175 12891 8085 5769
7093 10451 11190 7368
7337 10438 10088 8965
7319 8582 6277 6560
7562 6268 5565 5831
6680 5877 5691 5905
7009 6884 6671 6391
7047 7330 7042 6977
7227 7233 7107 7397
8699 7579 7486 7517
8445 8097 8182 8134
9893 9164 8644 8633
10205 9652 9379 9329
10060 10461 10245 10163
11020 11003 11047 10869
12199 11817 11800 11976
12246 12327 12195 12324
12506 12604 12395 12574
12566 12727 12580 12764
12501 12168 12297 12558
11791 11748 11934 11728
10420 10640 10619 10500
9277 9024 9182 9345
7593 7801 7692 7766
5814 5656 5914 5937
4117 4089 4134 4216
2628 2745 2704 2681
1466 1458 1548 1483
690 658 674 615
237 247 232 213
68 71 56 68
9 9 19 12
0 0 0 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

];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 
];
