A = [
458340 421405 803763 466982 441186 438252 412945 437531 431532 421834 439543 449013 464302 476663 479192 485627 486365 493401 494785 484546 489657 492036 487429 491754 499189 812549 811353 822841 1137279 1139979 1181533 1203959 1205024 1240761 1251617 1239973 1224271 1209499 1201710 1187726 1182286 1187323 1186882 1194161 1196499 1178309 1164169 1153434 1128517 1113955 1107812 1097134 1105973 1103750 1099057 1094585 1085518 1073985 1050323 1034871 1028853 1014104 1014432 1013509 1010310 1010896 1000468 985158 971915 954238 940555 929851 919514 916636 911946 906055 895414 885320 869287 854558 837401 825468 817115 806348 800860 794917 785116 769499 757810 746431 732623 719867 710242 699321 694303 689092 682942 677765 667240 656819 645485 635113 625016 617327 608848 605114 597858 591168 586059 577235 565935 557543 548805 539330 533127 528612 523337 516493 511327 503796 496746 486978 478466 470682 463477 458540 451801 447274 442025 435914 430025 422356 414878 408332 401173 396004 390606 387162 382010 377191 372246 365312 359868 352628 346167 341416 336476 331720 325445 323871 318434 313195 307673 301929 296845 291338 286842 283409 279690 276152 272669 267984 262590 258387 252420 249829 245927 241312 238708 234069 230681 227572 222950 220441 215794 211854 207716 204998 202111 198491 195339 192941 190550 186931 183672 180695 176516 174824 170968 169764 165849 163464 160668 157908 155714 152565 150159 147430 143931 142239 140589 138009 135606 133919 131736 129244 126450 123906 121580 120246 118584 115515 114019 112075 109066 108064 106336 104002 102265 100741 98750 96370 95305 93401 91905 89967 88207 86314 84758 82973 81609 80847 78249 77002 75797 74859 73188 72031 70863 69422 67633 66588 65309 64490 62460 61625 60412 59522 58105 57081 56034 55093 54216 52723 52109 50426 49572 49055 47819 46827 45828 44954 44130 43152 42440 41800 41098 39656 39298 38423 37883 37073 36067 35653 34749 34177 33630 32518 31976 31500 31080 30420 29980 29163 28545 27958 27520 26535 26198 25598 25113 24334 23965 23598 23100 22480 22482 21861 21224 21086 20394 19927 19717 19083 18829 18275 17979 17337 17241 17183 16634 16068 15703 15685 14990 14865 14585 14140 14110 13798 13563 13226 12754 12825 12164 12081 11769 11394 11292 11314 11022 10776 10384 10422 10104 9930 9526 9588 9216 9135 8893 8654 8513 8437 8118 8028 7891 7642 7381 7558 7262 7016 6933 6846 6558 6530 6214 6188 6071 5905 5784 5711 5701 5475 5401 5369 5116 4965 4911 4901 4730 4638 4501 4405 4366 4266 4179 4092 3989 3882 3740 3798 3657 3513 3425 3501 3311 3239 3256 3117 3158 2991 2982 3036 2869 2798 2768 2741 2577 2618 2507 2492 2565 2435 2337 2343 2261 2241 2278 2184 2110 2049 1949 1978 1934 1998 1906 1799 1889 1729 1776 1718 1687 1657 1611 1670 1607 1579 1522 1539 1464 1444 1448 1374 1390 1372 1318 1360 1234 1194 1230 1149 1205 1171 1163 1138 1061 1067 1087 1091 1001 996 1057 1036 996 999 927 905 916 947 888 907 900 869 812 805 864 822 826 764 809 758 793 722 769 683 747 707 748 648 677 720 642 646 635 672 611 614 611 640 579 626 592 584 570 592 567 558 585 552 582 562 549 579 537 500 485 521 481 520 501 508 483 497 475 481 466 409 416 452 455 467 430 458 431 434 408 415 424 410 432 412 434 411 336 390 373 371 405 355 364 396 387 365 351 363 365 355 372 370 315 319 333 352 324 380 340 366 310 299 323 339 313 321 355 322 333 289 331 319 311 295 292 323 287 318 304 297 306 297 305 296 252 293 289 266 275 293 281 314 261 256 273 279 269 281 278 251 300 267 286 238 264 252 250 291 281 285 252 250 271 260 235 238 245 233 241 237 238 231 233 210 232 237 221 229 244 234 244 218 235 228 208 235 259 237 256 228 212 225 195 195 203 220 231 208 217 192 226 198 205 230 213 229 212 244 212 211 212 208 175 157 186 207 168 210 187 180 203 169 181 186 197 188 166 188 176 205 168 169 190 178 182 176 160 179 198 161 174 199 170 169 199 166 168 176 212 161 181 167 155 164 144 154 182 185 144 171 148 148 169 165 159 175 165 177 186 173 153 165 186 172 155 146 145 160 140 146 158 139 159 176 167 130 152 143 149 130 146 162 159 144 139 130 147 125 119 135 140 132 149 136 130 131 123 127 104 118 126 111 114 142 124 120 141 126 116 129 131 123 120 109 132 108 120 120 123 118 105 99 104 124 108 114 111 126 115 135 110 127 139 103 115 124 127 100 101 99 98 117 126 88 100 115 100 101 96 103 91 102 112 95 114 103 114 117 102 116 92 110 99 98 118 98 90 111 114 84 98 111 84 103 106 80 101 94 91 80 100 84 80 87 78 101 78 82 96 94 84 80 73 84 88 78 90 78 95 83 87 100 72 89 70 71 76 78 61 83 82 72 81 75 78 90 71 70 79 69 93 66 87 53 67 83 70 74 84 78 64 56 49 61 91 74 67 55 58 74 59 65 63 57 66 68 67 64 63 73 80 62 60 78 58 61 67 72 69 72 66 69 65 55 65 58 58 75 50 42 57 54 62 59 51 50 57 50 59 70 64 61 62 59 70 71 50 43 62 50 59 50 53 56 52 56 59 48 49 55 56 64 47 47 63 44 51 52 50 51 45 47 48 46 56 52 50 48 59 55 46 44 49 44 50 47 39 40 34 41 48 47 35 46 48 49 38 37 51 49 43 30 54 41 36 29 46 40 37 49 50 42 48 36 36 34 36 36 46 48 40 41 35 43 47 28 38 27 33 52 29 39 37 55 32 52 32 35 40 44 30 35 37 37 33 28 35 33 36 46 37 33 37 45 24 34 36 35 44 31 36 30 26 33 28 37 27 41 26 35 34 25 29 31 41 34 38 22 35 19 30 41 24 29 29 26 21 29 28 36 30 29 37 35 23 25 30 23 27 36 19 32 29 19 26 17 25 35 25 18 27 23 24 19 33 20 36 26 16 27 21 29 31 20 19 28 27 22 18 19 24 24 21 27 33 17 17 27 18 23 19 16 24 20 20 19 23 20 21 21 24 26 14 27 35 22 24 23 17 20 33 15 25 26 56 54 60 60 49 71 60 67 52 60 59 59 47 49 46 43 28 20 14 18 10 19 21 18 24 18 21 22 13 14 16 18 19 12 13 24 19 14 23 22 28 25 25 43 20 22 25 24 22 24 29 16 20 19 17 20 25 17 20 11 21 15 11 10 12 19 16 21 19 15 18 17 12 10 15 17 10 17 16 17 11 11 20 17 18 10 20 8 18 5 12 15 14 15 17 11 16 18 8 11 16 4 15 18 14 14 17 20 21 20 15 22 10 20 19 10 21 16 17 14 11 12 13 12 14 16 15 14 8 8 8 16 11 10 13 7 11 12 16 9 16 12 15 16 9 17 12 12 13 9 9 15 17 13 16 13 9 18 18 14 9 18 11 18 9 11 18 12 19 8 24 13 9 8 5 8 14 10 8 5 12 9 9 12 14 11 8 13 6 10 10 14 12 15 9 9 7 12 12 11 11 5 6 7 11 12 8 9 10 9 13 7 9 13 6 5 7 13 11 9 10 11 8 13 11 9 6 11 9 9 14 9 7 11 7 11 7 9 5 8 9 9 10 13 11 11 12 12 7 7 6 6 8 5 12 7 9 10 8 11 8 8 13 4 6 8 8 7 3 13 6 6 10 10 6 7 12 7 8 7 8 7 2 13 8 14 10 10 7 6 9 6 6 8 2 8 5 6 7 7 2 13 8 6 6 3 9 8 5 10 6 8 7 6 6 4 6 1 10 7 3 6 8 10 10 7 12 15 11 6 10 11 9 7 5 8 8 3 8 8 10 3 4 8 5 7 6 10 7 9 7 8 3 3 7 11 9 5 4 7 6 12 5 9 8 12 7 8 6 7 5 1 8 6 11 4 11 12 3 4 5 7 7 3 11 2 8 4 3 3 6 8 2 2 4 6 5 4 7 4 3 7 3 2 6 4 3 2 2 6 3 6 6 4 5 3 3 7 5 3 6 5 2 4 2 5 5 5 2 1 2 3 7 6 5 2 1 2 6 3 3 4 1 1 3 5 3 4 1 3 4 0 4 2 3 4 1 6 5 0 2 4 5 17 23 9 10 11 18 11 3 2 3 1 3 1 4 2 5 3 6 1 6 3 5 4 5 3 1 1 5 1 4 1 4 3 5 3 3 0 2 3 1 8 12 8 10 10 4 8 10 14 2 4 1 3 4 5 2 4 1 6 2 3 5 6 1 5 6 1 1 4 3 3 4 6 1 2 2 5 2 8 1 2 4 3 5 3 4 4 3 3 3 3 3 3 3 3 2 1 1 4 0 4 4 0 1 3 4 1 6 2 3 2 6 3 0 3 4 3 1 5 1 2 1 7 1 4 2 3 0 6 1 0 3 1 3 2 3 1 1 0 2 2 2 1 4 3 0 4 1 2 3 1 2 0 3 4 3 1 2 1 1 3 3 2 2 2 1 2 4 2 1 2 5 0 0 1 3 2 0 1 3 4 4 3 7 2 1 1 0 3 2 1 1 2 4 0 0 4 3 1 4 1 2 2 4 0 4 0 2 0 1 3 1 1 1 0 0 1 0 2 2 1 2 1 2 2 2 2 5 1 1 0 5 1 1 5 3 1 2 2 2 3 4 1 3 2 4 2 0 2 3 2 2 1 2 0 2 0 5 0 1 0 3 1 3 1 2 3 2 3 2 1 2 1 3 2 0 0 4 0 3 5 3 1 3 2 2 2 3 5 2 1 1 1 2 1 1 1 2 2 3 2 1 2 3 1 2 2 2 1 1 0 2 1 1 4 0 0 1 4 2 0 2 3 1 2 1 3 2 4 2 1 1 0 2 3 1 3 0 3 0 2 1 1 3 2 3 2 1 0 2 1 2 0 1 3 1 0 0 0 0 0 1 0 3 0 2 0 0 3 4 1 3 2 0 1 
];
B = [
0 0 0
 570298 426029 144269
 298905 221978 76927
 653048 503478 149570
 563488 434282 129206
 326614 252307 74307
 739517 583499 156018
 441171 344200 96971
 570401 451833 118568
 748169 589365 158804
 410100 321162 88938
 945822 738946 206876
 758446 598421 160025
 258899 205894 53005
 488843 399237 89606
 446386 365012 81374
 120754 98160 22594
 695513 570802 124711
 146023 119458 26565
 80092 65348 14744
 38826 31600 7226
 19858 16307 3551
 18167 15045 3122
 1061419 874763 186656
 222340 183048 39292
 143651 118512 25139
 1126315 930899 195416
 289726 239572 50154
 141049 117398 23651
 1672742 1374909 297833
 371500 309083 62417
 246994 206669 40325
 1336171 1114868 221303
 428290 361026 67264
 1306619 1095736 210883
 908848 767820 141028
 709746 602337 107409
 2485632 2093798 391834
 1331303 1130798 200505
 1392594 1187145 205449
 2497983 2112718 385265
 1750468 1492943 257525
 1486203 1261106 225097
 1765546 1499715 265831
 1522981 1300329 222652
 1301251 1109139 192112
 2048688 1746563 302125
 2394048 2049354 344694
 837577 719916 117661
 4258161 3658365 599796
 2433059 2095711 337348
 2665230 2301493 363737
 4278990 3691870 587120
 5322369 4607657 714712
 3 3 0
 4867302 4224406 642896
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 25 0 0
3 0 0 0
1 1 0 0
5 8 1 0
2 5 0 1
7 6 79 2
243 10 337 36
3044 18 403 116
19018 26 696 291
70866 37 1067 619
179030 55 1466 1009
421000 120 2183 1580
836644 256 3362 2632
1535641 718 5096 4573
2269199 1581 7538 7307
2788416 3122 11488 11366
2571063 4282 16659 16185
1751898 5587 22982 23033
855710 8547 31801 31659
280740 13248 40925 41247
92101 19803 50879 51415
69158 27778 60382 59758
72924 41578 69564 69522
79242 57719 79551 80272
86835 77435 91232 91984
98369 99204 105057 104700
110069 122218 118657 118934
124093 144151 135259 134422
138368 164100 150753 151106
151865 182415 166111 166457
163936 197066 179065 178883
173193 207918 188783 188898
181734 216475 197118 197871
186050 220068 200276 202052
189688 221239 204093 204102
190457 219213 203260 203282
188361 213980 199755 200325
188582 209330 198254 198010
189114 205009 195427 196281
187970 201636 194177 194678
188916 199900 195254 193603
190538 198992 194181 195747
193092 200140 196541 197166
197262 203775 200279 201123
204576 208673 207931 207005
213572 217284 215354 215578
225225 228585 226751 226741
237558 240273 238956 239822
251667 253504 251922 253384
266950 268859 266763 266592
281084 281242 279867 281732
291463 294386 292065 293151
299754 301139 300805 300620
303519 306333 304822 305754
303266 304858 303954 304552
296591 298444 296569 296329
283625 285324 283274 285083
266405 268201 267949 267220
244928 247575 246368 246162
222637 223727 223461 222981
201509 202711 201935 202001
179218 180790 179845 181056
158703 160078 159183 159903
141037 141684 140393 141452
128807 129175 129382 129800
122858 123264 123303 122901
120863 121425 121213 121239
114125 115363 114884 114694
111185 111151 111119 111041
112337 111610 111333 111468
108465 108579 108700 108514
103367 103705 103675 103684
94096 94708 94296 94706
83737 82929 82709 83040
71572 71968 71557 72035
58397 58535 58247 57921
42370 42320 42407 42560
29893 30142 30050 30025
23225 22973 22933 23212
15161 15448 15400 15370
8173 8241 8256 8250
3445 3371 3351 3361
176 159 181 169
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
