A = [
529555 550222 2243825 457063 472892 428331 414952 420692 407926 381731 379055 379718 374715 370017 364691 359564 354541 352483 347592 345365 344123 339017 337685 336770 337093 401298 399802 401449 464831 465341 469428 471021 473205 475787 475660 472915 467900 463964 461919 455506 453086 451533 449370 447715 447606 442310 438890 434591 429196 427329 422937 419798 418367 416664 414496 411827 408483 403927 401228 396754 393523 390569 389095 388435 381966 381568 379848 376319 372230 368380 365729 362307 359277 355788 354196 351571 348615 346238 341984 339470 336254 333139 330882 328490 325028 322751 319725 317661 315354 312125 307936 306131 303392 300428 298016 294422 293490 290917 288874 285787 282322 281717 277246 275794 273865 270773 269056 268348 263437 262724 259758 255642 255085 251460 250103 248563 244935 243632 241138 238516 236823 233662 230828 228571 226056 225227 223082 220135 218679 216548 214676 212883 210258 208624 206718 204108 201721 200582 197817 196535 194297 193065 190659 188776 187166 185526 183129 181803 179826 177691 175967 173794 173134 171360 168521 167312 166339 164260 162287 160010 159608 156959 154691 153302 151003 149577 148154 147422 144685 142987 142167 140709 138126 137437 135524 133920 132886 131016 129473 128196 127013 125502 124286 123051 121157 120436 118553 117171 116211 114145 113748 112168 110732 109509 108245 106433 105927 104819 103458 102663 101360 99448 98700 96793 96162 94946 93815 91932 91533 89800 89091 88321 87475 85851 85111 84135 83159 81671 81274 80118 79214 78445 77056 75261 75105 73314 72547 72471 70943 69982 69268 68926 67265 66411 65468 65230 63573 62808 61872 61448 60848 59816 59280 58713 57896 57228 56603 55631 54991 53836 53609 53366 52217 51381 50889 49808 49330 48831 47805 47315 47055 45443 45356 44884 44357 43580 42989 42243 41865 41417 40891 40333 39928 39447 38750 37825 37703 37117 36777 36388 35813 35555 35436 34527 34253 33634 32753 32889 32672 31826 31554 31076 30321 30495 29913 29678 29141 28452 28284 28162 27572 26990 26858 26629 26287 25908 25643 25000 24834 24391 24399 23729 23519 22993 23229 22711 22339 22139 21507 21358 21058 20569 20048 19800 19639 19397 18942 18445 18210 18161 17967 17534 17271 17505 16905 16929 16333 16459 16237 15819 15821 15887 15476 15427 14996 14753 14622 14419 14012 13903 13758 14400 13800 13238 13151 13008 14194 12560 12751 12481 12341 12106 11835 11931 11506 11379 11322 11107 10880 10789 10691 10433 10417 10286 10212 10050 10005 9795 9729 9421 9333 9155 9099 9070 9225 8875 8757 8871 8565 8476 8594 8217 8426 8300 8275 8045 7765 7458 7369 7428 7306 7190 7110 7063 6996 6790 6667 6690 6614 6421 6372 6338 6100 6247 6226 6146 6034 5911 5824 5724 5584 5575 5508 5516 5424 5193 5260 5159 5256 5300 5066 4938 4959 4920 4910 4829 4771 4671 4711 4472 4488 4414 4294 4235 4275 4096 4184 3944 4094 4026 3967 4057 3868 3854 3863 3741 3782 3712 3656 3592 3428 3459 3328 3404 3447 3390 3345 3326 3210 3347 3258 3209 3098 3141 3125 2922 3030 2964 2855 2754 2837 2911 2769 2759 2722 2799 2802 2671 2716 2706 2680 2619 2648 2630 2554 2601 2443 2486 2480 2401 2418 2419 2320 2365 2315 2397 2303 2269 2323 2267 2190 2156 2169 2212 2188 2068 2153 2028 2052 2061 2059 1937 1971 1985 1969 1912 1888 1846 1937 1953 1889 1846 1824 1909 1869 1842 1784 1824 1831 1896 1935 1812 1793 1853 1743 1975 1808 2021 1883 1653 1807 1697 1727 1709 1684 1769 1574 1669 1643 1603 1497 1674 1609 1719 1685 1437 1363 1372 1445 1382 1453 1498 1492 1533 1569 1591 1588 1498 1479 1394 1378 1367 1404 1392 1374 1296 1246 1294 1245 1257 1235 1296 1324 1355 1328 1247 1305 1241 1300 1254 1206 1136 1179 1212 1182 1079 1096 1170 1103 1082 1138 1126 1073 1055 1063 1038 1121 1084 1090 1046 973 1006 1064 1012 994 931 921 981 957 974 950 1021 949 961 899 927 935 944 857 907 935 922 883 920 883 867 871 789 844 824 833 816 854 869 772 840 795 823 812 848 794 831 804 711 804 806 818 775 752 726 749 781 725 747 686 719 752 724 745 728 701 706 728 674 655 654 684 675 662 686 722 721 694 680 637 668 708 598 626 674 624 665 633 621 676 679 640 638 649 629 623 606 611 660 611 536 607 581 651 637 636 631 648 628 640 622 591 627 603 628 610 648 682 691 728 898 859 704 758 742 664 636 692 741 618 624 746 695 660 637 654 683 646 617 578 597 593 589 529 507 524 496 455 526 507 489 518 534 525 546 579 559 534 620 533 578 486 534 526 487 469 527 491 513 523 483 532 589 447 495 454 492 426 482 472 473 490 441 491 473 487 424 455 470 484 452 427 448 484 410 396 396 412 395 414 407 378 411 413 400 396 371 377 373 364 422 382 324 386 372 383 391 405 400 404 410 403 400 379 389 440 437 413 382 405 372 367 362 359 357 370 375 363 345 364 349 350 325 332 326 344 315 290 267 300 329 310 299 323 299 290 319 359 345 321 307 357 371 322 357 319 340 321 326 302 304 272 330 328 293 294 286 292 280 279 253 299 263 289 303 240 251 268 227 288 272 303 287 257 271 261 238 263 257 252 255 265 289 311 286 394 272 283 238 286 264 242 245 257 226 251 252 199 213 220 209 219 206 223 213 212 213 196 204 199 217 222 273 201 195 198 211 230 227 222 230 228 231 190 232 215 195 210 179 196 173 191 172 187 188 180 185 176 163 181 165 161 188 157 157 210 191 189 177 172 182 185 173 175 187 172 168 154 199 188 178 187 170 175 202 179 186 159 155 169 162 176 158 154 166 141 160 152 159 168 136 172 158 179 176 139 135 182 159 183 153 138 146 157 151 177 146 159 145 150 165 149 152 147 151 161 164 148 146 132 150 177 164 157 147 147 160 135 129 140 161 184 159 170 162 140 153 187 153 143 160 153 142 163 144 145 143 184 169 128 145 142 138 117 140 139 136 136 136 133 154 122 140 137 155 114 131 135 126 125 142 140 112 94 131 135 153 133 114 106 140 124 130 138 117 120 113 113 107 138 121 132 122 106 142 111 125 117 139 120 127 130 133 127 129 118 126 134 126 104 124 123 110 104 105 120 98 130 120 97 113 105 115 124 111 103 120 116 127 113 118 100 120 126 108 113 107 108 103 135 113 120 102 102 142 120 113 122 110 116 104 118 104 123 121 116 116 113 114 114 101 101 145 113 111 91 116 93 102 95 113 115 97 101 84 98 95 100 69 88 96 81 70 74 77 82 91 82 67 75 102 88 100 91 80 71 92 74 70 71 80 81 74 81 74 78 88 84 77 78 63 68 58 70 79 74 68 73 73 91 57 88 66 69 76 67 64 65 62 69 78 70 60 79 79 71 77 82 86 76 72 62 60 60 71 75 76 66 62 66 54 71 59 66 69 58 68 65 61 76 77 66 66 67 63 64 81 82 83 58 85 71 88 57 77 74 63 68 47 71 65 55 90 75 63 66 59 49 49 62 53 56 48 65 59 62 71 47 54 53 51 42 44 56 42 57 52 50 56 50 45 44 57 41 47 56 62 51 37 40 38 47 52 57 49 53 47 56 46 47 64 60 52 41 44 60 53 54 48 37 54 53 37 45 45 36 42 53 43 33 39 44 46 56 31 48 41 45 53 49 53 45 44 53 44 49 37 52 43 51 43 48 53 50 34 40 41 43 38 51 56 50 59 63 56 57 46 69 68 56 77 67 68 57 55 55 63 53 53 54 59 59 41 53 59 48 66 38 51 57 59 40 56 43 42 45 41 57 47 50 50 50 41 49 25 43 48 48 38 35 39 54 41 45 45 36 37 47 46 42 42 40 26 37 46 36 36 34 35 33 30 41 33 38 34 37 35 31 29 28 39 44 39 33 20 28 31 28 26 33 43 29 35 37 32 36 30 38 35 38 36 39 46 37 37 33 30 46 29 28 47 33 32 44 37 37 35 39 29 37 34 27 26 21 31 35 34 42 28 31 25 30 37 30 29 29 22 49 21 34 25 26 34 27 26 27 25 28 34 23 23 30 22 38 23 16 26 26 31 35 24 33 29 33 25 28 27 18 22 21 19 27 25 24 27 30 17 26 28 26 19 20 24 22 33 30 24 40 32 29 36 25 29 30 42 30 38 30 42 30 41 34 34 28 30 29 26 29 27 25 34 35 29 33 24 35 33 29 37 25 21 25 27 40 19 29 34 36 47 31 29 34 32 29 39 19 32 40 30 19 20 16 26 21 25 26 22 15 24 25 24 25 32 35 22 33 30 24 19 26 27 30 22 32 28 29 28 26 29 38 29 29 91 135 157 170 122 94 88 108 53 22 27 23 21 21 25 23 20 27 18 15 26 27 32 13 29 33 27 22 26 30 20 25 21 16 31 29 41 51 30 32 48 34 40 35 23 27 23 18 23 14 13 24 19 9 20 21 18 27 25 21 22 21 24 25 16 16 27 26 29 17 11 22 25 27 19 24 20 24 21 22 16 19 17 24 24 17 19 13 26 17 19 18 18 19 24 16 31 32 19 25 31 16 20 29 27 16 23 19 15 22 15 11 16 20 27 18 18 14 15 17 14 20 13 12 18 13 14 21 11 16 20 20 17 22 13 14 17 21 16 13 9 22 20 18 15 15 20 17 20 21 14 17 16 16 14 16 24 14 31 20 23 15 22 19 24 18 19 24 25 14 15 10 32 23 25 17 25 23 20 21 25 10 17 22 22 24 32 25 22 17 22 27 27 28 15 21 19 17 14 23 16 20 22 22 21 24 27 12 18 14 19 16 15 12 22 9 20 22 17 27 19 21 15 23 25 27 24 12 18 20 18 16 21 12 16 14 12 14 24 15 18 15 18 10 12 20 15 23 11 18 14 17 16 13 11 11 14 10 20 12 16 11 14 16 18 12 17 11 16 19 16 11 10 14 22 13 19 10 11 16 20 17 14 20 18 15 8 21 19 11 19 17 16 14 21 19 16 20 19 7 14 18 16 25 21 16 17 17 12 20 16 14 14 17 19 21 16 15 19 20 17 18 13 
];
B = [
0 0 0
 182062 54916 127146
 87315 26030 61285
 302996 105290 197706
 192545 60541 132004
 112918 34492 78426
 297673 106464 191209
 236282 77826 158456
 131718 41792 89926
 403406 142337 261069
 418819 138703 280116
 76139 23689 52450
 1200021 428660 771361
 160587 55513 105074
 51069 16957 34112
 279635 115607 164028
 89866 35191 54675
 27504 9908 17596
 309882 130357 179525
 25217 8904 16313
 26687 9745 16942
 6034 2196 3838
 146 50 96
 6116 2413 3703
 459896 197690 262206
 29965 10761 19204
 39544 15748 23796
 482589 211446 271143
 28111 11562 16549
 60240 24947 35293
 751187 315857 435330
 55749 22804 32945
 100031 42218 57813
 546757 249961 296796
 372240 169383 202857
 620593 286761 333832
 1133457 523349 610108
 915255 398271 516984
 574421 261576 312845
 1327609 626460 701149
 508638 216203 292435
 35281 15038 20243
 1192932 556461 636471
 19043 8194 10849
 32976 14041 18935
 1636072 787835 848237
 34871 15322 19549
 406583 173326 233257
 2268860 1166902 1101958
 409407 179757 229650
 10 5 5
 15784775 8441296 7343479
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
57 85 1 1
52 13 0 0
149 18 0 0
217 22 1 0
169 27 1 0
143 30 25 1
271 72 78 8
1083 85 88 25
5906 99 116 58
23513 141 206 80
53552 166 242 116
114216 243 333 179
229869 294 487 300
478431 424 674 455
905788 596 898 758
1551597 863 1276 1179
1973185 1230 1789 1673
1791838 1908 2302 2373
1229656 2933 3022 3054
643369 4049 3785 3753
243525 4919 4284 4299
56214 5919 4535 4605
13342 6050 4751 4669
9723 5581 5009 4884
8673 5876 4942 5334
8010 6565 4999 5203
8141 5827 5219 5339
7583 5821 5453 5650
7605 6340 6009 5912
7439 6567 6268 6176
7679 6873 6702 6826
8483 7462 7068 7205
9222 8584 7731 7743
10251 9166 8451 8557
10833 9853 9571 9673
11558 10934 10644 10345
13096 12136 11744 12069
14294 13575 13329 13209
15484 14943 14955 14941
17159 16945 17124 17081
19306 19331 19128 19169
21881 21641 21657 21689
24506 24689 24390 24453
27967 27889 28017 27676
31371 31586 31485 31534
35764 35928 36229 36478
40244 40366 40850 40400
45439 45123 45081 44906
50301 50018 50276 50543
55992 55522 55495 55115
60514 60546 60553 59986
64464 64294 64192 64506
68319 68301 68283 67236
71450 71544 71335 71683
75456 74730 75590 75477
77882 77997 77903 77747
82341 82782 82407 82294
87063 86579 85963 86219
90703 89151 90518 89939
93836 93427 93625 94480
97428 97989 97266 97107
98095 97708 98010 97506
94473 93824 94722 93560
81165 82510 82292 82152
60836 61401 61630 60145
34609 35067 34655 33945
15185 16021 15595 15000
9365 9220 9604 8623
8092 7095 7376 7016
6380 6692 7685 5880
4808 5030 4761 4998
3832 3082 3511 3595
287 306 224 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 
];
