A = [
528349 546505 1152166 566446 556345 552375 521254 532093 520961 514258 514629 508346 509646 509248 503349 499239 499095 494503 493493 491497 489138 485780 483991 479523 477985 474068 472970 468481 468820 464733 462061 460269 457152 454983 450755 448748 445207 443688 441606 437495 437092 434605 429069 427290 425861 423006 421645 418944 414440 412520 410529 407017 404955 402557 399374 397284 394413 391095 387747 386227 384272 380553 377019 374660 373415 368948 366186 363010 360013 357228 355833 351747 348687 346921 342261 340643 336711 333900 330634 329299 325216 321556 319936 316897 313088 310002 308370 303769 302562 299328 297009 292763 290868 288190 285383 281923 278968 276537 272085 269656 266766 264110 261003 257858 255722 252290 250057 247054 244242 241204 238244 235369 233241 230798 227875 224627 222765 220492 217581 215021 212310 208857 205829 204256 200479 197875 195916 193861 190376 188193 186344 183232 179773 177899 175344 173173 170705 167994 165418 163527 161542 158432 156400 153372 151818 148871 147124 145871 143453 140917 138602 136895 135712 132732 131206 128994 125913 125004 122434 120972 118813 116816 114604 112975 111114 109350 108274 105560 104153 102481 99825 98903 97050 95406 93511 92302 90875 89159 88260 85940 84583 83011 81876 80031 78859 76806 76005 74317 72968 71905 71047 69571 68274 66659 65535 64531 63077 62042 60984 59620 58700 57386 56267 55673 54298 53204 52363 51649 50297 49096 48500 47232 46705 45756 45055 43957 43152 42174 41356 40807 39840 39257 38307 37538 36677 35990 35746 34572 34045 33568 32526 32284 31588 30586 30239 29399 28899 28511 27923 27361 26476 26399 25746 25100 24784 23991 23479 23223 22865 22356 21661 21102 21124 20587 19848 19717 19251 18725 18265 17772 17651 17224 16859 16470 16108 15653 15324 15209 14966 14249 14140 13830 13644 13322 13103 12837 12550 12398 11745 11664 11801 11128 10926 10824 10473 10345 9958 9637 9498 9256 9092 9102 9021 8595 8452 8282 8090 7917 7662 7556 7286 7303 7219 6785 6872 6721 6309 6277 6099 6247 5897 5748 5542 5629 5342 5294 5199 5054 4926 4809 4747 4587 4490 4311 4347 4163 4128 3916 3909 3834 3819 3685 3618 3496 3367 3348 3333 3170 3070 3054 2836 2872 2893 2653 2749 2674 2624 2549 2438 2458 2394 2442 2263 2263 2044 2127 1978 2026 2076 1960 1868 1850 1837 1816 1757 1711 1631 1648 1552 1570 1491 1450 1495 1345 1298 1370 1355 1334 1245 1292 1175 1173 1163 1089 1138 1116 1082 1083 977 1004 1030 973 1011 941 888 864 852 878 834 809 763 809 841 717 653 752 725 702 633 679 630 624 642 606 636 622 632 608 569 613 551 549 512 493 506 487 497 450 464 498 459 408 483 427 420 435 422 393 388 373 359 336 384 390 350 339 328 332 346 344 288 297 322 288 338 324 290 311 295 302 303 310 262 271 244 234 258 266 258 251 248 261 265 221 251 231 229 226 212 225 183 227 226 212 220 214 195 217 184 187 222 196 184 190 186 200 171 193 186 176 183 187 183 150 172 191 171 165 165 175 166 166 160 154 173 167 145 156 161 155 137 162 161 153 144 161 148 138 160 152 156 139 147 145 169 126 148 160 140 127 139 142 116 140 109 135 130 127 143 131 121 135 111 132 123 116 122 128 120 122 106 117 93 118 106 120 114 114 102 98 104 107 104 109 118 113 109 111 99 92 101 89 107 118 109 99 106 109 90 103 84 108 109 96 107 76 86 100 108 100 113 91 81 89 95 93 92 96 92 100 94 94 86 95 93 94 85 88 81 84 91 88 85 87 93 93 78 64 78 97 68 75 75 74 86 89 105 68 74 80 87 71 63 79 59 64 79 84 90 83 77 86 80 84 77 70 78 63 67 70 86 78 71 58 72 69 76 71 56 59 71 65 74 71 62 76 68 59 67 62 61 65 61 59 52 56 57 46 52 53 77 61 67 57 59 57 51 55 60 51 53 46 51 48 59 61 58 60 54 56 54 56 59 45 64 54 49 53 57 54 55 49 41 56 46 54 62 48 50 50 44 50 41 58 51 57 39 46 41 45 56 56 46 47 52 56 40 41 42 40 42 47 48 47 46 42 51 45 46 49 45 42 47 42 36 54 49 38 40 41 38 57 40 37 34 36 36 44 40 39 25 37 39 35 43 43 49 41 50 51 31 34 35 39 45 45 35 35 37 35 37 39 41 36 40 42 31 29 20 37 45 35 30 39 29 25 34 32 31 19 37 26 26 31 36 38 33 34 31 33 48 34 33 27 34 24 39 33 40 37 33 31 30 30 31 19 33 39 36 27 37 25 30 34 30 21 26 34 31 24 25 20 34 31 28 32 28 35 23 27 22 28 29 24 29 24 24 20 31 27 28 26 23 22 32 31 27 25 20 30 21 19 32 26 24 23 25 23 19 17 24 18 28 25 31 15 23 22 21 21 18 21 19 21 20 16 27 22 13 26 23 23 21 18 21 17 24 11 19 23 16 18 16 19 23 24 18 27 22 17 19 21 21 23 19 21 22 10 22 28 23 21 21 31 19 25 17 16 18 13 15 5 20 19 27 21 10 21 12 14 17 24 19 11 14 19 29 22 21 31 25 26 21 22 23 20 18 13 17 11 17 22 14 10 15 10 18 8 16 18 12 20 15 15 27 20 17 21 17 20 16 21 20 7 21 23 21 23 11 16 13 19 10 19 18 18 18 16 15 12 18 12 21 12 17 12 11 13 11 10 15 13 9 7 11 18 13 8 13 14 10 19 16 16 14 14 18 18 15 9 17 12 8 12 11 7 6 7 15 8 10 10 11 8 17 16 12 22 11 18 11 10 16 8 5 18 8 23 5 13 7 7 6 6 4 10 9 9 13 6 11 8 5 14 10 9 9 6 7 3 14 10 14 4 9 8 10 8 11 12 5 13 7 10 10 8 9 13 8 8 7 8 7 8 9 6 11 7 6 6 10 6 4 9 10 13 11 6 8 17 8 2 6 5 8 11 9 3 4 8 8 10 8 2 10 8 10 4 10 10 5 9 3 7 7 9 7 6 6 8 5 6 2 3 6 11 6 11 9 5 8 3 6 6 9 4 2 3 7 6 8 6 14 6 4 2 5 7 4 5 5 7 10 9 7 7 4 6 10 7 8 2 4 6 5 6 4 6 2 9 7 10 8 0 6 10 3 7 2 3 2 5 5 6 3 6 5 5 4 3 7 7 6 2 5 6 9 6 7 4 4 4 4 5 3 6 3 4 5 4 6 5 7 6 1 7 2 2 3 2 4 7 3 2 4 6 4 2 6 2 3 3 8 3 5 8 8 3 5 3 3 2 4 3 4 2 8 5 5 2 2 3 4 3 1 2 5 6 1 2 4 3 1 4 3 1 1 4 3 6 1 1 3 1 2 2 1 3 4 4 1 5 1 2 2 4 5 3 4 0 3 2 2 0 4 1 3 3 7 2 4 0 3 1 3 1 2 3 4 4 4 1 1 3 1 4 5 1 4 4 5 1 2 4 0 3 4 3 4 1 4 0 0 1 1 2 4 3 2 3 3 3 2 4 3 1 11 4 3 1 2 3 2 4 2 2 2 1 0 2 4 1 1 0 5 2 2 2 0 4 1 1 2 2 2 1 3 1 3 2 2 3 2 1 2 6 1 2 2 3 0 0 2 2 4 1 3 3 2 1 5 1 3 1 0 1 1 1 2 2 0 2 4 4 2 4 2 0 0 3 0 2 2 4 3 2 1 3 0 2 1 3 1 1 4 1 1 2 2 1 2 3 0 3 0 4 2 3 0 1 2 1 0 0 1 1 2 0 1 3 0 3 1 2 2 1 0 0 3 0 2 1 1 1 1 2 0 2 2 3 1 0 0 1 1 1 2 2 0 0 1 1 2 2 1 0 0 0 2 1 2 0 0 3 1 1 3 0 2 1 2 1 2 2 0 0 1 0 3 2 4 2 0 1 2 2 0 1 3 3 1 2 0 2 0 2 1 0 0 1 1 2 0 0 2 0 1 2 0 0 0 1 1 0 0 2 0 1 0 1 0 0 2 1 1 5 2 2 4 0 2 1 5 0 0 0 1 0 1 0 1 2 1 1 1 1 0 0 0 0 1 1 1 3 1 1 0 0 0 1 0 0 2 0 0 2 0 0 2 0 0 2 2 0 1 0 0 0 2 0 0 0 2 0 2 1 1 1 2 1 1 2 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 3 2 3 0 0 1 2 0 1 0 0 0 0 1 0 2 0 1 2 1 1 0 0 2 0 0 0 1 1 0 1 1 0 3 0 1 0 0 2 0 0 3 1 0 1 2 0 1 0 0 1 1 0 2 0 0 0 4 2 2 0 0 1 1 0 0 0 1 0 0 1 0 1 2 0 0 1 0 2 0 1 0 1 2 1 0 0 0 1 1 1 0 0 0 1 4 3 1 0 0 1 0 0 1 1 0 0 0 0 0 1 0 1 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 2 0 0 1 0 0 2 2 1 0 0 0 1 0 0 0 0 0 2 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 2 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 1 0 0 1 2 0 2 1 0 0 0 1 2 1 0 0 0 2 0 0 0 0 1 1 0 0 0 0 1 1 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 1 0 0 0 0 1 0 1 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 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
 31483 30545 938
 57020 55716 1304
 16321 15657 664
 159005 156198 2807
 13822 13361 461
 40691 39567 1124
 21744 21268 476
 49080 48121 959
 3095 2897 198
 202710 199832 2878
 338 323 15
 12145 11810 335
 3744 3527 217
 48760 47676 1084
 5760 5647 113
 4366 4230 136
 18805 18432 373
 9962 9570 392
 333914 329548 4366
 58372 57562 810
 5867 5772 95
 32335 32003 332
 13931 13690 241
 13129 12732 397
 435876 431218 4658
 8933 8815 118
 156898 155952 946
 20744 20575 169
 17515 17255 260
 21031 20464 567
 28089522 27991884 97638
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
9 4 0 0
6 2 0 0
16 1 0 0
21 3 0 0
9 1 1 0
23 4 10 2
1817 5 28 1
13563 9 25 7
57815 9 39 19
197123 6 57 20
502430 13 70 38
1205070 19 86 44
2443717 27 99 69
4321199 33 138 124
5887975 84 148 162
6289197 97 188 220
4881458 89 223 248
2702311 163 218 256
987631 232 283 315
193471 264 343 376
18983 300 356 437
2713 344 412 474
1682 356 471 504
1482 338 459 538
1474 371 408 458
1216 372 408 421
1634 350 357 418
966 343 345 354
1479 269 302 321
958 279 296 277
1204 240 259 249
1834 222 232 220
3407 219 245 213
565 314 227 229
424 406 276 325
336 264 177 283
213 914 146 185
278 255 141 133
254 310 159 154
235 274 125 134
294 269 144 146
283 287 163 199
227 240 186 147
274 302 191 178
236 245 185 178
247 202 155 185
255 260 199 179
212 176 177 185
220 197 184 197
206 199 181 196
221 198 149 136
185 170 187 164
163 184 180 165
152 158 152 153
170 188 164 146
142 152 151 157
151 124 171 152
119 121 337 328
150 128 139 128
142 148 121 125
124 136 152 138
165 172 144 163
135 105 113 120
128 129 146 146
142 155 170 171
193 167 175 202
194 176 193 148
189 196 200 207
221 201 228 243
245 275 385 286
310 286 292 276
277 309 342 317
318 319 275 353
315 321 302 318
322 289 315 299
286 275 257 289
216 231 235 261
187 193 193 198
129 124 115 132
61 46 39 44
18 9 18 12
0 0 0 1
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
