A = [
126321 127023 443666 125936 130081 118184 117634 119616 119455 116266 116636 118265 117980 117375 119978 120072 119692 121901 121682 120163 120905 120599 119349 120690 127583 202154 204201 207720 283946 276893 289537 292207 282367 288571 298857 297552 287234 291023 287946 283189 279394 279547 277867 275083 275437 270774 267693 266853 261379 256592 254803 253492 249900 247055 245205 243748 238778 235223 233577 230200 226203 224062 221745 218685 216271 213281 210947 208760 207097 202874 200183 197017 194432 191277 188137 186952 184053 181299 178668 177564 175359 171339 169483 166772 163282 160980 159170 156347 155505 152079 150237 147390 144976 142689 142630 139579 136632 134809 132449 130531 127433 125953 124848 123527 120847 119235 118352 115632 113155 111886 110050 108124 106105 103921 101912 100529 99450 97678 95973 95150 92836 91253 89427 87520 85080 84102 83746 81978 79450 78751 77944 77209 75390 74014 72810 71083 70618 68843 67862 65854 64952 63918 62961 62010 60931 59633 59046 57598 56189 55318 54384 53406 52172 51625 49932 49308 48126 47327 45976 45376 44327 43541 42785 41758 41699 39850 39623 38796 37613 36971 36609 35676 35249 34346 33966 33028 32499 32146 31150 30631 30344 29405 28764 28137 28285 26999 26527 26344 25599 25317 24795 24201 24125 23482 22965 22575 22096 21917 21540 20602 20496 20091 19592 19291 18729 18627 18320 17871 17101 17326 16762 16210 15877 15433 15448 15080 14675 14486 13992 13994 13771 13576 13308 13031 12352 12156 12038 12034 11922 11166 11261 10978 10829 10306 10230 10166 9665 9801 9386 9134 9035 9008 8808 8750 8756 8527 8375 8448 8155 8036 7704 7584 7610 7321 7219 6908 6851 6953 6499 6554 6564 6314 6079 6525 6128 5857 5780 5696 5609 5732 5609 5386 5425 5307 5340 5219 5063 4918 5189 5256 5317 4957 5047 4931 4924 4812 4590 4448 4590 4353 4404 4552 4394 4374 4178 4114 4007 3902 3980 4201 4027 3920 3821 3899 3916 3586 3564 4225 3634 3610 3459 3468 3473 3447 3408 3388 3524 3116 2920 2790 3127 2588 2568 2394 2276 2602 2445 2359 2046 2244 2071 2097 2084 2045 1880 2003 2145 2084 2071 2053 2159 2261 2253 2304 2173 2150 2036 1950 1933 1783 1932 2073 2052 1823 1979 1840 2072 1947 2073 1930 1936 2023 1965 2196 1885 2122 2220 1956 1747 1637 1874 1724 1579 1805 1729 1844 1950 1623 1663 1445 1428 1465 1270 1347 1740 1636 1627 1574 1621 1649 1643 1774 2017 1734 1883 1648 1350 1291 1221 1263 1261 1544 1230 1395 1421 1635 1255 1210 1245 1386 1261 1336 1207 1387 1287 1208 1233 1167 1133 1101 1144 948 1007 1023 1055 1070 986 1024 1130 1171 999 905 927 914 929 905 944 840 892 930 752 726 729 729 788 693 707 861 740 666 804 792 836 719 638 648 632 626 650 595 653 598 611 670 724 579 753 638 678 660 922 700 727 605 614 536 544 486 528 506 504 566 530 500 551 518 533 520 559 582 576 576 552 530 601 594 550 583 488 511 585 560 496 544 532 588 519 491 518 451 492 490 478 474 501 559 480 460 434 450 457 464 410 400 481 490 420 466 418 466 512 504 454 455 489 547 438 443 466 464 469 360 429 454 518 537 413 527 487 464 467 451 452 511 506 500 440 443 519 506 415 400 373 482 413 392 370 465 437 440 461 432 395 432 415 365 375 360 354 354 434 367 398 375 352 324 325 321 314 366 372 332 379 421 355 302 343 288 301 310 305 304 298 320 286 286 270 297 283 288 330 369 388 358 275 308 302 355 316 341 288 338 340 306 308 352 302 326 250 282 276 358 316 273 285 311 314 297 234 245 299 213 296 257 216 219 232 300 281 234 316 211 206 241 230 220 215 207 198 216 182 184 197 182 202 198 264 231 203 202 187 178 196 213 168 172 177 184 165 139 174 185 151 167 156 175 165 154 165 165 172 186 171 187 189 180 229 240 245 214 198 196 170 197 219 158 214 192 170 197 249 238 206 230 187 206 183 242 219 240 212 236 214 249 224 256 214 189 257 227 205 235 237 460 436 537 1167 761 503 543 378 390 363 513 250 300 601 407 551 418 492 359 522 443 418 530 222 357 288 307 177 162 139 171 153 146 207 165 193 178 235 222 203 244 201 169 281 257 165 112 113 124 151 156 143 152 232 247 246 146 164 164 209 161 192 176 179 163 165 144 150 125 105 127 176 140 130 192 163 140 112 126 146 147 136 112 149 151 118 113 149 105 114 110 96 94 111 116 117 150 97 91 122 115 127 108 133 174 175 138 201 191 210 164 185 199 182 205 153 165 162 194 225 141 147 201 121 120 105 110 139 88 126 93 100 135 119 114 128 168 122 123 103 124 123 138 181 135 176 179 164 151 152 169 141 151 134 121 95 107 94 92 85 109 81 72 124 77 112 119 87 87 85 76 65 91 89 100 81 71 79 65 73 70 79 85 85 86 92 112 72 72 82 76 67 70 79 79 56 72 62 86 71 55 70 63 60 49 70 62 52 79 60 54 63 48 70 42 49 82 52 47 33 46 49 37 33 40 47 51 41 46 52 60 49 58 66 54 41 44 39 44 62 51 58 39 38 43 40 42 45 33 44 49 32 24 38 42 40 49 32 41 48 30 31 37 46 37 55 58 53 48 43 33 42 33 27 29 36 34 34 39 31 30 40 32 34 26 32 35 34 35 49 40 47 24 35 25 83 52 58 77 64 64 62 59 60 63 62 61 54 53 64 44 58 45 54 50 64 70 41 31 39 19 29 36 102 80 96 124 94 131 201 30 36 28 41 42 41 29 34 35 34 28 39 43 35 40 22 35 28 25 38 27 34 34 19 22 25 22 36 24 24 32 37 33 28 36 29 26 34 32 42 27 43 52 81 33 58 33 24 14 40 22 23 32 29 26 35 44 29 27 19 17 21 31 20 19 24 27 32 21 20 36 33 26 26 24 30 29 18 23 15 20 30 20 19 20 12 28 23 11 22 28 30 31 39 39 55 32 39 36 39 36 47 66 49 47 46 57 58 50 37 40 48 45 60 27 76 53 51 66 58 45 53 75 87 57 80 98 31 44 44 40 53 40 37 42 34 45 23 28 55 18 23 16 24 16 44 20 45 37 32 22 20 15 24 14 25 17 16 18 26 15 21 12 20 12 16 10 23 17 22 17 9 16 22 16 18 8 17 15 15 10 13 11 17 14 17 13 6 11 8 14 9 16 13 18 19 12 22 24 14 21 10 18 10 15 6 16 15 19 14 12 13 18 11 7 13 13 12 23 19 15 16 13 15 10 16 17 33 23 41 32 26 43 39 23 24 30 19 24 19 29 33 21 27 26 33 20 23 29 30 17 26 24 18 15 25 21 29 18 21 11 1 9 7 9 9 20 11 11 3 10 13 10 6 12 7 8 9 14 5 7 9 4 8 9 11 13 7 9 14 9 13 10 8 11 11 9 7 8 8 15 13 9 6 5 6 6 5 3 12 11 12 21 5 16 12 13 12 6 9 7 6 5 9 5 9 6 4 8 14 8 7 17 8 8 9 5 2 6 8 3 6 6 13 4 13 15 10 12 16 9 10 13 20 10 14 9 9 9 7 17 5 10 8 4 7 9 4 6 13 6 8 12 9 5 7 5 4 5 4 6 6 9 9 9 4 3 7 7 4 3 4 3 4 8 10 5 6 2 3 7 3 8 5 8 7 8 2 7 5 5 7 8 4 6 11 6 7 7 6 4 1 8 3 4 6 5 2 6 4 4 6 4 4 8 4 5 4 10 7 5 7 10 4 9 6 6 4 7 9 8 6 6 10 5 4 6 8 6 7 5 3 5 3 15 29 6 16 21 12 16 7 1 5 6 11 10 4 3 4 5 2 5 8 5 8 3 5 5 4 3 3 3 1 4 4 6 7 2 4 3 6 3 5 6 8 4 5 6 10 11 8 4 8 5 2 6 6 7 3 5 3 7 4 3 2 2 5 4 4 10 4 3 11 12 3 4 0 7 5 3 3 6 15 7 7 2 2 8 5 6 6 5 4 5 0 8 5 4 5 7 9 8 9 1 2 8 7 5 3 6 4 6 6 9 9 14 4 12 8 4 4 7 9 7 11 8 18 10 7 10 12 15 15 22 10 14 17 18 15 23 25 16 14 17 21 19 21 14 18 29 18 22 288 230 352 472 487 327 290 185 257 95 2 6 3 2 12 12 10 8 7 9 5 15 14 7 12 3 9 6 9 3 2 5 8 3 11 9 10 16 50 14 13 11 10 4 9 6 6 11 5 2 8 1 2 7 4 18 3 9 9 13 3 4 10 4 6 5 12 12 9 5 5 1 5 23 7 12 4 4 8 10 10 2 5 9 3 4 1 2 3 4 4 5 4 5 3 6 6 2 12 1 1 4 12 2 5 6 4 3 2 0 4 1 4 1 0 3 2 5 2 2 3 0 4 3 5 2 1 3 2 3 2 3 4 3 5 2 2 3 2 3 2 4 1 4 1 6 2 1 4 2 6 3 2 2 2 2 3 5 3 3 3 1 3 2 8 3 1 6 2 5 5 11 4 7 4 2 0 7 3 6 1 2 2 6 2 4 5 5 0 3 4 4 3 4 4 4 2 5 2 5 7 4 7 5 3 3 2 7 3 4 3 2 3 6 1 6 1 5 3 2 4 2 3 1 4 4 2 1 3 6 1 3 7 1 1 4 6 1 5 4 4 2 2 3 1 4 4 3 4 9 3 4 6 1 3 3 3 1 0 1 3 1 3 3 2 2 2 4 3 4 2 1 1 2 0 7 2 2 1 1 1 2 1 0 1 3 2 4 5 3 3 4 2 9 6 2 11 4 2 7 2 3 0 4 2 4 0 1 2 3 6 1 4 2 2 3 2 3 2 0 2 2 10 4 
];
B = [
0 0 0
 53376 13160 40216
 28283 6453 21830
 98078 26355 71723
 29154 7044 22110
 31609 7726 23883
 44926 11098 33828
 50833 14399 36434
 37695 9570 28125
 99432 28670 70762
 30736 9428 21308
 35384 11445 23939
 45062 16744 28318
 61775 18126 43649
 28707 9451 19256
 90736 28669 62067
 31576 8560 23016
 30852 9023 21829
 32673 9511 23162
 67351 19559 47792
 36223 10264 25959
 102656 31328 71328
 58966 16418 42548
 55302 16752 38550
 111267 27729 83538
 157396 45035 112361
 24606 8276 16330
 467208 141380 325828
 13776 5965 7811
 29085 11421 17664
 18948 7454 11494
 31152 12077 19075
 13367 5257 8110
 102422 39131 63291
 10438 4617 5821
 21470 8406 13064
 14899 6320 8579
 26497 10545 15952
 6215 2756 3459
 120054 45558 74496
 2485 1417 1068
 4857 2600 2257
 6485 2642 3843
 21111 7750 13361
 10405 5459 4946
 3966 1894 2072
 6189 2689 3500
 12132 5314 6818
 200526 76818 123708
 4432 2611 1821
 5257 2657 2600
 4348 2245 2103
 8121 4378 3743
 13738 5702 8036
 212083 84522 127561
 7973 3893 4080
 5383 2564 2819
 7667 3831 3836
 87963 34870 53093
 72004 29768 42236
 10706770 4935527 5771243
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
12 18 8 3
6 10 0 1
5 11 0 0
15 15 1 0
18 11 3 2
31 8 14 0
323 19 46 2
1753 17 59 11
7464 43 83 40
24313 53 115 72
105677 62 165 115
162112 133 337 170
208762 242 762 273
263790 462 957 380
271009 829 1088 518
235332 1519 1048 953
161958 2363 1455 1254
83872 3357 2130 1737
32613 4312 2635 2925
11915 5115 2721 2719
6000 5357 4048 3792
4338 6110 5296 4349
4384 8372 4795 3478
4295 6439 6827 4307
4351 6254 6406 5190
4549 5193 4180 4096
4831 4052 3593 3769
4302 3757 3688 3775
4576 4549 4357 4219
4555 4637 4677 4474
4900 4888 4763 4898
5955 5124 5159 5095
5865 5624 5495 5797
7225 6557 6112 6209
6896 6780 6745 6827
7456 7863 7750 7848
8577 8701 8550 8591
10072 9976 9695 10111
10814 11005 10832 11041
12303 12366 12273 11937
13712 13699 13960 13768
15610 15456 15629 15502
17362 17516 17399 17527
19275 19656 19457 19643
22012 21929 22177 21931
24602 25277 24932 24709
27519 27723 27987 28038
30555 30589 30860 30537
33980 33619 33617 33807
36299 36379 36746 36910
39270 39462 39397 39011
41531 41612 41315 41223
42992 43006 43716 43294
44673 44766 45312 44890
46556 46640 46359 47073
48370 48259 48028 47789
50364 50327 50138 50125
52353 51833 52714 52267
54352 54042 54617 54249
55541 55847 55546 55428
55454 55449 55579 55819
53480 52896 53435 53098
48231 48202 48260 47793
38858 38173 38488 38830
25638 25671 26085 25548
12578 12313 12215 12292
3339 3383 3407 3379
354 391 334 394
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
