A = [
43981 45207 264106 43407 37590 36330 36838 36405 38958 41206 44597 48594 53772 58610 64035 70098 75797 82853 89386 96657 103233 110344 116537 123460 128579 135408 136279 134992 136178 122520 121783 117821 98977 96569 91043 86101 81003 75547 71575 67467 63440 60229 57884 55724 54131 52752 51509 50660 49494 49160 48662 48182 48038 47580 47179 46779 46465 46268 45951 46085 45708 45303 45580 45466 44789 45311 45581 48289 48540 48521 51985 51826 51693 51954 51516 51240 51081 51245 50728 50499 49631 49914 49352 49474 48791 48882 48950 48382 48049 47553 47797 47092 46829 46806 46264 45712 45683 45250 44730 44632 44102 43774 43535 43131 42682 42477 42072 41536 41278 40563 40288 39416 39535 38908 38880 38245 37589 37288 36531 36866 36637 36044 35686 35278 34913 34368 34037 33284 33245 32945 32448 31866 31556 31380 30629 30446 29475 29563 29195 28777 28617 28026 27452 27152 26822 26483 25598 25980 25393 24814 24747 24365 23769 23589 23070 22702 22281 22392 21602 21417 21333 20795 20551 20318 20107 19769 19377 19253 18717 18648 18348 18020 17709 17257 17271 16884 16597 16544 16037 15833 15680 14974 15046 14544 14582 14422 13825 13744 13520 13137 12928 12656 12506 12340 12056 11704 11695 11420 11147 10898 10754 10800 10595 10338 10106 9848 9596 9596 9412 9219 9018 9007 8878 8492 8514 8359 7948 7920 7980 7857 7608 7495 7181 7257 7074 6947 6943 6722 6572 6657 6444 6294 6118 6197 6003 5942 5646 5655 5577 5424 5354 5292 5171 5161 4881 4844 4733 4753 4542 4419 4445 4385 4176 4167 4050 4137 3888 3947 3755 3661 3646 3650 3662 3560 3459 3497 3389 3416 3395 3368 3232 3094 3185 3350 3180 3133 2884 2822 2796 2741 2684 2605 2538 2452 2534 2411 2281 2320 2256 2200 2106 2126 2133 2060 2055 1971 1928 2051 1831 1796 1754 1765 1750 1702 1633 1636 1583 1541 1540 1461 1371 1476 1389 1433 1381 1332 1310 1340 1306 1240 1337 1283 1224 1155 1144 1123 1121 1158 1031 1092 1066 1024 1021 955 1051 1011 1005 983 938 902 830 924 892 819 812 796 766 802 791 738 766 771 732 749 741 726 705 661 649 674 623 592 707 642 637 638 591 613 577 577 538 584 571 540 558 522 515 556 499 530 498 460 487 475 458 449 464 424 407 462 479 426 439 445 444 423 412 342 404 394 383 369 352 369 338 383 402 363 317 345 363 344 330 332 346 315 331 291 283 331 273 309 308 343 282 289 278 282 272 275 287 285 263 262 282 226 279 241 252 242 254 268 229 263 222 265 243 255 249 219 227 245 229 242 210 230 207 221 217 205 231 219 195 209 219 206 217 203 172 201 221 176 206 205 200 194 194 189 178 209 182 193 192 194 191 178 175 156 151 170 180 180 178 167 184 173 176 166 182 151 168 149 162 166 183 159 162 139 146 165 142 148 191 126 123 172 149 125 140 166 127 136 142 127 159 137 130 126 127 146 127 111 123 126 119 116 138 114 127 113 124 124 123 110 113 124 128 134 136 127 118 122 106 125 132 126 114 129 115 124 140 128 112 116 114 107 106 113 110 122 107 117 91 108 110 107 122 98 110 119 109 103 95 83 104 92 94 103 85 93 80 94 94 104 104 80 84 99 91 87 90 88 98 88 90 100 103 82 72 93 98 86 84 89 83 106 95 86 85 75 78 80 87 97 76 79 68 85 98 69 80 81 93 83 81 68 79 86 79 76 83 79 77 99 81 70 80 61 73 85 85 84 83 73 79 72 71 90 65 65 72 64 80 80 70 64 63 69 76 72 61 83 67 60 74 61 65 73 70 59 61 54 61 69 69 55 53 56 49 56 47 68 67 72 62 61 48 63 52 67 51 64 63 57 54 70 60 60 54 52 52 54 49 46 48 54 57 56 31 48 37 69 57 47 61 59 43 57 55 57 51 52 52 61 39 40 49 48 51 59 52 52 57 48 55 57 50 42 62 48 46 33 42 49 53 44 41 56 34 40 34 45 52 44 46 45 54 47 39 41 48 57 41 41 40 43 41 31 67 80 94 86 98 106 128 109 105 125 117 103 123 128 138 143 138 144 136 83 108 106 113 102 91 91 90 80 87 80 134 100 83 99 91 59 71 60 43 43 36 41 40 35 42 29 31 32 57 33 34 33 30 34 43 30 23 41 35 25 33 28 26 35 41 27 28 27 20 31 26 40 34 38 34 26 24 37 26 26 27 22 35 29 20 25 30 36 28 23 24 28 23 31 32 32 29 28 23 26 26 34 29 30 35 31 35 20 35 51 27 24 34 32 56 66 63 55 54 68 84 105 64 96 105 160 168 163 221 194 189 257 250 221 208 128 128 115 51 38 28 30 32 30 40 40 38 51 38 44 50 50 57 33 55 41 47 43 41 42 37 44 28 34 33 37 35 33 38 32 38 22 18 15 20 32 27 18 30 20 28 10 22 17 17 13 25 19 19 26 15 21 24 23 16 32 26 15 16 30 24 15 19 21 22 17 23 24 20 18 18 13 10 19 25 18 19 17 16 11 22 20 20 25 25 15 26 14 20 22 22 21 18 22 28 18 11 23 19 20 21 31 22 19 28 42 30 31 33 38 44 37 74 65 43 37 50 28 33 39 38 42 34 30 28 39 31 44 42 45 42 26 38 36 37 34 29 32 39 26 27 23 22 22 22 22 16 22 25 19 15 19 15 17 23 23 21 30 13 9 9 17 13 14 13 8 13 14 11 13 9 12 8 17 6 9 8 5 14 10 14 9 10 8 9 11 7 4 7 11 8 10 4 10 3 21 8 10 10 5 11 5 6 3 9 12 13 10 5 8 8 7 8 7 9 5 8 6 9 1 7 8 7 12 9 8 13 9 10 13 6 7 5 8 4 9 6 8 6 7 4 6 7 7 6 9 8 7 5 4 9 5 3 4 5 3 10 7 8 9 8 9 4 13 4 9 3 8 6 5 6 4 3 8 8 7 9 5 7 10 10 11 4 9 5 5 6 5 5 8 10 6 6 8 9 6 8 7 7 8 5 6 10 4 11 7 6 6 11 1 3 10 7 4 5 7 2 8 7 4 2 2 1 8 4 3 2 2 4 7 1 3 2 3 6 7 4 3 5 3 2 2 12 5 2 4 2 3 5 8 5 5 5 3 4 6 4 2 2 4 3 2 1 2 4 7 3 8 3 2 3 4 6 3 1 4 5 3 5 3 6 8 7 7 3 5 3 1 2 4 3 4 5 4 3 3 3 9 6 0 4 9 4 4 5 7 3 6 3 3 0 2 2 4 3 3 2 4 4 2 2 3 1 1 3 5 5 6 7 2 5 6 2 1 3 5 1 4 1 5 5 3 3 3 1 1 5 5 5 1 2 1 7 5 8 2 1 0 2 4 2 7 5 3 1 3 1 2 1 3 5 8 1 6 4 3 3 0 2 3 6 1 3 1 5 4 5 4 6 0 1 1 2 3 0 3 4 1 4 3 1 1 6 4 1 6 3 3 2 1 3 2 3 2 3 5 5 2 1 2 2 3 1 2 4 2 1 3 3 0 2 3 1 3 2 1 1 2 4 5 6 0 4 3 3 5 1 3 5 3 0 2 4 2 2 3 4 0 0 2 0 2 4 2 0 1 3 1 6 2 0 1 4 2 3 3 2 2 0 5 1 1 3 0 3 1 2 0 0 2 4 1 1 2 0 2 1 1 3 1 3 1 5 1 3 1 2 3 1 1 2 2 1 0 2 3 2 0 4 0 3 2 2 1 0 2 2 0 1 1 2 2 1 1 3 0 2 0 0 1 2 3 5 2 1 1 0 2 1 2 2 3 1 3 1 1 0 1 2 0 1 1 1 4 1 0 1 3 2 0 3 1 0 0 2 2 1 1 0 2 2 2 1 1 1 1 1 0 0 0 1 1 1 1 0 3 6 3 0 6 1 3 1 2 0 1 0 1 2 3 2 3 2 1 1 0 3 2 3 2 0 0 0 2 2 3 1 0 0 0 0 0 0 3 1 0 1 0 0 1 0 1 1 1 0 1 1 2 0 0 1 1 0 1 5 0 0 1 0 3 2 0 3 1 0 0 1 1 0 0 2 0 0 0 0 0 0 1 2 0 0 1 1 0 2 1 2 3 0 0 2 0 0 1 0 2 0 0 1 0 0 0 1 1 0 1 0 0 1 0 1 3 0 0 1 0 2 1 1 0 0 1 0 1 0 0 0 2 0 0 0 0 0 0 2 1 1 1 1 2 0 0 0 1 1 2 1 1 0 0 2 0 0 1 0 0 0 0 1 1 1 0 0 0 0 1 0 1 2 0 3 2 0 0 2 0 0 0 1 1 0 0 0 1 0 3 0 0 0 1 0 0 0 0 0 0 0 0 0 1 2 0 0 0 0 0 0 1 1 1 0 1 0 1 0 0 1 0 0 2 0 0 1 0 0 0 0 0 0 0 1 0 1 1 0 0 1 0 0 0 0 0 0 1 1 0 0 1 1 0 1 0 0 3 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 1 0 2 0 0 1 0 0 1 0 0 0 0 0 0 1 1 1 1 1 0 0 2 0 2 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 2 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 
];
B = [
0 0 0
 23147 13150 9997
 25824 15471 10353
 23103 13691 9412
 37141 25077 12064
 27320 18952 8368
 20861 15063 5798
 17617 12765 4852
 13155 9325 3830
 10685 7779 2906
 7472 5479 1993
 8532 6313 2219
 9370 6904 2466
 9852 7316 2536
 22696 17546 5150
 16035 12606 3429
 16634 13245 3389
 15220 12353 2867
 15373 12545 2828
 15483 12492 2991
 13465 10918 2547
 18997 15345 3652
 16934 13665 3269
 16109 13071 3038
 14692 12015 2677
 16303 13351 2952
 15530 12806 2724
 19180 15821 3359
 14722 12202 2520
 17595 14430 3165
 17479 14307 3172
 16845 13704 3141
 18365 15153 3212
 18159 14875 3284
 23031 18721 4310
 18093 14987 3106
 21116 17410 3706
 41325 33021 8304
 19818 16342 3476
 23069 18770 4299
 37968 30509 7459
 24310 19900 4410
 36200 29217 6983
 20317 16830 3487
 25240 20894 4346
 37423 30228 7195
 24957 20658 4299
 37353 30274 7079
 26058 21602 4456
 37828 30732 7096
 25511 21243 4268
 37778 31041 6737
 29232 24356 4876
 38247 31467 6780
 26793 22243 4550
 41554 34200 7354
 39076 32270 6806
 27194 22710 4484
 39693 32783 6910
 24626 20940 3686
 3589722 3188677 401045
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
1 2 0 0
1 0 0 0
1 2 0 0
2 0 0 0
1 2 0 0
2 0 1 0
2 3 1 1
28 1 0 0
476 1 1 1
7262 4 8 1
30927 5 40 5
102914 0 56 17
263609 5 67 45
462096 11 122 71
538194 27 152 148
454506 41 235 234
284992 84 366 349
135557 126 456 479
46102 202 613 669
9572 309 868 909
2204 480 1143 1108
1702 729 1410 1429
1862 1081 1633 1766
2143 1430 2204 2082
2508 1887 2588 2537
2919 2556 2942 2976
3524 3219 3701 3671
4278 3914 4643 4830
4894 4596 4836 4869
5695 5333 5606 5566
6215 6115 6358 6227
6758 6594 6932 6803
7552 6993 7238 7325
7554 7501 7688 7667
7872 7863 8110 8081
8124 8328 8457 8383
8466 8301 8652 8621
8765 8663 8825 8880
8851 8836 8760 8977
9193 9214 9414 9230
9324 9521 9702 9505
9796 9906 9814 10109
10141 10434 10223 10242
10836 10815 10933 10623
11172 11307 11171 11325
11837 11614 11885 11906
12114 12241 12222 12290
12400 12485 12470 12576
12762 12830 12804 12904
12930 12904 12974 12932
12947 12739 12827 12831
12618 12631 12976 12721
12182 12352 12444 12184
11756 11800 11786 11757
11121 11122 11085 10985
10294 10619 10347 10345
9658 9649 9457 9680
8727 8634 8643 8744
7989 8152 7801 7925
7345 7293 7201 7213
6612 6578 6733 6671
6244 6345 6310 6509
5939 5838 5870 5948
5823 5730 5724 5683
5680 5796 5732 5822
6057 6037 6085 5941
6657 6354 6511 6367
6967 6989 7024 7073
7966 7903 7765 7859
8739 8748 8708 8922
9925 9968 9831 10036
10729 10606 10889 10623
11542 11212 11272 11308
11679 11919 11639 11887
11581 11537 11470 11466
10483 10260 10553 10581
8723 8863 8777 8923
6160 6259 6177 6060
3249 3135 3193 3231
1167 1154 1121 1152
187 189 202 154
1 2 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 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
