A = [
475604 437721 835368 485023 459173 454968 428386 454987 447363 437701 456758 464918 481167 493850 495919 502411 502860 510610 512828 501088 507781 512940 506524 511776 518815 841772 840918 852961 1175741 1176814 1222677 1244309 1243204 1280681 1291622 1280052 1264385 1249147 1241712 1228759 1222787 1227653 1228086 1235433 1237876 1218208 1203406 1192338 1166536 1151205 1145602 1133079 1143254 1142459 1136525 1131324 1122949 1112066 1086482 1069611 1064842 1049007 1050143 1049192 1045451 1046262 1034105 1017433 1003279 984036 970048 958682 947398 944353 940143 933662 922942 913380 896392 881145 863311 850462 841652 830074 825224 817871 807092 789741 777525 765936 751484 738192 728568 717467 712091 706842 700168 694951 684032 673200 662029 651162 640910 632858 624365 620199 612669 605834 600783 591903 580352 571614 562525 553077 546631 542325 536749 529665 524326 516702 509530 499395 490706 482736 475246 470321 463349 458724 453316 447226 441195 433096 425293 418707 411262 406015 400867 397226 391634 386755 381824 374654 368830 361736 354990 350142 345105 340204 333890 332173 326532 321246 315483 309571 304428 298699 294072 290617 286706 283088 279725 274886 269433 264971 258822 255930 251994 247350 244755 239848 236407 233200 228609 226228 221258 217238 212958 210384 207631 203533 200547 198010 195391 191697 188292 185467 180953 179296 175434 174193 170159 167765 164864 162075 159812 156627 154179 151319 147825 146134 144248 141786 139287 137406 135413 132894 129983 127309 124945 123509 121833 118624 117217 115179 112261 111048 109294 106998 105152 103646 101582 99019 97944 96028 94420 92444 90475 88496 87132 85162 83783 82945 80209 79033 77796 76804 75057 73962 72684 71270 69429 68393 66980 66040 64050 63184 61947 61009 59590 58557 57395 56445 55507 54039 53402 51711 50851 50351 48975 47971 46937 46090 45268 44243 43442 42886 42121 40581 40366 39399 38822 38044 36965 36561 35645 35043 34376 33320 32814 32234 31850 31168 30705 29874 29230 28653 28201 27164 26854 26224 25806 24969 24547 24176 23705 23060 23089 22417 21810 21632 20918 20429 20215 19522 19309 18734 18483 17830 17700 17668 17056 16527 16142 16116 15401 15249 14975 14513 14465 14148 13940 13617 13099 13200 12488 12419 12095 11756 11584 11651 11334 11082 10654 10739 10374 10214 9793 9890 9483 9402 9137 8899 8758 8663 8336 8260 8158 7859 7589 7782 7473 7233 7110 7068 6752 6748 6434 6373 6273 6102 5959 5889 5860 5627 5551 5538 5271 5134 5091 5074 4877 4807 4671 4569 4514 4433 4340 4239 4144 4003 3894 3942 3811 3635 3549 3621 3442 3351 3378 3240 3309 3116 3110 3160 3011 2898 2894 2850 2685 2741 2627 2595 2668 2559 2445 2438 2372 2349 2395 2272 2208 2162 2043 2066 2023 2080 1991 1883 1965 1815 1878 1812 1767 1748 1684 1742 1684 1665 1596 1613 1544 1519 1527 1441 1451 1463 1396 1437 1319 1267 1306 1220 1266 1248 1234 1215 1130 1132 1172 1156 1069 1051 1119 1096 1073 1052 994 959 984 997 952 955 964 921 865 850 906 867 878 820 884 835 844 769 818 733 800 775 826 701 721 758 700 702 693 721 652 664 651 708 617 668 645 632 612 646 606 609 635 671 626 599 601 621 578 547 534 561 527 564 536 551 537 547 526 527 506 460 461 486 498 503 499 505 477 465 448 459 462 460 478 438 482 455 370 437 398 403 441 386 389 421 427 403 372 401 394 389 404 390 341 357 366 378 364 413 367 400 339 322 359 365 346 352 382 345 368 307 366 345 353 317 318 341 311 345 335 322 336 319 335 331 288 305 314 294 299 322 301 335 280 279 297 298 296 315 304 268 334 294 308 258 283 270 274 306 307 327 274 274 306 279 254 258 288 248 270 263 255 251 254 242 249 258 252 245 262 260 258 241 250 259 222 256 271 252 267 252 237 254 216 219 223 236 256 227 241 209 244 213 225 253 228 241 230 256 237 226 232 232 199 174 205 221 190 223 208 194 218 187 202 200 215 204 182 201 191 222 182 179 213 198 205 195 176 201 219 177 188 213 189 191 216 177 186 186 219 180 198 183 171 176 155 176 190 199 163 190 162 158 190 179 170 186 179 190 203 184 169 175 198 187 165 161 157 171 142 158 174 159 167 198 182 144 163 156 158 141 155 178 176 153 145 144 166 138 136 146 148 143 160 153 135 149 131 142 116 129 136 128 128 152 130 134 155 141 129 142 146 130 127 126 139 114 130 127 133 129 113 113 120 133 123 124 123 135 124 143 120 137 151 115 125 137 141 113 108 113 104 129 135 96 111 128 119 116 105 110 101 109 122 102 123 117 122 125 108 124 106 116 107 106 130 111 98 119 119 89 108 119 91 111 121 96 117 103 104 89 112 92 92 92 88 116 84 88 106 102 86 89 83 94 94 87 97 83 100 92 91 112 80 100 73 77 82 87 61 90 91 80 83 81 83 98 80 74 87 79 100 72 98 56 75 89 75 85 92 87 68 63 55 67 92 79 73 59 65 82 67 68 72 64 72 72 74 67 68 79 90 65 64 83 65 69 73 86 79 80 76 71 73 62 79 64 67 86 56 45 62 58 63 63 58 58 61 52 65 78 69 65 74 67 75 74 57 46 71 56 64 54 58 58 58 62 64 51 52 57 61 71 56 54 65 50 54 52 54 54 46 52 51 55 62 54 53 53 67 59 49 48 54 51 59 50 43 46 39 44 52 50 37 49 53 49 42 43 57 51 45 33 58 44 41 32 48 44 41 52 50 44 48 39 40 36 39 38 49 49 46 45 37 51 52 34 39 31 37 56 34 43 38 58 38 54 36 40 44 47 32 37 39 38 37 31 39 35 36 52 40 34 44 46 28 36 41 42 46 33 39 40 32 38 34 42 31 45 30 36 37 26 31 34 43 40 41 26 41 23 33 47 26 37 34 28 22 35 34 38 33 31 41 37 24 26 33 27 31 39 24 36 37 21 32 23 31 41 26 21 29 26 28 26 35 21 39 31 18 32 22 30 34 23 20 32 29 25 24 19 26 25 24 30 33 21 20 27 21 26 23 24 27 24 25 21 26 21 23 21 28 28 15 26 38 25 25 25 19 22 38 18 26 86 65 33 59 81 48 77 64 73 54 68 66 67 62 59 56 66 118 92 66 40 34 27 23 22 24 18 23 21 17 19 18 19 21 12 15 28 23 16 24 23 30 33 31 47 27 25 27 27 26 30 35 21 24 24 28 24 32 29 24 17 23 18 12 11 12 20 19 25 20 17 22 20 12 14 19 16 13 20 17 17 13 14 23 17 18 11 24 11 19 6 12 17 19 17 18 15 18 19 12 11 17 5 18 20 20 18 20 22 22 21 15 24 12 24 23 13 37 81 36 14 12 13 13 12 13 18 16 14 9 11 10 19 13 10 14 8 12 14 15 10 17 13 17 17 11 19 13 13 15 9 10 18 20 13 16 14 10 21 19 14 10 19 11 18 9 15 17 13 19 8 25 13 11 9 6 9 15 13 9 5 15 11 11 13 16 12 10 15 8 11 11 14 12 18 13 8 12 15 17 15 12 9 8 10 11 12 9 11 10 10 13 9 10 15 6 7 8 13 13 10 13 14 8 15 14 9 7 12 11 11 14 9 7 11 8 12 7 9 5 9 9 10 12 14 12 11 13 13 8 8 8 8 9 5 14 8 10 10 12 16 8 8 13 6 8 10 11 8 3 14 6 7 11 12 6 7 13 9 8 10 9 12 4 13 14 16 20 18 12 12 11 7 6 10 2 9 5 7 10 8 3 15 8 8 5 3 9 8 6 12 7 8 9 8 8 4 6 2 12 8 4 11 11 11 12 11 14 17 13 8 12 11 12 12 6 9 10 5 9 8 11 5 6 10 7 8 6 10 7 11 7 7 4 4 9 12 10 9 5 16 7 15 8 10 8 16 10 9 6 11 7 4 9 6 11 6 13 14 4 5 5 8 10 3 13 3 10 5 6 4 8 7 3 3 9 8 7 5 8 6 4 8 5 2 7 7 3 2 2 6 3 6 6 4 6 3 5 8 8 4 6 6 2 5 3 5 6 6 2 1 2 4 10 6 6 3 2 4 6 4 3 5 1 2 3 7 6 6 2 3 4 0 5 2 4 5 3 6 6 2 2 5 7 21 23 11 10 13 19 14 6 3 3 2 3 3 5 2 5 5 7 4 7 3 6 5 5 4 1 3 8 1 5 1 5 4 6 5 6 1 2 3 1 8 13 12 11 12 4 11 10 14 11 5 3 3 5 5 3 4 2 7 3 3 5 9 2 5 6 1 1 5 5 5 6 7 1 3 3 6 3 8 2 3 5 4 5 3 4 5 3 4 4 5 3 3 3 3 2 2 1 5 1 4 4 2 2 3 4 1 6 3 4 2 7 3 1 5 4 4 1 6 1 2 1 6 2 4 1 3 0 7 1 1 4 2 2 2 4 1 1 0 2 2 1 2 4 3 0 4 1 3 4 1 2 0 4 6 4 1 2 1 1 3 3 4 2 5 2 2 4 2 2 2 6 1 0 1 3 2 0 2 5 4 5 3 8 2 1 1 0 3 2 2 1 2 5 0 0 6 3 2 5 1 3 2 4 2 4 1 2 0 3 3 2 1 1 1 1 2 0 2 2 1 2 2 4 2 2 2 5 2 1 0 5 4 2 5 4 2 2 2 2 4 4 1 3 2 4 3 0 2 3 3 2 1 3 0 2 1 6 2 1 1 4 1 3 1 3 4 2 3 3 1 3 2 3 2 1 1 4 1 3 5 4 1 3 5 2 2 3 6 2 3 2 2 3 1 2 2 2 3 3 2 2 2 3 1 3 2 3 2 1 2 2 2 2 4 0 1 2 4 2 0 2 3 1 2 2 4 2 5 2 1 1 1 4 6 2 3 1 3 0 2 1 1 3 2 3 4 1 0 2 2 3 0 1 3 1 0 0 1 3 0 1 0 3 1 2 0 1 3 4 1 3 2 0 3 
];
B = [
0 0 0
 318544 211860 106684
 195182 132470 62712
 320415 228076 92339
 227076 157300 69776
 219185 154925 64260
 243206 173556 69650
 278492 204097 74395
 189223 137485 51738
 308059 231988 76071
 222737 164470 58267
 221687 165408 56279
 241773 182717 59056
 317874 244246 73628
 189447 144252 45195
 347900 271765 76135
 242427 187109 55318
 251674 196161 55513
 261310 204572 56738
 391891 308151 83740
 251287 197864 53423
 432526 343371 89155
 370009 292248 77761
 292020 230130 61890
 490337 385483 104854
 610852 481199 129653
 141343 111975 29368
 1189717 926076 263641
 92243 75466 16777
 157273 128555 28718
 145528 119416 26112
 238681 195620 43061
 86829 70704 16125
 574332 471204 103128
 67200 55131 12069
 155816 127961 27855
 105833 86871 18962
 201213 164628 36585
 37595 30807 6788
 714111 586866 127245
 434 365 69
 26430 21779 4651
 20856 17119 3737
 176431 145894 30537
 21813 18143 3670
 20746 17156 3590
 57554 47798 9756
 93671 77554 16117
 1218718 1004629 214089
 186487 155325 31162
 24807 20653 4154
 64447 53963 10484
 58650 49426 9224
 124009 103738 20271
 1533476 1271525 261951
 35829 29865 5964
 200562 169510 31052
 93155 79507 13648
 245082 208746 36336
 409516 345728 63788
 49950443 42710545 7239898
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
7 26 0 0
3 0 0 0
2 1 0 0
6 9 1 0
2 6 0 1
7 5 81 3
262 11 343 36
3136 20 411 121
19410 25 715 296
72198 41 1090 629
182305 57 1502 1030
429401 126 2237 1619
855080 268 3440 2697
1572894 741 5217 4675
2322465 1631 7759 7508
2850703 3241 11786 11679
2628954 4416 17094 16596
1792225 5761 23535 23634
874654 8827 32611 32428
287145 13620 41921 42253
94428 20365 52143 52712
70898 28554 61908 61237
74790 42682 71263 71264
81258 59288 81630 82267
89056 79509 93563 94327
101008 101826 107744 107545
113014 125441 121841 122046
127397 148094 138781 138082
142137 168642 154829 155243
155974 187457 170670 171027
168470 202522 184041 183866
178027 213749 194128 194126
186950 222498 202788 203381
191206 226141 205934 207661
194829 227311 209727 209824
195739 225254 208763 208958
193362 219725 205147 205736
193669 215002 203723 203463
194233 210567 200784 201614
193069 207069 199342 200002
193989 205233 200496 198820
195556 204283 199252 200987
198449 205335 201650 202362
202638 209023 205605 206660
210076 214145 213557 212617
219067 223012 221030 221331
231436 234611 232733 232599
243816 246515 245183 246074
258408 260121 258479 260076
273897 275969 273776 273616
288616 288612 287316 289138
299010 302028 299844 300780
307675 308987 308591 308594
311343 314265 312868 313575
311165 312736 311867 312585
304381 306218 304398 304113
290992 292667 290655 292315
273228 275085 274793 274227
251396 253921 252737 252609
228452 229761 229289 228751
206740 208026 207313 207257
184022 185602 184653 185880
163102 164331 163372 164280
144855 145485 144202 145324
132322 132798 132945 133414
126157 126642 126606 126355
124311 124894 124582 124686
117499 118743 118176 118087
114328 114317 114276 114208
115594 114831 114600 114707
111653 111674 111872 111594
106403 106721 106690 106725
96921 97555 97079 97400
86282 85464 85297 85537
73692 74177 73861 74220
60352 60484 60221 59861
43871 43868 43862 43954
30946 31241 31173 31168
24052 23864 23817 24070
15758 16086 16021 15984
8480 8552 8559 8586
3607 3560 3517 3522
183 174 193 182
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
