A = [
445706 484993 1589721 478172 518974 471525 462412 470412 461344 435898 433324 437393 433821 424566 424025 416951 412801 412261 405552 404624 403013 398391 395197 394525 393250 465772 462682 462654 533719 533482 533809 533891 533884 535832 534284 529813 523864 519981 515395 507858 504193 501444 496881 495057 491501 486733 482129 479117 472630 468899 464962 460165 459084 455345 450587 447338 444425 438964 434881 432420 427008 421650 420304 415823 412417 410281 406526 402157 399106 391949 388667 386600 382520 377629 375128 371903 367555 364574 361223 356973 354755 350437 347194 343696 340692 336915 334556 330323 326765 323746 320180 317085 314199 310946 306984 303451 301474 298604 294951 291642 288897 285642 282214 279666 277024 274731 272398 269564 265997 262791 259251 256787 253676 251771 248163 245972 243734 240972 237865 235072 232051 229841 227183 223745 220107 218641 217103 213284 211944 208858 206015 205566 200966 199643 196258 193526 192988 190091 187737 184443 182804 180753 178380 176219 174739 172333 169803 167687 165082 163419 162020 159569 156887 156181 153759 151673 149451 148047 145388 143486 141363 140948 137027 135471 133929 132284 130758 128702 126518 125373 124185 121609 120630 119024 117759 115389 114623 112215 110768 109724 108238 106906 105081 103865 102296 101049 99596 98482 97049 95230 95056 93620 91827 90858 89180 87761 87328 86394 84783 83503 82766 81111 80428 79301 78127 77416 76387 75124 74150 72900 72699 70989 70503 69173 67947 67018 66839 65190 64552 63390 62883 62058 61356 60918 59770 58825 58123 57550 56131 55186 54585 53990 53354 52703 51410 51310 50145 49636 49098 48355 47690 46919 46560 46129 45356 45096 44136 43811 42723 42272 42102 41659 41323 40660 39888 39524 38673 38647 37697 37296 36910 36442 35768 35547 34708 34347 33978 33510 33112 32796 32261 32310 31515 31030 30772 30541 29717 29558 29060 29175 28655 28251 28042 27502 27378 27030 26489 26261 26344 26078 25268 24960 24455 24388 24359 23651 23342 23052 23154 22698 22149 22169 22077 21867 21484 20948 21096 20798 20465 20363 19904 19516 19509 19322 18979 18676 18631 18229 17856 17710 17674 17224 17215 16781 16388 16789 16336 15719 15782 15688 15343 15420 14795 14821 14684 14591 14240 14317 14113 14108 14183 13756 13639 13666 13432 12947 13177 12677 12923 12641 12421 12972 12143 12036 11981 11659 12202 11579 11596 11342 11354 11180 10969 11036 10717 10689 10467 10414 10075 10225 9869 9909 9738 9787 9720 9638 9535 9205 9290 9228 9099 8769 8905 8765 8894 8706 8474 8484 8453 8390 8203 8176 8289 8183 7943 8123 7608 7617 7403 7362 7553 7366 7172 7114 7017 6774 6869 6717 6720 6663 6402 6773 6493 6365 6423 6393 6139 6241 6284 5988 6044 5823 5899 5709 5616 5692 5502 5531 5484 5665 5422 5415 5442 5251 5328 5165 5268 5027 4935 4961 4821 4910 4825 4786 4797 4646 4659 4536 4578 4553 4511 4434 4276 4365 4377 4337 4281 4227 4213 4156 4176 4256 4006 4013 4071 4058 4045 3926 3886 3821 3915 3783 3805 3660 3750 3692 3596 3541 3552 3510 3575 3407 3418 3393 3537 3401 3299 3218 3353 3207 3260 3204 3202 3202 3181 3300 3154 3081 3085 3046 3089 2981 2850 3013 2902 2939 2900 2849 2888 2838 2781 2771 2809 2740 2820 2740 2628 2651 2644 2641 2602 2561 2504 2574 2535 2584 2563 2478 2516 2497 2477 2420 2357 2443 2369 2400 2390 2356 2359 2324 2349 2302 2275 2289 2305 2310 2295 2458 2314 2232 2350 2220 2268 2231 2247 2230 2119 2174 2137 2101 2077 2290 2070 2190 2088 1961 1979 1967 2013 1913 1991 1986 1959 1945 2076 2009 2034 1982 1919 1959 1877 1799 1834 1772 1727 1798 1845 1821 1697 1756 1763 1675 1768 1746 1735 1671 1671 1659 1658 1644 1609 1553 1625 1591 1670 1584 1623 1567 1586 1531 1507 1585 1478 1421 1540 1522 1523 1471 1429 1403 1467 1435 1395 1410 1401 1362 1377 1392 1368 1360 1328 1358 1356 1410 1288 1321 1263 1333 1313 1262 1329 1293 1300 1221 1248 1258 1257 1128 1200 1178 1187 1213 1157 1140 1147 1157 1248 1157 1177 1093 1131 1108 1129 1116 1126 1201 1150 1112 1123 1076 1051 1075 1140 1094 1074 994 1033 970 1031 1043 1008 982 1001 1020 990 995 1005 1031 965 1002 996 1003 979 983 989 970 930 953 945 949 934 927 965 881 968 889 915 882 886 899 908 900 876 860 849 812 821 840 869 832 896 909 837 903 860 882 801 798 898 900 853 936 841 879 981 1014 1053 991 971 905 870 895 829 923 784 809 902 844 893 860 809 899 848 836 736 759 769 794 714 700 750 706 736 710 766 702 714 703 716 707 720 781 725 781 733 671 741 754 675 665 635 675 715 648 716 676 724 714 690 628 669 683 589 608 621 670 638 634 648 660 658 640 592 573 717 643 578 573 705 575 562 576 548 576 555 556 519 482 543 564 536 554 538 514 513 540 570 587 500 543 550 550 536 500 541 590 591 543 524 506 581 582 596 543 568 516 532 503 471 493 466 499 494 487 462 508 484 449 477 408 459 434 424 443 453 448 442 407 445 407 416 413 459 440 476 498 460 484 401 444 449 450 406 438 422 416 379 425 403 375 379 417 463 436 369 426 429 349 407 418 397 365 371 348 357 349 342 392 356 357 360 321 335 322 358 322 395 355 379 407 427 345 384 378 331 294 345 333 331 291 340 280 340 306 336 297 307 282 306 323 296 270 272 352 302 266 288 307 296 288 278 295 291 271 307 307 294 296 281 334 261 295 296 274 238 297 279 235 267 236 248 293 259 235 245 236 218 232 238 262 269 261 249 276 251 284 195 244 247 268 245 261 215 231 224 230 242 250 247 259 271 266 275 249 240 251 216 233 233 279 246 222 222 193 184 260 227 222 217 216 228 226 222 239 217 217 185 196 216 204 212 245 205 192 222 207 213 247 193 199 227 187 225 182 206 230 249 216 210 233 205 209 230 194 217 186 208 225 214 214 215 213 204 204 223 201 211 190 236 199 211 200 191 241 188 189 215 199 213 203 192 209 202 198 188 163 176 160 176 177 165 175 200 193 174 176 197 194 178 142 183 184 183 174 165 145 181 177 172 169 164 165 168 179 160 165 194 151 193 157 170 177 158 196 165 154 152 157 157 150 171 181 162 143 171 170 158 146 173 135 143 149 176 174 141 133 141 167 161 156 150 160 169 148 150 161 164 181 153 159 156 127 157 142 173 152 170 158 157 166 161 154 147 158 186 160 145 144 172 166 148 150 131 155 130 148 136 146 142 149 145 141 154 133 151 152 124 143 125 144 119 108 126 108 99 125 124 111 118 110 136 108 128 132 121 119 110 120 107 100 111 123 113 104 129 99 104 95 109 98 104 108 116 102 102 89 128 85 106 111 111 99 109 114 107 109 106 98 102 109 110 99 104 115 102 95 119 115 87 105 100 121 101 115 102 105 83 93 93 93 82 113 98 99 86 89 108 101 94 113 83 117 104 107 84 102 104 87 105 81 103 103 122 115 94 91 99 109 100 92 104 88 82 112 79 85 86 109 86 92 105 91 96 82 82 74 81 80 90 69 88 81 76 80 79 77 82 73 79 84 67 76 73 65 64 84 68 52 76 70 62 77 70 76 82 64 78 82 71 67 73 65 81 69 73 73 71 69 67 81 55 62 77 56 72 74 64 63 62 68 74 86 73 68 71 92 62 74 74 61 62 80 70 65 73 61 72 55 65 86 82 80 74 70 84 70 72 79 64 68 68 50 63 61 67 81 57 85 75 81 87 80 86 75 76 77 99 87 85 82 64 92 84 79 72 68 72 60 60 61 61 84 65 75 84 82 80 63 55 57 71 62 54 77 52 73 70 82 57 64 57 76 62 69 44 51 58 60 59 72 68 53 58 60 46 50 48 50 46 53 45 58 49 69 53 38 49 59 42 41 57 64 54 47 42 57 58 67 52 51 70 57 45 43 49 65 53 44 39 44 53 58 53 38 53 39 47 56 57 49 55 50 41 49 43 43 50 59 42 52 54 49 46 40 50 52 60 64 37 38 45 56 52 39 46 59 46 50 44 39 40 49 45 37 44 34 35 49 38 32 39 45 41 43 38 41 35 37 49 42 32 34 27 48 44 42 43 48 43 43 38 45 39 41 53 44 39 28 36 39 36 33 32 30 26 36 53 39 48 47 37 35 43 47 37 36 45 45 40 57 45 48 68 48 54 54 50 46 34 50 53 37 48 39 38 43 49 52 47 41 38 45 34 43 33 42 39 39 43 34 44 49 37 50 39 24 39 49 36 37 35 46 34 41 42 45 27 26 34 37 25 38 44 33 38 32 45 50 36 35 38 47 40 32 37 29 33 41 44 57 34 33 57 37 42 58 32 88 100 152 161 119 102 104 97 41 34 33 23 26 26 34 25 48 36 30 40 35 30 34 32 40 32 39 29 35 34 25 44 37 35 32 42 50 64 40 54 47 51 26 31 26 32 29 30 36 26 30 21 29 31 34 35 16 38 29 19 26 17 38 32 28 27 23 39 30 37 32 34 38 29 22 28 32 35 25 38 27 36 35 36 30 25 20 42 36 27 30 30 35 27 35 31 34 45 33 32 36 30 33 31 40 30 29 26 15 26 34 27 30 39 24 33 30 32 26 30 24 32 23 23 28 24 24 33 16 26 25 25 27 34 19 20 18 23 28 20 28 21 25 22 24 22 30 25 36 24 31 34 29 22 21 36 26 42 23 31 25 26 17 33 24 19 27 26 23 27 28 26 35 36 32 26 35 28 26 19 25 34 36 34 28 36 38 28 28 32 36 31 34 33 35 32 29 37 25 29 25 32 26 28 30 27 26 27 19 17 21 28 26 29 34 22 20 41 21 34 29 21 17 26 34 27 17 25 27 42 28 20 19 24 26 20 17 23 20 22 28 21 20 23 28 27 26 22 21 26 19 30 26 42 23 34 23 26 28 28 28 20 15 20 29 20 16 19 31 22 30 24 26 29 36 29 18 28 31 35 22 23 24 31 33 27 19 26 32 32 21 21 26 29 37 26 21 23 31 32 17 18 19 23 23 31 28 19 28 19 32 30 32 29 37 31 17 29 32 28 21 25 22 
];
B = [
0 0 0
 186637 55457 131180
 89347 26138 63209
 303957 105612 198345
 192956 60660 132296
 113158 33982 79176
 297276 105968 191308
 235139 76836 158303
 131561 41189 90372
 399137 142523 256614
 409822 135564 274258
 74192 22657 51535
 1169842 419308 750534
 156658 53242 103416
 50394 16204 34190
 277864 114825 163039
 89249 34524 54725
 26717 8931 17786
 306180 127803 178377
 24265 7853 16412
 25102 8795 16307
 5950 2014 3936
 182 64 118
 5651 2155 3496
 457228 195666 261562
 28888 10035 18853
 37148 13998 23150
 479007 208123 270884
 26061 10198 15863
 55925 22029 33896
 741662 310698 430964
 52115 20747 31368
 91681 37730 53951
 537399 245029 292370
 338784 153258 185526
 562110 261195 300915
 1070978 493800 577178
 867181 366843 500338
 518379 235731 282648
 1254686 591512 663174
 498888 203448 295440
 34030 14172 19858
 1185119 547420 637699
 17948 7382 10566
 32376 13297 19079
 1629038 784767 844271
 33491 14204 19287
 403714 165571 238143
 2277809 1195747 1082062
 396735 166929 229806
 17 7 10
 16185038 8922271 7262767
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
112 60 2 0
139 15 0 2
232 18 0 0
348 21 1 0
168 26 1 0
178 40 16 0
560 51 31 5
2691 86 61 26
12874 114 88 24
49860 161 125 55
124147 175 151 75
300970 263 194 137
651892 298 297 200
1291362 415 375 311
1929775 551 547 428
2183051 719 744 718
1819002 1042 1127 1093
1218464 1468 1452 1554
718628 2071 2006 1967
366491 2863 2481 2385
142597 3631 2744 2891
34561 4276 3062 2979
9777 4438 3362 3153
7501 4303 3464 3355
6842 4520 3521 3800
6325 4880 3696 3846
6849 4563 4001 3839
6108 4670 4093 4028
6068 5088 4372 4206
5780 5002 4683 4516
6016 5415 5022 5141
6803 6049 5523 5542
7616 6650 5853 5803
8110 7250 6249 6207
8497 7615 7117 7161
9067 8464 8058 7911
10119 9344 8916 8901
11024 10407 10017 10186
11984 11584 11381 11351
13110 12906 12731 12716
14827 14468 14425 14394
16659 16470 16680 16284
18820 18750 18856 18720
21502 21659 21259 21301
24330 24218 24301 24179
27805 27881 28141 28317
31817 31990 31784 31430
35466 35628 35251 35236
39623 39405 39758 39338
44152 44170 43729 43576
48403 48296 48161 47847
51492 51835 51641 51472
55454 54713 54494 55039
58119 58511 58628 58123
62058 61902 61964 61967
65061 64757 64504 64710
68973 68852 68962 67871
73537 72982 72999 72423
77004 76537 76058 76450
80360 79882 80042 80188
83769 84412 83410 83334
84138 84269 84176 83991
80917 80596 81356 81156
70241 70644 70583 70546
51904 52270 52527 51825
29074 29717 29295 28729
13250 13593 13386 13172
8311 8317 8483 7655
7378 6628 6709 6390
6113 6092 7092 5644
4658 4703 4354 4880
3464 2979 3233 3451
302 331 244 264
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
