A = [
345835 317556 601073 352195 330146 331712 313516 328318 327898 320394 332650 343752 355865 365833 369737 374721 377376 380401 378553 375948 377004 377335 376770 379185 384822 624759 626826 629857 873083 886036 910568 932798 933243 961040 969475 955067 946986 934085 927377 916229 913026 915253 912657 916657 919481 907930 897451 886700 870081 856974 849837 845795 847447 845098 842261 838340 830741 818571 803262 793446 783178 775289 771746 769436 769117 762297 756040 746710 734499 724197 715280 708398 702971 702440 699663 699279 693876 684962 676459 667748 654354 644806 640286 632939 629078 625251 618461 610157 602438 593664 583151 572564 564401 556253 552729 548718 543736 539502 531189 523304 514013 506331 498871 492319 485843 483275 477688 472806 467734 461414 452981 446122 438828 431157 426679 422949 418072 412870 408009 403296 397472 389828 382685 377190 370609 367882 361632 358568 354835 349215 344957 338657 333266 327664 322532 317795 313313 310555 306841 302540 298690 293011 288588 282857 278055 274333 269878 265589 261125 260139 255525 251187 247080 242380 238619 234038 230321 227613 224841 221805 219125 215137 210778 207218 202425 200186 197521 194210 191999 188234 185644 183173 179531 177303 173973 170247 166984 165376 162773 159702 156828 155187 152899 150060 147155 145073 141687 140445 136917 136327 132592 130949 128657 126599 124948 122121 120503 118220 115656 113810 112388 110203 108681 106758 105205 102950 101000 98776 96861 95929 94814 92346 90986 89691 87312 86245 84920 83011 81706 80627 78802 77339 76464 74780 73943 72323 70972 69348 67910 66579 65659 64813 62843 61668 61121 60166 58778 57741 56984 55774 54235 53567 52373 51876 50113 49355 48595 47888 46879 46152 45169 44359 43671 42865 42084 40753 40121 39762 38752 37997 37186 36547 35849 35036 34370 33838 33162 32243 31923 31156 30719 30132 29321 29073 28241 27620 27284 26256 25990 25542 25221 24708 24291 23661 23199 22593 22452 21564 21272 20732 20475 19639 19492 19082 18627 18238 18236 17775 17170 17111 16593 16277 15822 15541 15321 14740 14528 14166 13984 13960 13437 13083 12723 12739 12191 12086 11813 11475 11428 11086 10995 10689 10324 10383 9765 9795 9552 9240 9107 9129 8877 8718 8378 8272 8104 8075 7683 7707 7418 7346 7186 6858 6832 6842 6529 6431 6340 6174 5933 6040 5883 5630 5543 5446 5221 5263 4988 4956 4857 4694 4635 4507 4590 4344 4300 4275 4110 3951 3882 3888 3713 3660 3610 3513 3470 3355 3304 3238 3196 3085 2978 3026 2882 2750 2727 2813 2654 2575 2567 2463 2491 2341 2350 2380 2209 2209 2208 2178 2033 2060 1960 1966 2024 1898 1830 1829 1777 1751 1798 1699 1647 1626 1534 1563 1540 1561 1479 1398 1462 1336 1381 1332 1306 1281 1236 1251 1228 1262 1159 1194 1113 1089 1108 1026 1073 1055 991 1040 945 922 930 863 940 870 870 860 800 801 821 822 776 746 799 786 755 751 716 681 676 725 651 669 681 671 609 613 628 630 625 550 605 565 576 513 536 498 538 522 556 474 484 535 483 471 482 497 467 475 460 482 422 453 425 422 412 436 397 394 421 410 421 417 395 419 373 374 372 371 351 391 365 369 339 343 334 355 335 299 295 327 312 325 302 315 311 325 288 291 311 302 307 296 312 297 250 277 271 270 279 241 272 282 282 253 242 272 261 244 268 266 217 220 240 259 226 276 241 264 207 217 231 243 229 221 247 225 236 212 242 229 233 212 201 219 208 224 224 199 224 210 219 228 186 188 216 193 210 196 208 220 165 187 185 193 198 196 193 183 212 187 202 175 185 174 175 202 192 194 181 159 190 183 175 180 185 168 166 173 169 182 158 144 174 181 163 169 164 165 165 147 170 161 141 166 176 167 172 156 145 150 141 138 130 146 164 154 146 126 159 148 130 167 153 158 138 171 143 144 164 151 118 114 131 150 118 146 127 137 148 118 115 128 140 123 106 134 122 137 123 128 141 122 125 124 104 121 147 114 128 152 116 132 131 116 121 129 153 115 125 112 103 119 102 109 117 121 94 105 100 107 108 112 122 114 112 107 130 113 110 120 130 118 117 101 111 112 93 103 120 88 119 143 114 91 106 94 104 86 105 115 113 102 101 89 104 89 81 91 91 91 106 89 97 96 88 91 76 78 82 78 88 101 84 92 96 97 79 97 96 93 85 76 96 75 85 86 72 87 73 69 67 79 75 76 78 83 79 88 79 87 90 71 77 86 83 72 71 64 54 84 84 51 72 85 76 76 68 79 62 69 76 69 68 78 78 80 73 79 70 78 73 75 80 55 65 67 70 53 63 75 60 71 68 56 68 68 63 57 70 57 63 60 48 70 52 57 63 64 57 57 48 60 62 51 60 54 70 66 57 70 62 66 50 52 54 58 45 53 54 54 52 52 47 69 57 54 49 46 62 51 59 34 48 63 52 60 57 50 42 37 34 46 64 55 47 32 39 55 45 42 39 38 48 50 45 39 49 53 50 35 39 59 45 41 40 52 48 44 41 48 35 35 42 36 38 47 35 28 39 38 43 40 37 33 34 30 47 48 48 37 42 39 53 50 27 32 51 34 46 32 34 38 34 34 45 37 37 41 35 40 27 33 41 36 34 33 37 34 32 33 28 38 32 39 36 34 42 40 32 29 36 34 32 29 32 28 24 27 30 36 27 36 36 34 26 26 34 32 31 21 40 29 24 19 27 33 28 38 35 31 34 27 20 22 21 27 30 31 32 31 23 32 29 22 25 17 26 35 20 27 28 33 21 35 23 26 28 35 22 21 22 24 23 20 23 22 27 36 27 23 22 31 16 23 26 27 29 21 25 17 20 19 19 23 22 26 19 20 25 19 16 19 29 21 27 17 25 13 18 28 14 20 21 21 16 24 16 25 25 21 25 23 19 16 23 16 19 18 10 18 24 11 18 14 17 21 15 12 18 12 21 16 24 16 25 18 12 22 15 20 24 16 14 19 19 17 13 15 15 20 13 17 22 14 12 17 11 11 13 11 19 11 15 13 13 14 18 15 19 16 10 16 23 17 16 16 12 10 20 10 15 11 18 11 14 12 9 21 18 19 9 17 22 15 11 12 13 11 15 14 10 12 7 14 16 14 18 10 12 12 8 9 13 9 13 7 6 19 13 10 11 11 13 12 14 16 11 12 12 17 8 15 14 10 14 10 15 13 21 11 14 7 14 11 5 8 6 12 13 14 12 11 9 9 7 4 7 6 10 8 11 11 6 8 9 10 10 3 15 6 12 3 9 10 7 11 12 3 14 10 8 7 11 4 11 12 11 11 11 13 8 7 13 10 9 13 14 9 9 4 9 8 8 8 8 7 8 11 9 9 5 5 6 11 7 6 6 5 7 8 8 6 12 5 8 11 4 10 10 8 9 6 4 9 11 9 10 7 6 12 10 5 3 11 6 13 6 8 12 5 12 5 18 7 3 6 5 6 14 6 6 4 10 7 7 7 10 8 7 11 3 5 3 9 8 8 6 7 6 8 8 9 6 4 4 4 8 8 6 4 4 7 5 4 5 7 3 3 4 9 6 4 5 9 6 9 6 6 4 8 6 5 10 7 3 9 5 6 3 4 3 5 8 8 7 7 9 6 8 7 4 6 6 4 3 4 7 7 5 7 6 8 8 6 13 4 5 8 6 6 3 9 5 4 8 5 3 4 5 5 3 5 5 3 1 5 4 2 6 5 5 4 4 5 2 5 2 6 5 5 3 4 2 7 4 2 4 2 6 7 3 7 2 5 6 3 6 1 3 1 7 5 3 4 6 7 3 3 5 3 2 1 4 5 6 5 3 3 3 1 4 5 7 1 2 5 4 3 5 5 6 8 3 2 1 1 3 6 6 4 3 3 5 9 1 8 5 6 1 5 5 5 4 0 5 3 7 3 6 8 0 2 3 3 5 1 6 2 4 2 2 1 4 5 1 2 1 3 3 3 5 3 3 6 1 2 3 2 1 1 0 5 2 2 2 3 2 2 1 6 2 0 2 3 2 4 1 5 5 3 2 1 1 2 3 4 3 1 1 1 3 2 1 2 1 1 3 3 1 2 1 2 2 0 2 0 1 0 0 3 3 0 0 1 0 5 5 5 3 2 5 1 3 2 1 1 2 0 2 1 3 1 1 1 2 2 4 4 1 1 1 1 4 0 2 1 4 3 4 2 2 0 0 2 0 2 5 2 2 3 1 1 0 3 0 1 1 1 0 4 2 3 1 2 2 2 3 2 0 1 2 1 1 2 2 3 2 2 1 1 2 3 2 3 1 0 3 0 3 3 3 2 1 2 2 1 3 2 1 3 1 1 0 3 0 4 4 0 0 1 1 1 2 2 0 1 3 1 0 3 2 3 1 1 0 1 0 3 0 3 0 0 0 1 1 0 2 1 2 1 1 1 1 0 1 1 0 1 2 3 0 3 1 1 3 0 0 0 3 3 0 0 0 1 0 3 2 1 1 0 1 2 3 2 1 1 4 0 0 0 3 2 0 1 2 3 2 2 5 1 1 0 0 1 1 1 0 1 2 0 0 2 3 1 3 0 2 1 3 0 0 0 0 0 0 3 0 0 0 0 0 1 0 1 0 0 1 1 1 1 1 0 3 1 0 0 1 1 1 3 1 1 1 2 2 1 0 1 2 1 3 1 0 2 2 1 2 0 0 0 2 0 3 0 1 0 0 1 1 0 0 2 0 0 0 1 0 0 1 2 0 0 1 0 1 1 3 0 1 1 1 1 0 1 1 1 0 1 1 0 0 0 0 1 0 1 0 1 1 0 0 1 0 1 1 0 0 1 0 1 0 0 0 2 0 0 0 2 0 1 0 1 0 2 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 1 0 0 0 1 2 0 0 0 0 0 0 0 0 0 0 1 0 0 2 1 1 2 1 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
 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 = [
3 16 0 0
2 0 0 0
0 1 0 0
3 3 0 0
1 5 0 1
2 4 67 2
174 4 284 31
2398 13 334 95
16220 13 585 239
60640 20 874 517
152592 33 1196 803
356459 83 1763 1286
701036 192 2774 2157
1272230 564 4163 3733
1875805 1183 6102 5913
2315110 2425 9238 9180
2129012 3323 13488 13073
1435866 4324 18675 18511
701185 6752 25625 25467
229149 10432 32948 33266
74374 15511 40728 41058
55303 21761 48183 47602
57888 32787 55391 55570
62939 45549 63376 63788
68830 61048 72290 72783
77330 78064 82557 82431
86656 95965 92925 93727
96982 113244 105901 105210
108044 127964 116945 117575
117562 142060 129180 129030
127345 152502 138701 139025
134371 160871 145763 146503
139801 166914 152365 152535
143513 169773 154850 156304
147515 170900 157396 157800
147910 169855 157911 157419
146725 166867 155632 156137
147680 163727 155013 154759
148312 160276 152648 153417
146747 158107 152156 152265
147922 156537 152710 151746
149337 156050 152240 153667
151519 156878 154504 154700
154872 159923 156833 157920
160608 163986 163342 162643
167280 170291 169044 169523
176939 179414 178203 177996
186294 188697 187315 188505
197733 199052 197845 198604
209523 211346 209421 209073
220682 220810 219430 220751
228533 231031 229159 229877
235070 236445 235391 235516
237438 240103 238445 239476
237353 238643 238039 238413
232168 233555 232091 232355
222091 223935 221683 222779
208672 209685 209702 209004
191110 193564 192315 192570
173805 174485 174283 174310
157106 157707 157825 157836
139521 140683 139919 141116
123569 124459 123690 124372
109244 109663 108676 109400
99309 100160 100133 100270
94792 95123 95189 94917
92992 93089 93151 93207
87530 88239 88120 88075
85728 85802 85557 85602
86687 86293 85997 85997
84113 83630 83875 83823
79646 79937 79884 79903
72496 72700 72595 73136
64712 63703 63534 63895
54941 55351 54932 55336
44513 44751 44455 44215
32175 32223 32226 32344
22836 23023 23084 22991
17810 17711 17621 18043
11574 11757 11639 11782
6338 6354 6393 6391
2578 2547 2437 2507
125 113 126 109
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
