A = [
326762 344401 1312904 337567 354164 319570 312363 320372 310465 288170 287307 291421 288717 284200 282003 277621 274286 272917 269533 267475 266123 262323 261735 260309 258930 294882 293614 292554 328586 328685 329178 330267 331878 332312 331155 330557 326654 322883 320699 317295 315112 314288 311773 310423 310847 306390 304415 300548 297877 294989 292499 290352 289701 287958 285847 283908 281527 277923 276196 272592 270026 268306 267692 266518 262148 261607 259752 256534 255196 250879 249017 246772 244294 242025 241497 239663 237485 235033 232021 230058 228204 225263 223995 222345 219579 218322 215919 214007 212606 210809 207926 206346 204389 202288 200709 197600 197538 194386 194129 191058 189525 188571 185264 184606 182978 180655 178736 178702 176177 174925 172919 170478 169512 167396 166417 164445 162044 161278 159664 157778 156086 154663 152604 151752 149445 148667 146873 145305 143860 142680 140540 139236 136990 136381 135492 133414 132248 130708 129608 127850 126784 125377 124581 122856 122051 120567 119014 117582 116513 114893 114225 112286 111836 110404 108505 108376 106864 105584 104980 102945 102176 100926 99695 98010 96419 96126 95091 93947 92746 91412 90530 90557 88089 87892 86054 85176 84605 83281 82504 81301 80564 79873 78443 78041 76530 75820 74743 73774 73509 71912 71487 70415 69545 68892 68174 66979 66210 66007 65443 63731 62916 62525 61547 60509 60211 59088 58743 57399 57354 56120 55724 55309 54417 53209 52909 52407 51626 50819 50436 50049 49162 48948 47721 47006 46516 45545 44986 44978 44180 43486 42820 42456 41681 41017 40549 40202 39522 39205 38347 38157 37512 37042 36320 35999 35824 35210 34945 34375 33904 33590 32947 32621 32273 31762 31026 30967 30534 29894 29514 29136 29131 27970 27969 27819 27473 26808 26698 26046 25824 25635 25168 24929 24901 24305 24078 23578 23143 22896 22682 22665 21902 21937 21823 21119 21304 20772 20435 20521 20240 19672 19651 19207 18926 19074 18786 18391 18278 17635 17638 17605 17135 16700 16670 16598 16328 16083 15926 15678 15678 15212 15204 14847 14638 14537 14446 14193 14020 13924 13492 13055 13153 13093 12530 12553 12104 12232 12071 11682 11601 11355 11481 11124 11057 11145 10814 10695 10499 10618 10564 10072 10286 10071 9945 9968 9644 9500 9476 9358 9124 8860 8901 9203 8811 8486 8360 8306 8859 8215 8272 8035 8006 7948 7732 7783 7416 7610 7387 7310 7106 7019 7021 6834 6759 6831 6704 6674 6632 6413 6356 6177 6321 6065 6082 6125 6139 5884 5665 5949 5702 5513 5702 5565 5657 5546 5385 5432 5151 5080 4943 5083 5036 4873 4800 4886 4713 4695 4566 4574 4502 4452 4460 4386 4200 4216 4225 4237 4123 4167 3974 3948 3790 3813 3737 3787 3670 3651 3640 3515 3669 3740 3536 3500 3520 3383 3470 3326 3437 3389 3337 3149 3171 3040 3037 3013 3004 2950 2870 2796 2907 2847 2833 2874 2757 2823 2793 2610 2690 2606 2613 2583 2453 2499 2456 2489 2565 2523 2447 2304 2366 2495 2382 2269 2230 2285 2179 2140 2221 2172 2072 2025 2059 2093 2014 2023 2011 2049 2089 1979 1974 1994 1942 1957 1882 1912 1884 1960 1901 1853 1816 1756 1833 1818 1755 1819 1719 1759 1752 1680 1783 1668 1610 1651 1663 1657 1609 1599 1573 1561 1509 1546 1534 1524 1459 1427 1566 1421 1408 1411 1462 1437 1490 1473 1398 1437 1387 1415 1360 1400 1389 1441 1460 1336 1343 1414 1371 1466 1449 1530 1475 1303 1384 1339 1311 1341 1362 1349 1224 1261 1236 1231 1219 1321 1212 1317 1300 1156 1091 1112 1169 1062 1065 1224 1183 1207 1293 1198 1209 1191 1159 1111 1124 1087 1091 1117 1089 1014 1001 1061 985 1000 968 1003 1007 1068 1049 997 1033 971 1027 1002 904 893 944 933 943 901 876 922 855 858 921 909 883 860 854 794 901 836 835 837 788 808 837 777 776 727 725 794 767 787 733 774 735 746 750 734 759 730 683 778 736 709 692 698 693 687 694 693 652 680 658 697 646 708 619 696 633 604 605 686 639 623 626 613 639 615 651 598 584 584 594 642 575 596 585 584 582 581 593 568 553 578 575 553 559 548 529 543 555 540 586 582 546 555 536 547 562 537 517 515 519 495 482 492 511 502 520 508 485 475 481 477 461 514 476 465 485 417 489 494 490 505 538 504 479 497 430 476 472 479 497 515 522 528 593 748 612 540 569 557 519 474 548 583 483 487 565 527 481 533 494 556 491 486 471 479 435 477 416 426 388 381 381 430 389 404 406 454 413 440 459 472 431 509 428 426 371 438 397 394 401 416 417 395 435 388 398 448 345 399 378 371 348 392 369 372 376 360 385 371 387 322 351 382 405 345 330 332 382 314 309 318 351 326 328 337 299 337 286 304 301 329 337 283 287 318 330 283 279 303 307 316 325 323 310 323 309 327 301 282 346 320 332 296 314 287 284 278 273 307 274 296 314 275 295 273 258 231 275 275 279 243 223 226 248 269 261 233 238 216 237 273 287 288 255 253 271 272 230 285 236 248 239 254 253 239 224 244 247 203 236 231 235 237 229 221 250 228 226 244 219 184 190 185 234 228 218 226 208 229 202 187 196 195 220 197 198 205 227 230 298 237 206 196 242 213 210 206 174 179 186 204 168 182 181 156 169 163 197 196 201 189 165 169 161 152 197 205 167 170 151 177 178 167 174 186 164 197 161 181 179 160 154 142 147 166 181 143 153 154 141 166 146 129 153 124 137 135 120 121 150 175 158 130 158 129 141 148 138 139 157 135 107 146 143 133 144 132 145 166 142 140 142 120 128 127 132 150 134 150 139 135 115 116 137 126 144 119 141 138 103 114 128 118 138 117 116 119 119 109 132 130 147 121 125 124 130 138 132 126 141 115 121 118 115 140 127 125 115 125 129 131 122 110 127 127 127 136 138 130 120 125 137 125 130 142 119 121 129 114 139 103 141 119 108 111 106 105 105 114 121 119 123 103 111 132 105 120 119 124 93 103 109 98 102 123 112 97 85 105 99 116 111 113 82 106 117 110 110 81 120 97 92 102 106 102 106 100 95 125 95 102 81 101 107 101 101 103 95 97 89 91 98 97 88 97 96 102 78 98 82 84 113 101 84 86 83 90 107 96 90 81 101 84 88 101 86 98 103 98 89 84 88 81 90 88 105 87 93 114 102 105 93 97 93 75 106 87 104 91 91 89 113 83 114 82 112 104 101 92 66 93 72 87 61 88 94 78 90 83 74 97 76 62 70 82 61 63 66 60 64 70 79 63 69 76 64 88 80 75 63 68 62 65 48 78 73 73 74 55 68 83 71 63 65 52 66 49 60 56 65 51 56 58 73 48 73 64 62 57 62 65 51 61 62 58 61 55 63 77 55 62 71 75 73 70 50 57 51 52 57 75 58 56 61 46 52 50 43 59 53 50 57 58 62 60 58 64 47 56 55 64 63 74 60 73 54 59 52 59 50 54 47 50 45 49 49 71 57 59 51 47 53 54 54 48 59 33 50 51 51 63 50 40 41 44 36 36 47 43 44 48 43 43 31 53 34 47 34 41 59 51 37 38 42 33 38 45 51 43 46 41 43 40 38 51 50 48 33 42 50 35 47 40 41 55 48 40 47 42 32 47 43 33 36 30 41 31 46 24 39 31 39 51 47 39 41 46 39 44 49 31 46 50 39 40 42 35 44 30 36 44 42 37 49 39 46 37 49 43 43 40 51 51 51 48 54 41 53 53 47 54 43 53 49 50 54 29 38 45 45 51 40 34 49 47 34 51 38 34 28 40 44 38 38 38 42 43 41 23 29 38 31 41 30 31 41 30 36 46 32 30 25 39 33 43 37 20 29 27 32 27 35 23 23 33 27 33 27 29 35 33 20 25 25 29 26 34 28 16 18 26 27 18 29 33 29 29 25 21 26 28 31 26 34 34 24 35 35 31 23 25 35 21 27 28 32 30 31 28 30 29 27 19 26 36 22 20 26 22 22 35 33 18 32 22 21 28 25 27 20 22 30 19 28 21 28 33 23 17 14 26 25 21 23 19 21 21 32 18 16 25 30 26 28 24 24 31 30 19 19 23 16 21 19 23 17 31 23 19 24 16 24 26 22 22 17 15 18 30 23 18 35 32 29 26 24 22 23 38 26 30 24 27 18 30 28 23 22 32 22 19 26 28 19 27 36 21 23 21 24 26 20 25 21 19 18 27 27 21 22 26 30 36 17 25 28 32 30 26 23 30 23 26 23 19 15 23 19 17 17 18 13 15 25 22 18 28 21 21 32 24 23 17 21 22 23 22 26 22 25 29 29 27 42 22 32 51 111 111 131 95 85 74 80 28 17 20 17 21 20 33 19 21 29 10 17 24 21 20 12 16 26 26 17 24 26 14 19 16 19 25 24 33 47 23 28 37 23 37 27 22 19 18 18 21 10 14 15 22 8 13 17 15 24 18 18 16 17 24 23 14 18 24 24 19 11 12 18 20 17 17 19 18 27 13 23 15 20 25 21 23 14 15 18 19 13 18 16 14 19 22 19 29 24 18 18 20 16 17 28 21 15 15 21 11 18 12 10 13 13 22 11 17 18 13 13 14 13 10 9 12 6 13 17 10 14 25 18 16 19 9 11 10 15 17 16 15 21 22 13 14 18 20 17 19 25 15 19 19 10 12 16 19 18 19 16 17 13 15 23 19 19 14 19 12 10 15 11 22 13 17 19 21 17 16 27 19 6 16 19 17 26 25 18 16 17 17 16 22 24 7 16 17 16 8 17 14 17 23 24 12 22 13 15 20 9 12 14 19 11 17 6 14 18 10 28 13 16 13 16 22 17 23 15 19 12 13 12 14 10 18 11 7 12 19 14 18 10 22 14 9 14 11 22 14 18 10 15 14 15 16 13 11 9 18 12 13 16 9 18 16 8 9 11 16 17 14 13 9 15 20 13 15 8 17 13 23 18 12 13 15 15 11 19 18 7 14 17 14 15 22 21 16 21 16 10 13 15 17 20 23 21 14 10 14 19 14 13 13 11 13 17 15 11 22 17 16 11 12 
];
B = [
0 0 0
 119630 41124 78506
 57091 19537 37554
 199888 79622 120266
 124832 45040 79792
 72544 25342 47202
 195336 80222 115114
 153213 57680 95533
 83723 30755 52968
 260893 106072 154821
 269097 103104 165993
 48391 17142 31249
 769792 317310 452482
 102910 40526 62384
 33023 12483 20540
 184885 87011 97874
 58951 25962 32989
 17781 7040 10741
 204245 97655 106590
 16301 6338 9963
 17022 7002 10020
 4004 1593 2411
 112 37 75
 4077 1822 2255
 304609 147947 156662
 19393 7813 11580
 25634 11269 14365
 320851 158289 162562
 18305 8412 9893
 39107 18047 21060
 492606 234756 257850
 36390 16449 19941
 64611 30376 34235
 364704 187089 177615
 243130 123764 119366
 406485 210004 196481
 750207 388968 361239
 592063 286110 305953
 374759 190836 183923
 879381 462791 416590
 328494 153991 174503
 23084 10703 12381
 795844 413285 382559
 12243 5744 6499
 21769 10290 11479
 1101011 591013 509998
 22859 10915 11944
 264922 124049 140873
 1555929 895781 660148
 266733 128490 138243
 10 6 4
 10901347 6513771 4387576
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
36 47 1 1
42 11 0 0
139 16 1 0
197 21 2 0
140 27 0 0
128 26 11 1
244 61 43 11
1076 77 56 23
5968 70 79 38
23706 112 146 58
53629 136 171 80
112923 208 241 136
224357 245 345 216
464911 321 459 330
866365 461 638 511
1431316 552 903 804
1727244 803 1203 1116
1504738 1204 1620 1594
1017369 1699 1987 1981
533918 2280 2370 2418
205013 2800 2671 2758
48009 3308 2850 2858
10449 3523 2912 2851
7131 3324 3068 3053
6103 3689 3083 3405
5553 4268 3147 3369
5808 3724 3261 3300
5107 3735 3367 3445
4964 3995 3750 3686
4728 4037 3867 3740
4836 4325 4126 4115
5450 4632 4367 4440
6013 5387 4660 4698
6595 5770 5180 5201
6728 6126 5702 5708
7103 6623 6455 6224
8048 7296 7004 7238
8792 8291 8094 7972
9490 9173 8896 8918
10161 9992 10001 10111
11575 11391 11439 11276
12894 12995 13033 12787
14487 14659 14178 14354
16470 16375 16494 16441
18558 18765 18529 18619
21103 21526 21176 21847
23948 24107 24304 23677
26879 26593 26475 26752
29762 29713 29800 29804
33126 32620 32955 32487
35765 35834 35877 35835
38089 37967 37990 38100
40434 40503 40183 39871
42536 42390 42091 41992
44590 44565 45197 44624
45927 46435 45997 45896
48587 48636 48755 48506
51761 51176 50927 51302
53438 52728 52929 52955
55215 54824 55198 55180
57609 57933 57375 56865
57569 57417 57837 57908
56179 55030 55846 55372
47875 48587 48064 48459
35653 36238 36190 35347
20322 20968 20296 20263
9257 9961 9578 9378
6232 6165 6264 5631
5700 4870 4899 4706
4214 4540 5531 3992
3206 3382 3296 3483
2916 2212 2570 2610
207 225 163 142
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
