A = [
1247747 1160483 16533229 818055 805568 770904 719572 785986 646032 579887 583109 471939 457435 452493 450861 450489 447071 447896 446449 441959 437370 437167 433602 434392 447533 681132 688405 704253 941743 947093 959128 967064 966325 980412 979966 971904 969647 965116 958895 949157 945339 942542 931503 925462 921532 915138 905614 906859 899200 889836 888315 876850 874304 867112 858869 850964 846048 842742 832595 826431 824837 816797 810096 805329 797330 792185 786839 780218 776348 770188 766724 764734 760914 758364 755912 754442 748411 743275 736029 733086 726424 719067 712225 707201 700118 693193 686954 679035 671702 665316 658955 649852 643945 636493 630456 624225 617320 611214 604623 598689 592534 587223 579646 572758 567950 561331 555412 548773 544717 537396 530802 525004 521248 514363 507883 502330 495791 492424 484266 480090 473555 467155 463055 456959 451022 445246 441746 436050 429790 425396 419347 413920 408859 404165 399107 393975 390221 384120 379021 375222 371408 365844 360752 355368 351814 346620 342971 337411 334636 329452 324450 320907 317459 312305 307544 304606 299952 295772 292520 287287 284725 279551 276374 272507 269066 264406 261116 258133 255466 250834 246791 243358 240448 237996 234886 229924 226411 224338 221214 218603 214273 211555 208244 206064 202024 200397 195954 194259 191303 188319 186097 182765 180284 177388 174598 173101 170379 167798 164459 162173 160560 157342 154827 153471 150282 149017 146839 144572 142054 140210 137972 136006 133232 131939 130653 127568 125950 123605 122116 120269 119056 116194 115298 112567 111635 109425 107995 106239 104610 103203 101342 99449 98890 96801 95256 93464 92112 90972 89465 87742 86717 84986 84195 82376 81357 79747 79137 77301 76370 74774 73608 73091 71720 70444 69601 68298 67427 66498 65659 64436 62507 62045 61464 60069 59229 57791 56937 55653 55257 54112 53165 52236 51421 50927 50004 48763 48264 47072 46494 45545 45145 44428 43859 42859 41987 41509 40720 39945 39223 38505 37863 37005 37133 35722 35531 34797 34031 33559 33277 32244 32072 31513 30815 30437 29757 28966 28798 28215 27883 27541 26923 26295 25840 25284 24879 24517 23869 23915 23298 22922 22607 22194 21617 21534 20969 20701 20153 19720 19640 19349 18770 18650 18284 17883 17435 17057 16944 16595 16072 16287 16048 15648 15333 14941 14783 14614 14145 14081 13586 13249 13277 12996 12469 12419 12277 11965 11971 11565 11389 11319 10940 10799 10674 10331 10101 10088 10113 9806 9627 9247 9154 9067 8958 8804 8544 8445 8250 8106 7945 7797 7833 7554 7447 7059 7146 7017 6970 6872 6546 6523 6478 6202 6066 6193 6083 5725 5884 5587 5603 5393 5462 5228 5240 5135 5021 4872 4835 4588 4746 4590 4344 4392 4349 4109 4233 4026 3974 3930 3961 3801 3793 3784 3630 3546 3450 3397 3381 3344 3285 3172 3143 2995 3065 2906 2857 2815 2788 2692 2691 2643 2593 2497 2477 2463 2442 2397 2333 2256 2288 2187 2146 2114 2140 2028 2070 1949 1974 1854 1886 1844 1868 1795 1756 1745 1707 1679 1723 1662 1618 1575 1516 1502 1499 1503 1402 1492 1438 1415 1362 1352 1279 1299 1280 1322 1184 1195 1153 1158 1135 1127 1195 1077 1158 1050 1054 987 1060 1028 932 967 951 940 917 872 929 873 861 854 867 849 807 807 789 755 755 763 843 717 712 730 692 725 652 685 685 602 696 641 600 664 621 632 596 587 612 618 558 571 564 593 524 562 507 469 522 529 528 518 505 485 482 480 465 461 472 457 465 434 434 434 410 434 445 402 357 418 406 390 422 376 366 377 382 377 363 364 358 382 334 377 365 353 332 355 311 350 294 350 308 319 290 318 312 301 325 307 337 304 295 293 281 298 282 294 282 298 289 270 289 239 252 274 233 261 256 257 259 248 216 239 254 250 220 247 242 233 197 218 226 232 191 217 226 214 244 203 232 208 218 202 229 194 212 214 215 189 227 224 209 202 225 177 175 226 187 181 204 208 186 183 200 166 193 174 187 184 206 192 161 182 182 160 161 180 183 171 177 176 184 149 167 184 171 130 168 159 155 156 155 145 185 187 173 169 144 152 151 159 140 153 137 152 151 141 156 151 156 135 145 123 137 145 148 144 144 137 137 148 117 146 138 128 148 137 107 126 147 127 127 131 133 108 122 138 121 118 140 110 125 127 114 127 119 106 133 144 117 110 113 127 127 134 114 139 143 115 115 115 132 111 115 96 122 124 98 125 113 107 115 114 115 125 104 114 111 115 88 107 82 114 99 106 90 113 103 105 96 91 99 104 79 111 92 101 95 110 94 90 94 101 93 104 77 81 106 94 110 80 82 101 81 75 99 87 71 88 77 81 97 76 75 93 80 72 81 96 102 77 92 81 88 80 60 66 93 65 85 77 73 78 60 89 71 82 80 62 65 80 81 80 79 77 69 75 64 85 84 64 64 56 69 77 61 71 59 66 70 68 65 60 80 74 52 59 62 48 60 61 71 70 74 68 67 57 64 58 64 63 69 55 68 53 63 51 57 56 58 58 54 51 70 52 50 63 56 56 65 60 51 60 60 65 53 42 54 57 48 49 66 49 35 51 63 45 48 70 69 53 64 48 46 55 50 42 47 53 56 55 39 51 41 41 52 56 50 56 49 66 44 62 40 58 45 47 57 51 41 48 49 47 39 35 54 55 39 53 49 34 41 30 41 42 40 55 40 50 41 58 47 49 41 23 37 44 38 45 43 44 42 43 35 37 36 37 42 45 42 43 42 34 54 33 41 37 27 32 43 28 30 33 39 44 39 25 37 30 31 32 31 30 37 35 35 40 36 36 32 30 29 37 36 33 42 38 46 22 28 28 27 29 35 35 26 45 34 36 24 32 22 34 27 30 30 35 28 29 28 32 21 32 33 31 32 30 35 43 30 26 26 28 29 21 29 25 29 29 30 33 22 31 24 25 29 26 37 40 27 31 34 28 26 29 17 31 19 21 28 23 25 27 24 24 33 23 23 16 22 23 31 29 23 20 22 21 10 27 28 23 28 24 24 31 21 23 23 22 17 19 23 20 20 20 19 19 28 21 20 16 25 25 16 22 19 18 14 14 22 22 25 20 18 20 17 26 24 16 21 22 13 17 27 20 24 15 26 23 20 24 16 21 18 25 19 18 13 16 15 18 10 18 18 24 24 15 18 18 14 23 18 12 16 18 17 15 17 20 12 11 28 19 18 16 11 17 15 24 17 12 12 18 14 17 11 11 10 12 14 23 12 14 20 10 7 15 11 12 13 8 15 16 17 10 13 13 20 12 7 15 19 10 11 12 22 8 13 17 9 12 11 12 10 4 13 13 12 14 17 10 9 13 12 10 13 11 5 17 8 8 10 9 8 13 13 12 16 15 11 12 12 14 15 21 6 9 13 16 16 15 10 8 8 10 6 10 7 10 15 11 16 6 11 9 9 13 17 9 11 10 10 13 13 7 11 7 12 14 11 11 3 8 8 7 9 8 16 2 9 15 8 15 6 11 9 5 10 5 5 10 10 8 9 14 4 5 6 7 11 7 13 5 7 8 10 8 8 4 6 4 7 12 3 10 8 4 6 5 10 5 11 6 11 9 6 7 6 5 8 5 6 4 6 10 4 4 4 5 5 8 2 4 4 9 6 6 8 5 11 5 4 4 4 8 7 5 9 11 9 9 9 7 5 3 4 5 4 4 8 6 5 4 6 9 5 8 6 3 4 6 6 7 6 5 8 4 7 6 2 7 3 7 3 4 4 4 6 5 6 7 3 6 7 4 4 7 2 4 7 3 5 5 6 6 5 3 2 5 2 4 4 6 5 5 7 5 4 4 6 3 5 12 4 5 6 2 9 3 5 5 3 1 5 6 2 3 5 2 6 5 4 6 5 5 2 3 1 4 3 2 4 4 3 2 5 2 3 9 4 1 5 7 1 4 6 6 5 1 4 5 3 3 5 2 0 6 5 1 5 2 3 6 2 2 9 4 3 5 3 1 3 4 4 2 3 5 1 5 5 6 8 4 1 2 1 1 6 2 1 4 0 2 1 1 2 3 6 5 7 6 0 2 4 3 5 1 5 5 3 5 2 4 3 1 4 3 6 5 5 1 2 1 5 6 5 2 2 1 2 0 3 5 5 3 2 2 1 2 3 3 2 5 4 2 7 4 6 4 5 3 3 0 1 7 3 2 4 3 2 1 0 1 7 2 0 3 2 2 4 3 1 1 4 2 4 2 2 5 3 2 2 0 0 0 7 1 3 1 2 2 2 1 1 0 2 2 3 2 5 3 4 2 3 2 5 1 0 0 2 0 1 3 2 3 2 2 2 3 0 0 1 2 1 2 3 2 0 1 2 2 0 2 1 1 2 3 1 0 4 1 2 2 1 4 1 1 3 1 2 4 1 2 2 3 3 1 2 2 2 2 3 4 1 0 2 4 2 1 3 2 1 1 0 2 1 3 5 2 1 2 3 0 1 1 3 3 4 1 2 2 1 4 0 2 2 4 3 3 1 0 1 2 1 1 2 1 4 0 2 1 0 2 3 1 1 0 1 1 1 1 0 0 4 3 2 3 1 1 1 3 1 4 1 2 2 2 1 1 0 2 0 1 1 0 2 1 4 1 0 1 1 1 3 1 3 0 1 3 0 0 0 2 2 2 1 1 1 2 2 1 0 0 2 3 4 2 1 4 1 1 2 1 0 0 0 1 0 0 0 0 1 0 0 0 2 1 0 1 1 1 0 2 3 3 0 0 2 0 0 1 0 2 2 0 1 1 1 0 0 2 0 0 0 0 2 0 2 1 2 0 3 1 3 0 0 2 1 0 2 2 0 0 1 2 2 1 0 1 2 0 0 1 0 3 0 1 1 0 1 0 1 0 1 1 1 0 1 0 0 0 2 0 1 2 3 1 0 2 0 1 0 1 1 1 0 0 1 1 0 0 1 2 2 3 3 0 0 0 2 1 0 1 0 0 1 1 1 1 0 0 1 0 0 3 2 0 0 0 0 0 1 0 
];
B = [
0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 817815 688630 129185
 264258 226600 37658
 1726001 1461912 264089
 809457 693613 115844
 2049796 1746531 303265
 702260 613565 88695
 1132187 979493 152694
 3543093 3060186 482907
 984436 862464 121972
 2060189 1799452 260737
 3565834 3085915 479919
 1261999 1107081 154918
 2376026 2077572 298454
 2841211 2459205 382006
 877585 770694 106891
 2621438 2301472 319966
 3253345 2829054 424291
 970670 846970 123700
 2892152 2561485 330667
 6262665 5493112 769553
 167087 145470 21617
 5541606 4933566 608040
 9378562 8292138 1086424
 510982 447764 63218
 4 4 0
 15180937 13519722 1661215
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
115 222 0 1
10 26 0 0
17 54 0 0
14 51 0 0
5 41 5 0
14 49 674 35
447 68 1901 158
6248 67 2234 359
41368 89 2805 552
158099 82 3799 1001
377588 130 4224 1464
883874 239 5466 1999
1821297 364 6384 2891
3423203 716 7583 4083
5023942 1328 8550 5685
6058631 2187 10544 8448
5587008 3435 13082 11855
3964241 4976 17225 16643
2122664 7574 22828 22789
760249 10966 29498 29754
177382 16644 36363 36579
57381 23784 43902 44067
53971 33869 52348 52345
61957 46243 61533 61596
72388 60333 71643 71771
82715 75905 83270 83637
94333 91995 95816 95515
107357 106616 108656 109246
120243 121918 121780 121996
132638 135847 134465 134250
144073 147949 145827 146240
153347 157919 155623 155431
160778 166708 163749 163563
166051 172724 170033 169058
170049 175852 172649 172753
172304 177397 174116 174053
171623 177195 174330 174988
173412 176239 173981 174503
172486 175637 173378 173889
173258 175426 174168 174080
175134 177024 174994 176853
178417 180219 178522 179331
183910 184925 184417 185666
190964 192041 190503 191785
199762 201541 200666 200785
210327 211552 210761 211260
221996 222244 222336 221476
231979 233275 232039 232232
239867 241392 240728 241445
246506 247548 247445 247063
248731 250027 249396 248529
246173 248553 247332 247844
239781 240958 240758 242030
231388 232080 232150 232451
218096 219375 218890 219509
203251 203425 202549 203826
184348 185009 185725 185020
166580 167385 166444 166316
148194 148875 148855 148268
131869 132871 132470 132597
119118 119556 119111 118524
105191 105208 106100 105904
96510 96447 96646 96871
90868 91079 91190 91096
87340 88115 87707 87533
86209 86074 86171 86371
89654 90189 89806 90110
105831 104413 104828 104918
95628 96455 96249 95741
100784 100802 100967 101420
94659 95237 93782 94552
83773 83438 82908 83462
88840 89353 89227 89504
59484 59537 59884 59383
49128 48946 49368 49248
39257 39412 38791 39299
31959 31896 32083 31622
27334 27399 27431 27201
23054 23679 23009 23053
18099 18333 18437 18397
11763 11763 11816 11723
5747 5688 5810 5832
279 258 283 305
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
