A = [
270060 294148 865794 276056 301102 272836 267949 275093 269834 253809 256431 262646 268707 270758 277198 280413 284738 291947 290816 288769 293639 290747 288851 288319 289949 324929 327932 328001 359781 332565 332821 329847 301356 303792 300317 298208 294971 290958 287972 284259 281370 283690 280833 277734 280923 275773 272427 270332 263788 261118 258860 256694 254961 254508 250983 249244 245377 244415 241561 238773 235149 232923 230797 229175 227346 225255 222076 219726 218656 214172 211923 210519 207597 205491 202796 200941 198326 195958 193133 189902 187945 186369 183241 181253 178782 176931 174304 171996 170736 167394 165872 163155 161700 159669 157595 155255 153379 151588 149864 147906 146124 143192 142080 140074 138298 136381 135192 133982 132005 129747 128550 126665 124233 123783 121748 119762 118477 116376 115371 113936 112154 110448 108999 107973 105839 105087 103608 101958 100620 99969 98357 97527 94926 94313 93088 91652 90759 89115 88442 86986 85923 84533 83729 82332 81584 80194 79155 78277 77041 76137 75105 73987 72659 72050 71401 70206 69104 68301 67539 66230 65686 65092 63294 62891 61993 61229 60030 59563 58582 57807 57183 56455 56325 54897 54238 52955 52737 52080 50856 50942 49743 48943 48669 48157 47388 46782 46221 45911 45157 44257 43940 43327 42991 42502 41646 41104 40475 40904 39908 39030 38591 38523 37666 36955 36370 36211 35834 35274 34965 34643 34308 33581 32951 32795 32199 35092 31615 31706 30778 30325 29824 29723 29384 29048 28530 28258 27574 27241 27028 26746 26456 25982 25952 25123 25150 24603 26112 25057 24152 23536 23514 23410 22918 22399 22458 21968 21638 21547 21144 20973 20944 20397 20301 19787 22004 19783 19431 19135 18805 18624 18494 18157 17888 17508 17581 17267 16961 17037 17028 16490 16471 16192 15811 15880 15849 15296 15234 15048 14879 14791 14740 14314 14261 14047 14087 13814 13574 13508 13561 13295 13162 13040 12696 12703 12211 12323 12199 12003 12042 11971 11601 11777 11335 11372 11243 11163 11046 11073 10655 10722 10713 10570 10079 10262 10282 9991 9928 9858 9439 9455 9313 9191 9007 8986 8993 8823 8702 8794 8463 8337 8231 8383 8262 8122 8151 8021 7793 7930 7943 7711 7631 7596 7506 7450 7562 7364 7136 7030 6825 6898 6898 7059 6791 6588 6539 6531 6746 6310 6333 6049 6210 6244 6167 5926 5963 5971 5890 5767 5782 5718 5693 5660 5500 5429 5504 5574 5354 5257 5139 5013 5075 4968 4939 4915 5086 4842 4757 4977 4919 4761 4849 4727 4768 4613 4558 4449 4317 4346 4342 4312 4132 4197 4127 4045 4087 4036 3868 3850 3842 4041 3925 3861 3713 3795 3886 3640 3694 3559 3610 3658 3547 3494 3564 3382 3367 3498 3365 3362 3331 3311 3291 3131 3164 3123 3019 3064 3039 3020 3054 2917 2920 2835 2936 2882 2861 2820 2771 2759 2766 2743 2678 2721 2614 2704 2724 2758 2679 2557 2627 2534 2554 2574 2501 2489 2500 2425 2514 2463 2379 2329 2360 2255 2309 2318 2268 2202 2201 2252 2297 2241 2150 2174 2087 2167 2103 2191 2094 2087 2126 2121 2035 2126 1969 2060 1925 2001 1892 1945 1861 1854 1917 1937 1819 1909 1858 1777 1922 1889 1875 1678 1739 1764 1734 1785 1732 1725 1726 1834 1648 1719 1687 1616 1666 1685 1660 1596 1657 1676 1682 1569 1593 1577 1591 1536 1569 1613 1605 1546 1457 1560 1532 1582 1455 1552 1495 1533 1534 1547 1616 1500 1546 1478 1405 1438 1518 1532 1449 1384 1377 1357 1339 1363 1441 1478 1361 1403 1350 1335 1331 1311 1287 1318 1311 1238 1305 1278 1215 1297 1214 1184 1172 1193 1192 1170 1153 1242 1199 1161 1193 1167 1099 1158 1141 1064 1161 1119 1130 1101 1151 1091 1061 1084 1044 1075 1049 1054 1085 1069 1084 1081 1108 1034 1058 1061 1046 1013 1069 1008 1069 1044 968 914 991 986 1019 980 1005 948 977 959 972 942 919 914 903 906 918 946 842 977 961 896 867 879 894 846 888 894 878 887 870 808 827 816 829 832 902 813 832 810 821 783 821 778 808 807 845 788 767 809 772 746 794 807 724 720 771 713 726 746 744 741 767 746 752 771 692 748 712 730 718 694 727 693 737 682 686 679 635 669 661 654 661 665 633 694 654 626 667 617 630 616 674 654 663 650 678 659 679 609 643 653 610 615 608 693 658 593 678 677 578 610 609 628 622 676 728 620 644 666 615 601 583 597 556 645 609 578 571 606 598 556 590 569 576 549 503 527 557 588 579 539 511 510 561 544 524 548 553 535 538 550 552 524 541 547 480 536 541 569 498 543 512 487 501 481 526 540 483 460 477 460 505 492 484 438 496 466 416 504 470 436 421 419 427 416 419 399 470 411 401 451 494 408 408 446 446 441 385 423 389 396 424 392 393 427 434 427 416 439 425 450 354 409 417 402 404 399 388 404 414 435 388 363 400 369 405 388 371 399 378 383 383 388 342 372 368 362 386 333 377 325 321 354 310 326 327 346 316 352 319 300 315 318 345 310 304 331 318 297 312 347 311 326 306 303 283 292 343 321 300 312 315 343 322 300 299 310 295 279 300 275 284 270 275 291 265 298 274 277 257 275 284 286 277 243 257 289 259 247 295 260 287 282 241 236 231 231 244 261 257 255 240 250 261 213 279 204 256 206 228 250 206 224 237 241 241 243 238 247 221 212 235 227 223 235 222 244 221 222 225 195 216 194 221 207 229 208 205 200 210 214 215 206 190 204 225 211 197 225 221 215 194 195 199 194 179 207 190 177 193 182 180 217 198 180 187 207 190 196 202 185 188 196 164 188 188 209 185 186 169 191 169 179 174 187 200 192 172 173 188 144 193 188 166 175 150 160 184 159 191 176 141 154 180 172 151 173 174 137 161 186 164 153 168 175 177 148 196 171 171 172 174 191 157 176 174 171 176 174 146 147 173 161 163 145 153 148 162 155 166 152 147 164 166 146 176 145 134 141 138 155 153 148 130 142 156 135 141 134 162 159 152 143 146 157 140 134 139 121 157 132 151 144 133 148 125 132 158 120 150 142 124 127 135 131 143 114 161 133 154 143 134 130 134 122 123 125 134 118 128 138 155 116 131 135 131 135 121 107 129 125 124 145 113 131 111 98 126 132 111 118 120 121 123 122 114 129 120 142 111 119 110 105 106 140 98 140 114 130 128 139 108 114 120 140 116 110 122 113 111 123 120 132 115 120 123 111 130 122 113 121 115 105 105 110 109 109 103 103 105 110 100 98 104 101 76 98 109 92 95 102 102 99 90 106 91 81 100 90 89 85 117 94 84 87 106 102 80 84 83 74 99 97 82 73 76 88 79 83 93 77 80 80 85 100 78 83 78 78 83 71 82 89 84 96 75 85 92 95 89 83 73 110 74 76 83 74 81 79 77 100 104 87 86 84 102 83 90 77 67 90 84 84 77 71 66 103 71 76 78 80 90 64 81 93 72 87 78 66 69 65 66 66 75 85 79 63 60 61 79 70 77 59 82 68 70 79 68 71 64 58 56 45 62 47 58 56 66 75 72 65 72 58 65 80 57 67 65 68 53 76 64 77 56 78 68 70 66 71 86 53 68 79 81 72 58 51 71 57 69 65 60 72 83 53 66 58 55 48 79 62 68 52 56 71 54 63 48 58 51 63 62 56 72 55 48 52 51 74 57 70 83 50 68 55 44 70 56 67 65 34 59 65 49 58 59 49 52 43 61 53 60 54 63 71 63 54 54 60 58 63 56 87 63 55 41 49 54 63 56 54 65 51 50 54 56 64 52 58 51 38 50 41 36 68 44 53 43 50 58 38 44 59 29 37 62 60 48 36 47 53 49 56 37 39 46 48 39 37 31 40 52 41 39 39 44 39 57 52 38 51 46 39 41 47 41 50 34 33 37 43 52 45 34 52 52 52 45 46 39 32 39 34 44 37 24 47 35 36 35 35 35 35 42 27 47 40 45 45 39 52 55 36 39 39 38 36 42 46 49 48 36 41 39 38 40 34 47 38 42 45 33 34 42 47 37 41 26 37 36 48 36 51 37 50 45 41 45 51 39 41 49 32 43 43 42 34 33 34 50 32 31 31 51 28 45 32 29 43 45 38 38 36 38 38 41 48 29 27 45 29 37 51 38 41 42 36 34 41 36 40 47 37 40 34 31 48 41 31 35 30 20 36 38 46 30 31 42 29 20 23 31 24 32 30 30 31 20 28 30 30 22 28 52 42 36 33 44 50 55 46 64 50 45 33 42 41 47 47 52 44 35 29 44 41 49 61 51 45 67 53 48 32 59 46 39 33 44 31 53 43 56 47 40 46 72 59 64 79 93 40 39 55 32 25 39 34 30 32 21 24 26 18 33 30 28 22 31 23 18 16 26 26 23 23 34 36 26 41 23 25 29 28 33 27 37 36 34 39 24 34 40 25 27 25 29 28 35 26 23 30 17 33 27 30 33 30 29 33 26 31 37 23 44 31 31 35 27 43 39 27 27 36 34 23 23 27 34 27 25 18 25 23 23 40 31 28 16 30 24 29 29 17 30 23 31 33 30 31 24 19 25 20 31 16 21 29 18 21 15 30 27 20 19 28 14 31 14 16 21 25 19 17 19 20 21 24 24 26 21 32 14 25 23 17 20 28 25 18 16 18 16 24 29 16 22 34 26 30 15 35 22 28 34 22 30 26 26 30 24 18 24 28 24 19 20 18 24 24 15 35 22 31 21 23 13 20 22 16 16 23 19 23 20 35 32 25 33 28 29 26 25 32 18 16 22 20 13 24 14 18 33 16 16 18 28 24 20 23 20 17 23 16 13 29 22 30 20 20 17 17 15 20 19 16 22 21 20 35 24 22 21 23 17 21 22 14 20 21 19 22 28 17 20 16 25 22 17 21 16 17 31 16 17 18 21 34 25 18 18 15 26 24 22 14 30 17 16 20 28 18 26 21 25 20 19 18 16 21 29 18 29 24 17 25 25 29 21 21 22 17 18 18 14 23 16 22 15 17 15 19 18 16 23 19 23 18 21 20 18 28 14 24 13 19 23 18 10 17 
];
B = [
0 0 0
 81345 22194 59151
 81544 22413 59131
 116385 36644 79741
 74386 20772 53614
 83368 24524 58844
 97363 30188 67175
 105981 32198 73783
 106777 31976 74801
 169477 56408 113069
 166060 58413 107647
 150456 52143 98313
 319330 132172 187158
 74740 23099 51641
 76042 28268 47774
 57582 20090 37492
 38072 12785 25287
 53558 21343 32215
 30561 10841 19720
 46262 16874 29388
 35002 12819 22183
 63093 23761 39332
 56416 19791 36625
 84077 33507 50570
 63625 21634 41991
 97978 34930 63048
 75967 31468 44499
 182475 64981 117494
 78274 31188 47086
 196630 87629 109001
 58390 24003 34387
 44855 17806 27049
 65140 29210 35930
 75196 31027 44169
 41674 18697 22977
 70908 32134 38774
 42570 19346 23224
 43840 19384 24456
 55715 25997 29718
 84618 36405 48213
 31335 13999 17336
 82770 39322 43448
 36665 16889 19776
 34686 15403 19283
 137818 64592 73226
 32111 14568 17543
 39828 18948 20880
 68467 32465 36002
 94491 40489 54002
 72629 35315 37314
 38811 17648 21163
 40696 19628 21068
 75432 35688 39744
 32846 15127 17719
 130500 59569 70931
 74283 35577 38706
 31237 14198 17039
 42649 20726 21923
 126106 60747 65359
 71149 31871 39278
 14083870 8095865 5988005
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
52 17 1 1
52 8 0 0
92 20 0 1
94 22 1 1
63 23 1 1
82 22 2 3
730 42 7 2
4935 53 16 9
34943 74 35 15
152468 109 63 38
341950 141 75 45
599294 197 101 86
829893 234 163 84
1009052 277 209 149
997826 374 275 230
877457 430 429 401
701993 616 606 552
526662 746 836 794
356166 985 1058 1046
189836 1340 1293 1219
64575 1687 1414 1451
13705 1983 1694 1613
5177 2139 1790 1625
4384 2193 1912 1878
3878 2520 1926 2029
3944 2973 1889 2051
4501 2606 1976 2112
3521 2629 2179 2098
3599 2935 2302 2264
3266 2800 2675 2510
3298 3146 2612 2681
4024 3535 2950 2997
4132 3892 3090 3129
4709 4552 3536 3492
5047 4528 4031 3914
5233 4909 4178 4267
5526 5332 4840 4971
6253 6050 5464 5476
6628 6493 6112 6021
7151 7059 6923 6867
8105 8068 7806 7637
8907 9099 9039 8763
10252 10296 10112 10185
11602 11597 11611 11623
13162 13415 13027 13048
15285 15179 14847 15334
17072 17087 17115 17007
18898 19078 19065 18780
21234 21002 21381 21367
23798 23652 23272 23417
25934 25664 25789 25617
27927 27527 27275 27733
29769 29602 29330 29195
31271 30985 31038 31008
33048 33274 33389 32996
34619 34637 34603 34697
36435 36343 37061 36446
39328 38684 39057 38442
41025 40846 41123 41174
42767 43006 42826 42511
44827 45477 45295 44876
45430 45026 45152 44663
43873 43315 43848 43282
38781 38258 38332 38325
27975 28534 28844 28015
16587 16988 16439 16885
9580 9659 9611 9713
7248 7737 7054 6392
6493 5817 5874 5619
5208 5279 5500 4910
4231 3801 3694 3975
3389 2904 3031 2969
243 245 321 278
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
