A = [
112096 109937 294177 70874 69649 66950 64860 66623 69584 67845 74024 95135 118144 128814 160523 192877 200468 207083 207801 203419 203426 196083 187334 191642 198005 250976 267142 277717 330230 305157 306528 309605 284300 288835 291683 293112 286275 288791 285791 276388 284609 282612 281286 293012 291421 287133 287610 282133 274025 273759 269053 264583 274931 275324 268942 277581 277662 269251 276158 274024 266327 273986 273063 265633 273981 273313 266278 275328 269526 261797 268891 264854 258590 268140 263358 256738 261664 259582 252348 257160 255511 247053 251674 248837 240199 247158 243092 236336 242858 238531 227911 231851 229226 223143 227704 223934 218210 223861 218340 211684 216411 213538 204784 208912 205189 198954 202761 200224 193505 197014 194627 187534 188954 186964 180842 182399 180057 176206 178250 174959 168679 174034 167863 163430 165331 161975 157795 159100 157457 152451 153997 152021 146722 149300 145065 140420 142106 140161 136586 137674 136260 131900 132551 130845 125916 127493 125925 122022 125189 121918 118352 120401 118534 114749 115590 113234 109729 111302 108705 106235 107297 106045 102772 104291 102286 98350 98708 97696 93612 96293 94885 91503 92064 91200 87718 88392 87582 83827 85250 84345 80963 82359 80994 78479 79584 77362 75891 74681 74707 71280 73098 71894 68650 70493 68893 65936 67048 65585 63619 64313 63368 61110 61801 60815 59064 59526 58735 56003 57112 55714 54476 55125 54081 52029 52777 51886 49840 50563 50009 47954 49086 47702 46288 46699 45754 44531 44450 43696 42169 42450 41732 40452 41189 39875 38918 39427 38725 37383 37177 37204 35984 35926 35546 34227 34886 34210 33059 34114 32652 31508 31838 31498 30284 30489 30315 29155 29402 28730 27854 27956 27764 26960 27178 26470 26200 25631 25329 24828 24547 24085 23373 23725 22982 22192 22224 22011 21452 21428 21138 20647 20856 20512 19778 20162 19486 18841 18923 18362 18015 17993 17851 17324 17307 17431 16155 16206 16177 15803 15853 15543 15152 14839 14884 14298 14433 14162 13778 13951 13613 13391 13237 12785 12855 12517 12465 12037 11958 11799 11595 11554 11291 10951 11254 10912 10623 10506 10257 9890 10211 10316 9693 9789 9629 9448 9318 9247 9017 9096 8950 8511 8551 8567 8417 8245 8035 7805 7728 7584 7523 7651 7445 7107 7124 7059 6768 7037 6662 6534 6581 6588 6429 6355 6404 5974 5950 6109 5920 5792 5725 5604 5557 5597 5385 5308 5185 5208 5247 5014 5149 4905 4885 4869 4936 4913 4773 4910 4716 4700 4565 4579 4322 4314 4296 4242 4190 4180 4174 4068 4046 3912 3777 3965 3873 3969 3711 3678 3720 3542 3617 3514 3266 3422 3349 3538 3306 3333 3388 3179 3111 3162 3035 3188 3030 3041 3014 2904 2965 2784 2889 2885 2865 2863 2776 2677 2879 2673 2647 2664 2723 2596 2547 2507 2629 2508 2447 2435 2437 2371 2487 2469 2392 2316 2291 2274 2380 2122 2417 2172 2306 2228 2239 2203 2112 2256 2048 2209 2028 2096 1931 2068 2055 1989 1897 1969 1938 1984 1933 1920 1926 1909 1803 1853 1796 1852 1876 1898 1849 1786 1770 1891 1867 1811 1656 1882 1704 1720 1792 1782 1747 1611 1796 1706 1625 1692 1623 1660 1617 1664 1663 1656 1680 1610 1580 1592 1547 1584 1543 1577 1454 1595 1467 1570 1448 1530 1484 1393 1476 1408 1481 1459 1377 1466 1397 1452 1412 1332 1446 1290 1344 1430 1374 1371 1359 1311 1383 1343 1384 1320 1499 1341 1367 1220 1313 1312 1292 1227 1315 1275 1399 1235 1242 1238 1302 1299 1299 1349 1362 1255 1440 1251 1229 1221 1292 1357 1359 1306 1240 1166 1214 1333 1257 1184 1231 1106 1179 1201 1107 1187 1186 1143 1201 1254 1213 1168 1242 1268 1260 1258 1197 1219 1098 1152 1130 1065 1145 1113 1101 1149 1158 1132 1176 1106 1128 1105 1104 998 1076 1083 1106 1080 1134 1003 1075 1024 1069 1095 1043 1053 1043 1130 1119 976 1002 964 1014 963 928 970 970 966 916 852 934 936 954 955 957 945 999 940 947 965 922 881 905 933 958 898 925 880 970 853 926 987 955 955 936 864 880 980 820 850 773 805 796 920 792 905 856 885 791 866 824 883 843 795 792 849 862 735 849 861 715 844 766 807 839 719 744 806 715 719 784 756 765 737 848 813 708 834 744 751 720 725 738 727 806 705 747 730 734 726 753 737 804 734 748 800 748 793 711 719 744 761 838 731 833 796 782 842 863 799 824 890 776 942 842 773 834 659 778 811 783 799 794 777 792 701 821 822 693 759 834 739 707 772 778 786 770 784 759 743 737 714 672 720 808 664 636 607 742 747 768 624 725 639 728 632 574 590 633 556 586 568 603 596 660 593 649 689 736 628 627 625 655 646 659 549 570 579 581 602 671 614 566 571 605 626 599 664 601 637 563 587 571 572 586 597 537 564 561 614 548 550 593 603 548 681 567 548 627 579 562 640 554 547 599 632 506 639 528 610 597 489 592 594 469 630 573 595 516 522 531 537 481 533 504 520 533 552 640 454 516 480 573 453 502 497 498 531 457 462 499 470 532 575 529 500 533 497 508 539 457 504 512 426 553 543 483 553 537 475 527 512 508 556 480 539 535 458 438 387 477 458 526 448 481 477 491 532 531 490 512 568 481 481 464 601 487 436 491 420 451 449 490 492 455 454 468 487 437 457 416 416 464 509 554 488 550 402 511 432 413 438 444 372 467 443 409 393 428 384 551 362 384 422 477 461 457 423 444 412 407 461 473 437 462 471 609 432 452 544 557 558 618 486 511 572 477 417 417 387 365 422 304 344 411 368 379 361 355 377 452 411 432 328 321 368 400 336 355 386 380 331 323 387 376 398 382 350 347 318 351 324 371 370 383 421 402 401 331 315 348 302 321 309 253 287 299 340 380 299 319 267 256 291 309 279 245 294 289 265 298 289 234 256 282 283 317 237 275 277 286 229 275 274 242 242 213 302 241 263 253 288 259 285 344 263 297 292 259 286 306 318 255 297 296 295 266 344 351 289 324 424 273 325 321 539 333 341 363 257 281 303 333 252 232 290 301 249 299 310 384 392 335 371 318 271 330 204 236 369 293 268 295 276 277 305 303 229 263 265 278 309 218 214 256 234 274 225 217 263 208 174 224 184 153 177 176 175 171 147 146 159 174 148 195 186 170 192 146 217 182 174 191 183 183 150 163 191 192 187 197 155 145 198 169 193 160 159 165 176 148 145 179 182 188 211 187 170 147 170 162 174 132 160 138 154 132 137 146 142 131 142 120 161 102 144 134 134 126 155 138 167 170 143 159 112 145 164 184 160 168 131 168 146 141 176 146 124 134 153 147 131 150 104 102 107 140 130 138 125 100 142 126 105 95 114 98 103 129 114 121 160 136 146 152 107 116 144 142 123 121 136 108 100 115 105 128 114 122 128 120 117 110 113 160 135 122 160 134 108 103 94 134 123 145 161 117 130 131 103 154 142 136 133 127 112 147 125 113 130 92 134 130 159 128 124 118 102 115 139 105 144 172 134 145 114 157 120 141 110 107 127 111 121 142 109 95 138 129 167 114 109 125 106 106 87 130 101 124 141 112 141 105 85 101 101 109 118 113 101 93 117 89 90 103 94 144 116 137 116 103 104 131 118 159 97 185 99 142 128 154 128 112 130 152 80 99 101 122 113 89 74 116 109 78 98 111 99 119 81 88 68 117 132 79 95 99 99 81 116 121 78 83 93 64 67 86 43 86 82 61 72 82 94 62 84 63 58 80 85 78 77 88 112 71 83 91 114 140 90 112 104 101 90 99 74 98 109 93 81 96 105 112 98 85 87 90 86 126 83 93 77 75 76 52 44 70 86 96 78 88 98 94 86 64 65 70 62 62 51 59 89 78 79 65 60 66 98 83 72 41 71 76 53 63 65 88 61 54 79 57 60 48 85 75 42 55 58 71 53 68 34 67 44 47 60 48 42 66 55 33 44 56 43 48 32 43 39 35 65 37 45 50 45 42 35 45 48 33 50 52 38 50 46 46 64 47 45 46 48 50 65 55 49 46 49 32 65 64 48 55 39 60 83 64 37 59 47 61 57 41 53 47 50 68 46 62 41 38 36 41 53 48 50 53 60 35 62 62 40 53 45 48 51 49 63 46 51 38 49 45 59 48 54 41 31 36 52 51 43 33 41 43 35 31 47 43 40 38 29 55 33 36 44 40 37 46 52 44 26 58 55 47 38 49 37 49 41 56 53 32 43 36 47 27 32 48 40 41 50 46 21 61 38 37 68 36 62 45 24 30 30 50 17 47 28 34 47 38 28 46 55 35 38 38 25 62 64 42 40 48 45 45 57 48 42 51 48 75 55 38 52 45 56 49 43 52 110 124 72 43 87 82 56 66 58 75 88 58 76 63 43 55 67 77 53 62 60 100 63 69 65 90 89 98 115 60 58 69 62 71 44 57 49 57 48 46 63 85 48 48 58 46 51 44 65 48 48 53 43 26 43 53 38 47 45 35 37 33 45 41 33 37 37 25 31 15 35 27 49 24 49 30 34 41 27 40 41 42 33 34 44 32 24 32 54 44 28 41 38 40 27 39 26 43 50 32 35 34 32 48 23 40 28 40 58 42 29 50 37 53 42 51 38 60 41 51 42 57 53 60 51 63 49 50 27 53 45 38 38 31 40 25 43 24 40 22 44 18 30 26 20 38 63 31 25 18 12 22 35 15 22 36 27 43 27 29 21 28 23 15 26 29 20 29 31 22 21 18 26 21 26 17 18 16 17 22 13 16 22 21 20 29 22 23 25 26 30 21 22 19 17 18 15 21 7 18 16 14 28 26 24 24 10 28 35 22 26 17 23 16 23 27 27 16 25 20 25 22 11 25 37 20 24 33 24 30 29 28 15 45 27 24 25 26 14 17 20 16 15 25 16 26 14 12 15 18 19 21 15 13 11 11 11 14 16 18 16 9 12 24 21 13 19 19 15 17 15 17 23 25 17 15 14 6 21 11 28 16 9 14 27 19 20 22 14 19 24 23 29 18 15 26 19 18 37 27 37 14 33 15 21 11 26 35 26 24 16 
];
B = [
0 0 0
 64436 14120 50316
 74156 16994 57162
 78759 19709 59050
 67238 15590 51648
 76347 18527 57820
 90779 22519 68260
 99278 24517 74761
 112546 28608 83938
 141809 39770 102039
 108636 30212 78424
 276551 98579 177972
 65391 19620 45771
 55468 17772 37696
 39782 13129 26653
 30160 9197 20963
 21723 5929 15794
 24602 7100 17502
 17582 4700 12882
 25607 7029 18578
 24230 6590 17640
 40395 11486 28909
 39141 10685 28456
 46584 13773 32811
 38983 10753 28230
 52519 15207 37312
 47461 14405 33056
 94807 30993 63814
 31279 10539 20740
 87624 29275 58349
 37651 12930 24721
 36516 11995 24521
 31074 11355 19719
 37563 13981 23582
 29238 10502 18736
 32614 12226 20388
 31231 11176 20055
 26471 10131 16340
 37399 14174 23225
 33205 12785 20420
 28914 11661 17253
 41882 15372 26510
 27807 11548 16259
 65849 24058 41791
 35089 15101 19988
 25164 11181 13983
 34152 14096 20056
 36766 16490 20276
 40368 17071 23297
 43728 19908 23820
 29436 13115 16321
 33103 14920 18183
 46018 20967 25051
 32169 14222 17947
 59430 28876 30554
 43724 19406 24318
 58658 24708 33950
 35703 18553 17150
 46664 21179 25485
 90516 48188 42328
 17580039 11052266 6527773
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
0 9 0 0
0 1 0 1
1 0 0 0
1 2 1 1
0 4 2 2
5 3 11 5
14 1 31 35
121 6 52 59
1933 11 75 51
13672 12 113 76
54542 21 137 124
189707 30 215 163
407418 53 308 256
575758 106 451 424
603098 236 705 723
583487 413 1217 1155
491402 781 1784 1784
333953 1177 2571 2540
165567 1837 3558 3476
46704 2556 4517 4496
10165 3716 5583 5817
7689 5024 7100 7144
8879 6697 8482 8549
10337 8698 10122 10299
12528 10847 12051 12004
14730 13172 14097 14252
16942 16575 16377 16594
19659 19553 19317 19404
22638 22400 22297 22202
25994 25907 25523 25674
28833 28923 28764 28821
32472 31908 32106 31774
35468 34984 34374 35043
38155 38177 37573 38033
41084 40994 40730 40333
42773 42891 42934 42916
44663 45596 44723 44715
47224 47945 46895 46889
49155 49857 49335 49220
51972 52650 51850 51439
54546 53721 54131 54210
56828 57298 57189 57405
59821 59767 60289 60285
63878 63392 63796 63215
68096 67602 66714 67564
72506 72589 71837 72044
76380 75623 75483 75721
80947 80729 79825 79942
83452 83665 83374 83253
86906 86729 85933 86108
88427 88444 88130 88569
91066 90264 90466 90815
91376 91719 91239 92039
90634 91512 90673 91416
89755 90338 89739 89657
86750 86915 86592 86899
81814 82778 82385 83057
74365 74299 73105 74679
64650 65054 63974 65161
53087 53658 52806 54043
42894 44638 43553 44036
28402 29700 28636 29376
12078 12970 12389 12586
2429 2661 2577 2411
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
