A = [
22275 23260 1028547 29756 18711 18860 18730 13977 14535 15314 17130 17673 18699 19482 20498 21678 22381 22943 23789 24006 24465 24681 24858 25310 25376 25994 26219 26393 26763 26804 26767 26842 26819 27310 26851 26694 26707 26663 26507 26651 26420 26722 26332 26455 26300 26430 26465 26584 26153 25675 26019 25590 25498 25637 25185 25026 24784 25007 24891 24340 24309 24051 23689 23794 23345 23515 23070 22958 22642 22685 22528 22251 21942 21908 21758 21879 21472 21822 21130 21427 20878 20855 20807 20310 20288 19989 19607 19455 19076 19152 18637 18780 18410 18244 18272 18033 17726 17705 17310 17242 17036 16677 16941 16800 16568 16022 15877 15600 15725 15587 15164 15232 15068 14905 14930 14565 14824 14516 14257 14269 13784 13594 13873 13524 13241 13022 12905 13126 12930 12460 12373 12139 12361 12117 11773 11757 11503 11371 11268 11210 11031 10966 10656 10665 10390 10233 10278 10066 9859 9665 9438 9515 9398 9197 9125 9162 8786 8685 8674 8615 8109 8180 8190 8167 7985 7723 7668 7400 7621 7390 7148 7095 6991 6938 6591 6635 6421 6390 6314 6055 6122 6030 5922 5922 5763 5693 5459 5544 5245 5151 5202 5076 4874 4734 4757 4743 4611 4525 4346 4324 4167 4192 4180 4185 4071 3899 3875 3740 3729 3652 3564 3430 3310 3250 3309 3262 3075 3154 2960 2974 2825 2842 2910 2715 2698 2738 2632 2513 2550 2410 2363 2338 2322 2216 2284 2134 2043 2112 2104 2056 1932 1807 1833 1846 1799 1765 1701 1661 1588 1555 1438 1490 1495 1388 1290 1304 1357 1281 1234 1228 1235 1166 1161 1180 1062 1123 992 1048 996 978 924 916 914 846 837 834 868 820 782 728 786 738 671 698 708 678 611 600 611 619 590 539 549 575 472 507 494 509 470 470 493 449 427 425 404 372 371 388 348 344 364 337 305 323 304 303 282 268 276 269 266 250 275 233 262 219 234 216 232 238 233 202 191 212 185 186 186 165 189 178 153 157 167 162 138 145 153 152 133 123 129 127 103 107 107 102 90 107 96 99 94 97 87 82 95 90 92 78 79 70 77 76 73 76 64 52 42 64 54 56 64 64 58 55 56 45 49 55 41 44 25 31 29 39 35 29 48 37 32 21 35 22 22 29 19 21 34 26 26 14 21 24 21 30 27 27 21 20 21 26 40 28 31 23 23 37 47 38 41 49 54 31 21 26 18 16 14 14 12 12 11 11 8 10 11 9 7 24 13 14 6 9 12 5 10 14 13 7 6 16 8 6 5 8 10 9 4 7 8 10 6 7 7 9 11 5 9 7 3 8 2 6 3 5 3 6 2 8 6 5 6 1 2 3 5 3 6 6 4 4 3 5 2 5 2 1 4 3 1 2 2 4 10 5 0 3 2 5 0 4 3 2 4 3 4 2 3 2 3 6 1 5 1 2 3 3 1 1 0 0 2 1 3 3 3 2 1 2 2 1 0 2 1 3 3 4 0 1 2 2 2 2 2 0 3 1 0 3 1 1 5 3 3 5 6 2 6 5 0 3 4 1 10 3 2 5 0 1 0 2 3 2 2 1 1 0 1 2 0 2 3 1 4 1 3 0 1 2 1 2 7 6 2 0 2 1 1 5 2 0 2 0 1 2 2 1 1 1 3 4 0 2 3 1 0 2 0 0 4 3 2 1 3 3 0 1 3 1 2 1 4 1 5 2 2 4 2 0 3 1 1 0 0 1 3 1 0 2 2 2 2 0 2 0 1 0 2 4 0 0 3 2 0 0 1 0 1 1 1 1 3 0 2 0 2 0 1 1 0 1 2 0 0 2 3 2 2 4 1 0 2 1 1 0 2 3 1 0 3 0 0 0 4 0 0 0 1 0 0 0 0 0 2 1 0 0 0 2 0 1 3 0 2 0 0 3 1 1 1 1 1 0 2 1 0 0 0 0 1 3 0 0 2 0 0 1 0 0 0 0 0 0 0 0 1 0 1 1 2 2 1 0 1 1 0 2 1 1 1 1 3 1 0 0 1 0 0 1 1 1 0 3 1 0 3 0 3 0 0 0 0 1 0 1 1 0 0 2 1 4 4 0 1 3 4 4 0 0 2 0 2 0 1 0 1 2 1 3 1 2 1 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 2 1 1 2 0 0 0 1 1 1 1 0 0 0 0 0 0 0 1 0 2 1 0 0 1 2 0 0 0 0 0 2 2 0 0 1 3 0 0 1 0 0 2 0 2 2 1 4 1 0 1 1 3 1 2 1 3 1 1 1 4 0 2 1 0 3 2 0 2 1 0 0 0 2 1 1 1 1 1 4 1 2 2 1 0 2 2 1 0 2 1 2 2 0 1 4 0 1 3 2 2 1 1 2 1 1 1 0 0 1 1 1 0 1 2 0 1 0 0 0 0 2 2 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 0 2 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 3 1 0 0 0 0 0 3 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 2 0 0 1 0 0 0 0 0 2 0 0 1 0 0 0 1 1 1 1 0 1 0 0 0 0 1 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 3 0 0 0 0 1 0 0 1 1 0 0 1 1 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 1 2 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 2 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 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 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 4 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 10 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 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 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 1 1 0 0 0 1 0 1 0 0 0 0 2 0 1 0 0 0 0 1 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 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 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 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 1 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 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 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 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 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 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 2 0 0 0 1 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 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 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 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 1 
];
B = [
0 0 0
 22692 20411 2281
 10510 9444 1066
 27470 25386 2084
 23335 21323 2012
 11719 10775 944
 33569 31465 2104
 13179 12182 997
 28317 26671 1646
 29861 28058 1803
 4876 4586 290
 60817 58214 2603
 12394 11795 599
 3960 3762 198
 22892 22001 891
 7569 7208 361
 1534 1447 87
 24837 23893 944
 1216 1159 57
 1024 964 60
 204 193 11
 237 229 8
 428 415 13
 38749 37224 1525
 1777 1696 81
 2238 2164 74
 37673 36353 1320
 2257 2166 91
 2255 2173 82
 55906 54167 1739
 2947 2854 93
 2982 2909 73
 38163 37207 956
 4572 4503 69
 40741 39816 925
 8575 8495 80
 7018 6941 77
 62802 61775 1027
 18637 18496 141
 30793 30655 138
 76728 75744 984
 34810 34626 184
 27541 27319 222
 81118 80224 894
 25760 25626 134
 14469 14307 162
 95493 94592 901
 15077 14901 176
 2706 2666 40
 208672 207212 1460
 3588 3551 37
 11967 11843 124
 398013 395956 2057
 13395 13292 103
 0 0 0
 845255 841858 3397
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 3 0 0
0 0 0 0
1 1 0 0
2 2 0 0
5 1 0 0
9 1 0 0
59 10 1 0
497 2 0 1
2131 3 1 0
9977 11 4 1
31940 1 7 1
89453 11 5 1
207484 19 7 2
412281 3 15 8
569062 22 11 11
579170 11 16 9
368816 17 16 22
144364 10 32 36
33575 22 41 43
3942 18 61 58
286 40 72 64
113 43 77 66
123 56 106 102
123 90 137 123
122 128 132 143
139 115 152 140
174 169 169 156
202 209 183 187
214 191 192 200
259 222 236 218
261 255 237 254
249 262 251 240
276 262 275 255
262 289 243 247
499 610 266 259
252 289 278 277
279 599 308 252
300 265 274 287
313 309 271 285
309 308 301 286
313 366 328 310
328 296 322 298
321 319 345 342
351 345 375 364
334 351 353 316
368 375 435 344
359 397 454 373
391 396 445 437
368 406 443 375
423 446 392 395
463 413 432 438
443 428 416 431
431 451 488 418
367 407 402 433
388 418 421 414
370 370 391 398
406 389 345 372
349 370 348 342
319 307 360 299
295 266 287 285
242 258 257 264
218 229 230 257
229 189 206 225
231 218 191 177
201 187 184 182
192 181 167 191
171 180 192 180
903 561 237 182
179 200 183 158
186 175 185 168
167 160 180 172
158 161 166 175
163 165 183 151
158 143 134 130
125 121 135 145
126 136 102 130
81 105 92 82
61 56 65 52
60 44 51 33
41 49 40 28
26 19 20 23
6 11 13 19
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

];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 
];
