A = [
382678 410251 1582135 284927 314535 272213 263769 268078 260097 243511 242652 242669 242489 236215 235393 229967 226245 226279 222676 220689 220235 218094 216041 216103 216928 263129 264591 265925 312071 314127 317730 319790 321770 324821 325620 324515 320945 319280 317046 314310 312242 311939 308646 308517 308823 305525 303538 300616 298027 294015 293722 291298 289937 288329 287133 285269 282640 280354 277667 275451 272576 270169 268558 266395 265000 264721 261429 259984 258006 254588 252641 250206 247451 244991 244581 241185 240612 237929 235985 233091 231354 228545 226544 224840 222363 220462 218587 216152 214719 212367 209745 207855 206418 203528 202999 200034 197994 196659 194703 192532 191006 188763 186173 183795 183598 181233 180261 178629 175753 174233 172058 170054 168518 166852 165396 162657 161544 159866 158339 156051 154203 153272 151066 148838 146813 146244 144487 142558 140880 138890 137910 136236 134639 134175 131924 129601 128620 127251 126050 124108 122958 121439 119924 119235 117447 116271 114455 113499 112337 110830 110644 108214 107079 106152 104429 103344 101676 100291 99337 98143 96896 95843 93937 92410 90946 90047 89364 88545 87072 85716 84888 83913 82315 81680 80399 79053 78348 77116 75823 75589 74557 73765 72796 71332 70856 70375 68952 67593 66471 66049 65604 64601 63543 62407 61555 61601 60270 59724 58914 57647 57240 56156 55334 54267 54010 53206 52537 52140 51603 50798 50088 49211 48837 48371 47221 46977 46269 45707 44511 44550 44012 43340 42767 42166 41719 40804 40074 39989 39213 38562 37951 37736 36881 36644 36073 35348 34819 34459 34103 33543 33094 32781 32460 32144 31936 31137 30820 30268 29853 29389 29227 28781 28696 28136 27747 27199 26946 26841 26080 25781 25675 24974 24728 24426 24000 23545 23616 23165 22906 22328 22472 22240 21592 21664 21222 21053 20684 20113 20263 19947 19607 19376 19244 19143 19043 18533 18081 18106 17793 17458 17446 17076 16856 16987 16594 16416 15960 15971 15817 15309 15370 15288 15120 14953 14874 14345 14329 14090 14017 13734 13589 13604 13402 12959 13082 12516 12823 12610 12107 12042 12161 11518 11255 11487 11048 10838 10750 10595 10529 10303 10212 10208 10263 9867 9730 9692 9697 9434 9178 9145 9280 9174 9012 8827 8769 8668 8434 8534 8298 8039 8232 8893 7955 8015 7887 7589 8634 7464 7600 7465 7437 7289 7177 7279 6876 7044 6868 6680 6495 6571 6557 6332 6327 6338 6111 6124 6084 5908 6086 5730 5840 5711 5620 5547 5908 5556 5296 5332 5293 5295 5360 5259 5449 5304 5051 4961 4784 4685 4713 4694 4781 4647 4386 4479 4442 4395 4269 4219 4367 4206 4064 4074 4036 4009 4133 4038 3899 3814 3753 3642 3676 3764 3534 3488 3483 3594 3442 3371 3522 3420 3303 3316 3279 3273 3242 3263 3270 3157 3039 2945 2998 2886 2941 2840 2840 2829 2791 2812 2731 2772 2752 2744 2721 2552 2615 2502 2600 2573 2470 2523 2521 2452 2427 2390 2438 2406 2348 2506 2343 2298 2507 2323 2292 2261 2239 2171 2113 2155 2147 2187 2022 2054 2068 1929 2019 1966 1981 2001 1929 2036 1930 1927 1882 1887 1933 1836 1835 1778 1830 1865 1735 1774 1702 1709 1735 1748 1733 1744 1681 1657 1620 1610 1589 1566 1602 1512 1615 1497 1529 1496 1485 1505 1532 1473 1500 1450 1476 1393 1506 1480 1405 1468 1457 1440 1352 1387 1372 1451 1357 1391 1418 1409 1407 1425 1382 1451 1337 1551 1435 1329 1468 1356 1306 1370 1295 1340 1302 1266 1268 1314 1244 1352 1222 1256 1284 1147 1090 1129 1180 1116 1194 1149 1176 1224 1199 1243 1188 1190 1120 1182 1145 1058 1066 1141 1139 1052 994 1034 1045 1007 1028 958 1060 1021 1098 1039 1009 961 1012 984 939 942 903 949 936 882 939 857 898 922 847 894 882 856 863 783 891 817 817 857 784 820 826 860 817 797 798 845 778 750 829 833 799 773 801 807 790 829 755 764 803 744 754 722 743 666 694 686 708 655 640 691 682 679 635 647 670 644 601 655 649 638 648 631 671 656 668 652 633 596 616 567 671 584 603 569 579 580 595 566 573 601 527 540 559 564 542 593 568 540 593 615 603 595 526 557 577 510 525 563 537 551 538 516 568 524 527 512 534 514 481 515 501 489 497 527 486 476 516 520 510 509 551 544 504 546 515 499 531 540 533 523 584 558 581 705 712 621 611 590 571 505 529 600 480 484 573 521 571 511 546 536 553 518 463 449 464 502 447 435 482 477 412 424 404 425 403 432 399 450 467 467 461 505 462 434 452 415 420 404 416 478 400 399 426 442 427 484 370 401 388 380 358 398 366 376 388 333 390 389 381 361 325 373 385 330 332 349 417 336 296 333 335 337 342 313 338 311 340 349 348 317 307 299 308 325 318 352 312 342 344 329 338 308 309 341 331 342 340 341 322 336 340 295 327 273 320 319 320 300 293 292 278 296 275 316 279 301 266 253 282 239 254 253 234 237 246 249 265 241 221 238 260 293 278 246 272 253 252 280 289 259 252 296 244 225 271 248 230 254 240 254 225 228 239 247 231 220 258 271 216 176 204 202 206 209 203 226 196 216 210 231 199 219 198 192 187 219 233 232 366 224 219 200 201 165 214 228 174 217 190 191 176 185 191 152 172 185 182 180 176 164 169 195 179 165 158 207 184 176 202 192 183 161 197 178 169 192 165 183 149 165 170 165 165 149 168 139 151 148 133 158 142 146 135 145 133 147 150 132 160 179 158 146 149 127 145 127 155 118 138 120 141 145 157 163 167 127 162 147 165 156 130 139 146 145 149 140 144 151 124 143 126 123 131 149 126 125 137 138 146 120 155 133 139 125 116 107 139 111 115 120 143 133 142 120 105 143 121 117 133 111 117 113 120 125 151 120 120 111 115 121 105 135 133 124 156 114 122 153 147 123 115 131 125 148 122 109 123 120 127 120 135 145 118 120 96 106 110 116 110 110 139 108 97 127 102 98 100 118 95 102 122 101 110 127 106 107 86 101 91 99 109 101 81 94 125 94 89 90 91 86 100 103 90 101 103 89 95 102 93 111 88 96 103 99 97 95 105 100 96 112 126 99 104 101 97 106 94 108 94 79 93 106 81 84 98 76 82 82 99 73 86 98 76 90 85 105 72 89 79 101 92 81 106 71 86 93 101 95 82 90 85 85 110 92 74 83 80 76 85 94 109 84 90 89 85 88 90 89 93 84 98 79 86 80 88 85 82 76 93 78 82 71 66 64 79 81 76 68 67 79 76 67 73 72 69 70 67 59 51 82 58 78 59 50 74 56 62 52 43 54 66 72 52 43 70 51 49 76 57 60 50 53 51 62 45 67 65 43 83 48 70 57 58 49 57 68 55 82 47 77 58 74 73 64 49 55 46 41 44 83 48 64 70 59 61 53 53 39 54 69 63 51 54 48 42 60 63 52 47 65 62 68 75 65 66 68 52 66 56 60 59 53 46 45 47 71 57 48 45 62 52 54 53 45 45 50 47 50 45 53 45 49 38 50 47 48 43 48 41 46 39 38 40 51 45 30 37 49 43 37 46 42 47 33 49 43 39 46 36 41 62 40 57 45 38 37 33 31 36 41 47 33 42 35 40 31 48 35 41 39 43 29 34 39 35 33 41 38 42 41 50 44 35 42 32 35 38 29 27 36 35 41 44 42 33 39 48 39 30 36 41 34 51 37 40 55 46 57 51 60 60 55 53 55 62 51 35 47 46 48 45 43 39 41 31 44 45 49 36 34 43 48 53 45 28 36 47 36 37 40 41 44 39 40 30 43 37 31 40 39 36 35 40 30 33 38 34 31 24 31 30 32 25 33 31 31 39 36 30 42 24 26 33 32 25 36 29 25 35 30 30 25 20 35 27 23 22 22 29 22 26 22 41 31 28 23 35 33 32 34 31 30 27 27 32 24 19 35 23 22 32 24 29 26 25 31 29 26 36 31 23 28 26 26 28 25 30 31 19 27 23 22 23 32 35 21 24 26 23 21 23 24 13 28 24 28 32 18 22 20 22 25 20 32 21 18 20 14 22 22 29 31 27 19 21 15 29 26 16 18 21 23 20 21 19 23 16 28 29 16 16 26 17 18 23 29 21 30 15 26 20 31 21 18 27 27 19 22 22 24 22 33 24 23 23 33 24 25 29 27 27 34 11 35 25 21 21 31 23 25 30 20 21 21 28 15 18 27 20 33 26 35 30 35 28 29 23 24 21 29 24 23 25 19 18 22 12 19 18 25 18 24 33 28 20 28 17 20 18 32 19 21 25 29 22 23 19 14 20 32 22 30 19 20 41 60 127 122 141 113 79 90 99 41 19 12 16 17 14 24 17 23 20 23 26 21 24 25 16 26 27 19 18 18 14 27 16 20 23 19 26 24 33 26 32 32 30 33 23 15 24 17 10 17 16 18 15 20 18 20 16 25 15 15 18 15 15 14 17 15 13 25 16 13 21 15 21 13 14 17 13 23 25 21 28 16 20 17 19 22 12 19 12 16 13 17 23 18 13 14 17 16 19 19 26 18 28 16 12 22 13 18 14 8 15 12 14 12 14 16 21 16 10 16 15 11 11 14 14 14 13 24 26 7 11 19 14 18 19 19 14 14 9 12 13 16 24 11 13 12 13 13 10 23 16 19 11 14 9 14 15 13 22 18 15 16 11 18 23 15 23 14 12 15 18 14 21 18 21 18 11 13 21 22 16 37 23 27 16 17 22 11 16 16 14 13 13 29 22 19 23 13 14 11 14 22 15 9 13 19 18 9 8 13 13 16 17 19 18 10 21 13 17 15 16 8 12 20 18 15 15 18 14 21 9 22 22 12 14 11 13 14 12 15 17 13 12 10 15 17 11 19 15 14 13 7 19 14 20 14 14 14 18 21 11 9 10 12 12 16 16 6 20 16 9 13 26 15 12 13 16 13 14 12 13 22 11 18 13 16 13 11 19 12 13 18 13 14 12 16 8 22 18 10 19 18 17 19 16 17 12 14 18 14 16 14 13 21 24 26 19 14 9 10 23 11 3 16 
];
B = [
0 0 0
 125832 36012 89820
 59651 16783 42868
 210850 69960 140890
 132458 39468 92990
 76731 22219 54512
 207136 70866 136270
 162879 50602 112277
 92292 27678 64614
 279964 93936 186028
 292187 91755 200432
 52302 15226 37076
 837113 284969 552144
 110178 35022 75156
 35008 10592 24416
 186853 73333 113520
 59448 21823 37625
 18394 6009 12385
 204957 81394 123563
 16933 5394 11539
 17477 6053 11424
 3949 1350 2599
 99 30 69
 3958 1416 2542
 303710 123360 180350
 20080 6712 13368
 26038 9594 16444
 315921 130016 185905
 18436 6930 11506
 38919 14747 24172
 499684 197068 302616
 36207 14040 22167
 64633 25652 38981
 352527 151567 200960
 243654 105062 138592
 406813 179153 227660
 735028 322591 412437
 604973 247116 357857
 375013 161814 213199
 856137 383151 472986
 340483 134545 205938
 23051 9047 14004
 774549 339815 434734
 12234 4827 7407
 21797 8741 13056
 1054544 480707 573837
 22500 9171 13329
 277354 110282 167072
 1439413 710346 729067
 274973 112510 162463
 9 4 5
 10230345 5299554 4930791
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
54 78 0 1
54 17 0 1
97 22 1 2
143 32 0 0
85 33 1 0
90 32 35 1
243 61 59 6
1190 80 81 23
6997 75 109 40
30335 115 164 64
76417 159 195 106
168069 179 277 175
331013 270 382 246
626178 366 517 366
957708 431 686 535
1181509 703 932 852
1100376 918 1295 1214
826509 1404 1633 1618
528253 2216 2126 2123
284257 3078 2595 2548
127158 4060 3092 2972
36546 5134 3297 3296
8296 5376 3496 3361
5879 4506 3510 3516
5289 4536 3680 3702
5310 4943 3712 3813
5524 4447 3740 3862
5061 4392 3932 3951
5056 4739 4271 4075
5121 4781 4569 4583
5211 5093 4750 4732
5796 5527 5010 5150
6454 6015 5428 5382
6926 6388 5888 5794
7157 6847 6469 6523
7769 7478 6778 6987
8406 7907 7628 7585
9076 8860 8494 8415
9581 9458 9218 9603
10469 10405 10195 10288
11672 11706 11303 11396
12872 12879 12804 12919
14463 14315 14199 14359
16113 16203 16237 16050
17889 17868 18015 17958
20022 20499 20401 20747
22649 22920 22942 22905
25208 25380 25122 25116
27496 28013 27746 27923
30735 30307 30341 30124
33020 32742 32545 32890
34858 34640 34238 34715
36882 36846 36458 36329
38145 38392 38376 38316
40697 39960 40504 39958
40937 41605 41482 41172
43900 43785 43722 43533
46777 46145 45947 45969
48181 47820 47684 47838
50222 49633 50370 49734
52168 52052 52065 51615
52229 52237 52357 52201
50671 49845 50707 50394
44163 44139 44048 44802
33344 33655 34022 33369
19547 20018 20022 19231
9622 10006 10159 9559
6660 6565 6556 6097
5988 5439 5569 5199
4944 5055 5856 4532
3661 3759 3678 3895
2671 2229 2482 2734
221 222 198 193
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
