A = [
334299 375742 1047874 333204 382586 334186 335805 341463 336269 322268 323414 326762 325979 318404 316057 310215 305097 304648 299961 297575 296230 292314 290146 288599 286800 310428 309386 307266 331199 331737 332534 331414 333388 332842 331938 329841 328383 325963 323764 320300 319314 317169 315586 312052 312087 309184 305849 304964 300764 298709 297181 293612 292208 290573 288061 286895 283463 280509 278059 276910 273556 270920 269230 266332 264285 262455 259265 258105 254369 251573 250294 249028 245412 242333 240047 238369 235453 233186 230815 228252 226086 223407 220544 218796 216658 213918 211403 209327 206303 204322 202396 199794 198145 195190 192918 190607 188497 186143 184356 182163 179182 177998 175354 173643 171171 169211 166717 165598 163311 161613 159643 157870 155630 153304 151762 149071 147810 145280 143020 142176 140611 138690 136418 134251 133143 131333 129640 128199 126514 124902 123155 122105 119519 118523 116892 114584 113715 112860 110565 109143 107141 106954 104978 103953 102478 100757 99953 98551 96438 96230 94719 93386 92736 91034 89335 88290 87580 86402 85152 83781 83124 81889 79856 78692 78043 76651 75719 74883 73971 73406 72084 71191 70102 69009 68074 67880 66473 64997 64744 63542 62672 62176 61280 60338 59294 58460 57637 56821 56691 55742 55612 54097 53887 52904 52074 51611 50575 50206 49421 48716 48216 47764 46751 46289 45667 44784 44620 43605 43643 43243 42033 42025 40937 40714 39624 39646 38872 38635 38219 37632 36880 36912 35815 35696 35622 34530 34509 34353 33146 32955 32501 32318 31772 31663 30884 30464 30186 29768 29048 29187 28640 28378 27732 27770 27729 27373 26924 26459 26022 25736 25612 25390 24831 24769 24464 23962 23786 23632 23424 22595 22491 22253 21975 22008 21758 21063 21479 20777 20706 20388 20371 19994 19866 19462 19314 19124 18714 18681 18295 18296 18115 18298 17570 17291 17645 17332 16737 16646 16605 16363 16317 16026 15939 16120 15414 15479 15185 15238 15019 14984 14514 14573 14198 14276 14023 14009 13647 13654 13280 13423 13273 12978 12843 12854 12789 12410 12534 12242 12014 12119 11587 11665 11694 11303 10920 11244 11088 10815 10892 10697 10597 10713 10523 10325 10207 10100 10124 9949 9745 9992 9953 9665 9632 9469 9475 9414 9246 9220 8888 8998 8886 9162 8564 8614 8610 8228 8670 8402 8374 8104 8005 8008 7957 7978 7812 7916 7771 7558 7598 7497 7345 7289 7247 7186 7171 7134 6943 6898 6765 6852 6647 6708 6618 6488 6514 6439 6348 6251 6153 6118 6310 6196 6192 6164 6138 6014 5857 5840 5683 5862 5827 5772 5469 5657 5487 5502 5359 5311 5406 5343 5182 5267 5221 5084 5109 5061 4874 4985 4791 4840 4779 4754 4764 4650 4584 4588 4584 4492 4585 4536 4566 4470 4470 4432 4377 4304 4437 4310 4425 3984 4080 4165 3942 3945 3941 3886 3862 3964 3770 3861 3793 3824 3863 3670 3620 3602 3502 3595 3558 3435 3499 3377 3482 3534 3466 3470 3408 3359 3327 3286 3266 3336 3230 3175 3123 3080 3095 3135 3102 3046 3011 3010 2921 2838 2962 2936 2987 2920 2864 2925 2943 2771 2741 2807 2817 2764 2796 2757 2718 2634 2712 2636 2679 2666 2553 2627 2643 2504 2518 2489 2438 2500 2488 2564 2390 2409 2357 2383 2407 2426 2260 2311 2374 2251 2290 2279 2285 2164 2223 2194 2246 2205 2126 2190 2090 2079 2171 2130 2186 2155 2142 2137 2059 2104 2068 2307 2065 2303 2076 2028 2146 1960 1964 2006 1977 1998 1894 1988 1838 1997 1853 1900 1910 2014 1938 1733 1791 1772 1793 1862 1671 1701 1803 1746 1821 1863 1865 1745 1744 1690 1693 1662 1701 1702 1634 1634 1658 1647 1631 1683 1606 1556 1601 1602 1529 1502 1538 1536 1541 1575 1442 1444 1413 1498 1435 1453 1401 1427 1376 1430 1436 1440 1415 1350 1374 1283 1398 1340 1309 1334 1212 1262 1355 1279 1179 1297 1250 1321 1193 1232 1242 1197 1258 1119 1250 1220 1233 1226 1107 1207 1257 1135 1184 1155 1111 1108 1153 1107 1163 1067 1088 1105 1118 1043 1066 1033 1049 1031 1056 1061 980 1062 987 980 1083 1057 1064 1040 971 990 1028 1056 983 934 955 949 919 973 910 990 953 912 965 969 918 932 859 937 842 923 935 918 923 892 868 869 868 811 789 848 860 860 833 821 839 869 826 864 788 806 804 828 788 818 800 763 793 759 827 839 821 786 739 789 820 801 798 732 753 778 735 797 789 864 828 874 973 950 859 776 799 828 841 778 732 735 805 774 822 810 788 801 798 766 678 662 689 737 667 638 688 649 670 641 683 613 639 640 687 613 644 650 684 723 663 668 701 705 636 607 586 641 578 593 630 618 666 644 611 577 555 588 535 591 568 591 602 624 540 613 568 525 556 527 585 626 484 536 578 544 538 516 487 529 490 485 487 491 489 476 503 500 479 463 485 499 526 501 459 473 454 525 468 467 482 481 480 532 468 439 513 485 463 435 459 432 453 476 477 458 405 436 468 486 413 392 423 429 396 392 422 409 410 394 395 343 403 379 411 380 371 398 415 359 366 405 365 406 421 388 408 372 407 386 379 397 364 370 394 364 375 342 338 406 351 366 401 340 359 340 362 314 366 339 299 338 308 388 339 303 341 318 287 280 319 323 279 386 314 325 360 310 319 375 282 284 283 315 285 344 313 286 297 304 244 307 283 264 306 263 305 283 294 299 268 262 277 264 256 231 271 256 289 262 269 280 251 292 233 261 272 275 242 242 263 248 266 257 237 251 235 223 234 232 228 223 244 221 231 238 220 220 228 235 229 207 224 229 185 225 207 212 231 228 197 223 207 214 209 205 249 230 231 195 201 197 199 203 229 219 200 198 185 210 218 180 205 205 213 207 206 222 202 213 217 179 176 174 197 185 178 195 195 180 211 190 176 190 176 170 200 208 203 160 194 185 179 173 184 174 205 177 191 180 182 177 184 193 185 169 205 176 214 198 173 184 196 163 176 206 201 207 205 174 195 189 165 205 186 177 185 165 174 177 161 151 170 174 149 190 159 153 149 170 149 145 164 174 137 150 147 170 142 148 137 136 156 156 137 158 147 168 141 143 157 157 162 163 144 139 154 145 139 145 144 141 140 139 146 138 142 147 154 154 137 156 145 136 148 131 133 140 139 158 141 144 133 149 130 157 144 139 170 143 118 134 128 156 144 129 135 148 135 141 157 120 130 129 112 138 136 144 152 136 162 108 140 145 130 131 118 156 129 128 146 135 134 139 134 117 122 131 116 116 131 118 103 116 128 107 107 110 106 113 142 87 108 108 130 93 106 121 129 102 117 106 112 108 96 90 102 121 124 105 81 97 97 86 121 90 80 96 90 98 112 80 74 91 93 104 101 101 96 87 76 95 88 123 108 99 92 80 82 95 100 87 99 94 68 84 133 105 90 96 95 109 95 83 83 80 104 105 81 76 79 82 84 86 78 90 85 103 101 82 90 78 83 94 98 93 85 90 91 93 90 117 92 93 87 98 91 86 66 89 79 90 78 87 72 92 73 69 71 82 64 78 96 93 79 70 87 99 83 68 62 76 89 65 56 69 65 76 65 66 89 72 68 62 73 80 65 73 60 72 74 47 67 66 44 76 81 62 77 73 83 62 66 75 62 69 51 78 67 63 53 64 68 76 76 63 71 57 64 50 60 64 59 68 78 77 70 63 70 61 72 55 63 60 55 80 62 63 66 63 70 64 65 76 84 66 65 49 70 72 65 62 74 64 63 53 64 70 77 67 70 90 83 70 69 73 57 77 49 51 68 73 59 65 64 63 54 62 56 73 58 60 65 46 45 66 40 63 66 51 59 60 52 79 55 56 69 55 52 43 43 50 51 70 46 52 47 53 38 47 60 56 46 62 57 39 55 57 46 48 49 52 41 49 55 52 58 53 45 48 40 53 55 41 37 48 47 47 42 44 50 63 48 47 56 51 49 46 44 47 62 50 42 48 48 40 44 46 45 47 55 45 43 59 39 49 50 56 46 49 36 42 61 44 47 41 41 43 43 45 53 40 45 37 45 44 36 37 41 48 40 24 37 36 39 37 34 39 35 38 47 27 20 33 45 40 49 31 32 44 39 35 35 43 51 46 29 35 41 39 36 37 33 40 35 43 39 39 35 35 43 40 39 41 35 32 26 41 33 33 47 38 40 36 41 36 44 36 35 44 45 48 43 47 50 43 44 34 39 51 42 36 36 53 51 39 46 31 35 32 37 34 41 33 38 40 41 53 41 43 35 40 31 36 36 44 35 35 41 42 31 39 41 28 28 38 30 30 25 35 31 31 44 36 42 40 43 44 41 31 41 42 36 40 46 31 50 58 45 50 41 46 48 74 148 161 157 121 90 95 89 53 32 30 40 28 23 32 30 34 32 33 44 37 34 42 37 26 30 32 38 47 23 31 30 40 28 43 42 32 67 31 50 47 42 47 35 41 23 31 26 33 31 25 36 36 34 28 31 26 34 34 21 21 31 22 29 24 26 28 24 36 28 25 26 29 18 34 31 27 37 28 34 40 31 34 30 41 25 23 22 20 28 36 34 42 27 35 32 40 20 40 43 40 38 24 33 38 31 31 26 23 29 27 30 27 25 28 24 32 34 24 29 28 30 16 31 33 31 27 33 18 20 30 28 33 20 28 35 18 32 33 26 26 24 27 32 27 33 29 20 22 31 43 27 28 20 32 23 32 31 34 18 27 30 27 27 32 36 28 25 14 32 20 23 38 38 28 30 32 32 29 31 41 34 29 29 24 38 27 29 25 38 31 17 38 32 29 25 24 22 32 34 27 33 19 39 21 24 22 18 24 23 20 19 29 27 26 23 21 23 17 19 34 27 33 22 29 26 20 25 24 29 27 21 22 26 24 23 22 24 22 14 27 23 27 26 23 33 16 19 17 21 15 27 24 24 19 23 17 22 32 25 20 15 26 22 34 27 27 26 22 15 20 27 18 18 26 23 27 20 20 29 29 29 32 20 18 26 18 31 29 28 28 22 29 27 26 30 31 19 29 26 27 21 23 23 22 27 28 40 27 36 22 34 24 30 33 25 27 24 26 32 32 29 17 
];
B = [
0 0 0
 114400 39561 74839
 54251 18249 36002
 196701 78515 118186
 118990 42987 76003
 66972 23288 43684
 191564 79346 112218
 145774 54463 91311
 79870 29165 50705
 252908 103380 149528
 258117 99248 158869
 46214 16303 29911
 747745 310454 437291
 96876 37629 59247
 30715 11260 19455
 172639 81013 91626
 54704 23850 30854
 16794 6279 10515
 189354 89876 99478
 15538 5812 9726
 15993 6173 9820
 3924 1461 2463
 115 48 67
 3520 1501 2019
 281736 135790 145946
 18176 6936 11240
 23508 9913 13595
 295265 144390 150875
 16664 7304 9360
 35106 15334 19772
 456847 216201 240646
 33419 14437 18982
 57808 26153 31655
 334126 168503 165623
 222553 110816 111737
 371091 189599 181492
 685312 350028 335284
 546943 253606 293337
 343401 171221 172180
 810442 418771 391671
 310037 135842 174195
 21571 9506 12065
 741731 373334 368397
 11717 5215 6502
 20753 9119 11634
 1025923 540418 485505
 21505 9789 11716
 256206 111371 144835
 1449713 835135 614578
 257850 116074 141776
 6 1 5
 10630030 6380834 4249196
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
58 49 2 2
78 10 0 0
149 16 0 0
199 33 0 1
132 21 0 0
131 36 19 0
323 61 53 7
1814 69 72 10
12678 104 98 35
60886 145 137 80
157412 166 173 90
344248 236 222 125
646836 301 327 216
1149524 398 431 314
1603747 490 539 413
1793659 636 720 655
1519534 809 945 951
1058360 987 1197 1220
628326 1276 1399 1457
313454 1504 1708 1768
120674 1886 1764 1832
29634 2202 1954 1893
7421 2507 1972 1945
5425 2585 1984 2051
4794 2704 1947 2282
4409 3169 1995 2246
4795 2927 2180 2247
3864 2831 2325 2316
3830 3278 2452 2292
3498 3109 2566 2528
3600 3116 2697 2777
4004 3545 2858 3041
4679 4009 3111 3026
4990 4201 3264 3415
5009 4407 3708 3670
5004 4461 4021 3938
5568 4861 4439 4462
6039 5327 4911 4849
5908 5583 5480 5271
6100 5959 5730 5904
6736 6709 6239 6488
7324 7370 7231 7156
8084 8156 8236 7774
9069 9210 9025 9088
10310 10204 10049 10157
11499 11557 11529 11779
13115 13254 13046 12956
14247 14100 14394 14340
15922 16006 15786 15895
17616 17741 17136 17322
19164 18928 18851 18987
20403 20442 20127 20158
21786 21398 21156 21157
22795 22717 22377 22731
23912 23867 24395 23636
25093 25079 24919 24940
26632 26662 26598 26440
28390 27817 27857 27779
29359 28963 29377 28940
30367 30186 30430 30578
32238 32165 31723 31602
32389 32011 32205 31815
31782 30914 31657 31193
27927 27718 27827 28169
20975 21254 21361 20689
12782 13446 12854 12798
6796 7619 7142 6789
5310 5258 5286 4757
5074 4361 4526 4110
3983 4302 4928 3688
3237 3312 3187 3490
2536 2028 2354 2408
208 205 157 172
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
