A = [
2138748 2963079 38271830 1594480 1705918 1647376 1592708 1679789 1610119 1575986 1565329 1514776 1535358 1503744 1482877 1492470 1445585 1450157 1452139 1412873 1397471 1395367 1384130 1383206 1370281 1375950 1382614 1366013 1369291 1352726 1353637 1360266 1340159 1328391 1329312 1339574 1323955 1311386 1316001 1322388 1308932 1319448 1327490 1323552 1333683 1333513 1313334 1322367 1316800 1302678 1299017 1272736 1281989 1279582 1259065 1265520 1256829 1263015 1249641 1231833 1231787 1221127 1208950 1193775 1185244 1177621 1160605 1149502 1140209 1126811 1121418 1122957 1117293 1112021 1111903 1108681 1101182 1095845 1080190 1068340 1062394 1055942 1043888 1034041 1028675 1018135 993303 957361 944155 933147 926546 917754 914770 907177 899552 894330 887567 881808 877957 868581 864872 859312 854663 848836 842269 838287 832807 825316 821541 818211 810380 808859 803935 797268 792013 788024 785053 779313 773387 769693 764211 756790 751383 746443 739265 732995 728288 722260 716859 710101 705019 699985 692773 689319 683988 678796 671242 667578 662254 656024 650511 644775 640592 631770 626334 621681 615646 610337 603823 599472 592537 586460 580892 574459 569751 563369 557283 551987 547694 543046 536706 530908 526350 520472 514119 508463 505211 500347 493968 488600 483093 478671 475703 470964 468330 460946 457200 452173 446577 441640 437154 432997 427778 423103 418997 415657 410358 407306 403230 398311 393768 390296 385106 380669 376030 372542 369312 364725 360895 357839 354436 349187 345553 343280 337742 336055 331494 326873 323942 318669 315321 311648 307693 303953 301277 298317 294819 291384 288327 284127 281566 278645 275698 271704 265978 261818 257961 253751 248897 243924 241140 238361 234389 230859 228584 224560 221834 220043 216017 212571 210361 206485 204764 201859 199303 196561 193632 191130 188741 187197 183545 182012 178372 176687 173761 171568 169533 167467 164328 162212 160252 157221 156200 153693 151006 149534 147272 145968 143502 141478 139484 137935 135538 134109 132315 129588 128009 127394 124282 123137 121014 119389 118282 115971 114874 113010 111216 109978 107598 106503 105300 103427 101765 100975 99203 97681 96289 94151 93117 91991 91471 89309 87968 86675 85119 84156 82724 81640 80699 79522 78047 76445 76064 74405 73030 72526 71447 70006 68797 68161 67172 66291 65395 63946 63126 62490 61133 60405 58908 58340 57612 56585 55804 54827 54011 53071 52406 51585 50852 49938 48743 48435 47365 46787 45957 45271 44588 44135 43528 42519 41336 41585 40691 40048 39269 38608 37911 37636 36937 36427 35576 35301 34668 34185 33872 32568 32535 31999 31499 30939 30182 29680 29585 29227 28700 28044 27583 27313 27324 26565 25812 25727 25283 24904 24251 23817 23161 22981 22785 22268 22044 21551 21360 21095 20499 20008 20029 19446 19601 18921 18756 18457 18079 18188 17848 17281 17110 16771 16644 15980 15762 15496 15256 15165 14955 14522 14613 14081 13804 13782 13608 13329 13052 12897 12818 12441 12538 11753 11903 11716 11490 11231 11133 11180 10956 10404 10401 10378 10211 9906 9873 9678 9662 9236 9396 9103 9082 8720 8779 8665 8527 8361 8354 8106 7804 7744 7706 7444 7377 7528 7324 7176 7142 6914 6749 6661 6641 6509 6461 6344 6227 6246 6060 5758 5899 5758 5650 5677 5570 5461 5286 5215 5159 5198 4929 5006 4938 4741 4709 4778 4661 4542 4430 4388 4426 4270 4369 4203 4188 4106 4148 3929 3922 3868 3726 3796 3780 3643 3608 3599 3603 3435 3345 3302 3270 3250 3146 3129 3090 3185 3097 2892 3078 2957 2950 2841 2896 2828 2761 2753 2684 2646 2667 2580 2564 2534 2515 2519 2421 2383 2504 2395 2375 2320 2312 2235 2262 2257 2264 2170 2199 2195 2149 2083 2115 2081 2073 1958 2034 2020 1992 2003 1986 1855 1883 1833 1884 1844 1828 1887 1887 1763 1696 1788 1666 1713 1707 1655 1627 1634 1661 1581 1610 1565 1572 1593 1563 1538 1486 1474 1494 1526 1420 1467 1442 1440 1455 1413 1457 1352 1405 1359 1350 1313 1397 1285 1248 1329 1211 1293 1270 1322 1345 1196 1165 1230 1293 1174 1220 1156 1153 1189 1136 1134 1091 1170 1198 1096 1125 1071 1089 1097 1061 998 1026 1072 1082 1035 1104 991 1078 1038 1018 999 1028 963 978 1027 1113 992 1014 947 973 981 1046 933 909 960 970 1036 984 956 935 918 957 960 975 949 930 907 935 967 968 936 911 949 922 912 885 911 909 985 868 992 950 877 938 850 863 931 831 872 882 861 846 837 870 860 818 817 791 786 790 775 834 794 740 782 746 764 734 730 752 760 719 725 737 700 699 649 653 676 690 676 677 672 700 675 708 713 692 679 683 695 724 705 722 665 642 667 647 661 682 691 665 719 619 694 665 601 676 656 710 688 699 726 706 718 699 686 635 619 643 654 683 700 629 628 653 597 605 654 663 568 624 598 631 576 544 616 534 592 582 566 590 596 572 551 568 547 536 564 522 527 524 507 566 549 510 514 508 537 591 530 515 503 489 510 511 531 511 522 495 512 519 490 468 464 483 421 432 483 497 498 449 480 459 479 441 485 470 441 508 451 470 479 471 430 476 432 443 476 437 435 463 467 445 447 473 479 482 502 441 461 490 488 485 498 406 483 487 447 461 461 497 461 519 498 426 448 433 434 466 437 443 433 459 462 429 433 415 373 416 419 432 456 393 394 422 434 395 433 426 411 448 466 403 391 402 376 419 363 379 350 418 369 389 367 423 421 414 405 372 374 405 390 370 361 369 401 389 378 388 366 370 411 393 406 397 367 382 408 394 399 415 432 390 353 399 434 396 406 393 389 396 384 382 390 365 378 345 362 369 385 369 357 345 327 325 337 339 341 345 369 323 347 400 363 352 389 395 423 358 379 365 363 379 353 371 302 310 343 319 331 363 305 335 298 347 278 284 323 307 302 334 315 294 307 312 314 281 270 280 319 338 307 315 289 310 299 315 305 334 300 320 338 281 332 297 317 292 300 282 274 268 303 255 294 277 311 273 285 259 238 263 275 285 265 281 280 238 229 275 259 253 222 250 239 241 225 209 230 238 229 234 224 191 228 235 257 215 200 213 223 245 231 215 212 234 237 223 223 201 236 261 222 252 241 270 252 288 362 268 272 262 297 310 299 262 245 251 241 272 228 225 241 251 244 237 274 266 226 237 240 246 221 251 225 214 209 185 182 232 221 167 190 209 217 196 177 220 215 198 205 226 276 292 375 502 536 585 652 634 668 712 697 650 634 760 571 490 484 524 548 483 558 529 557 494 552 526 599 545 563 632 703 615 864 604 549 573 640 653 613 524 546 525 506 489 473 515 489 503 556 492 448 417 398 406 424 340 253 165 271 840 175 212 156 142 509 158 156 164 164 186 186 202 177 155 161 161 153 186 169 163 204 218 235 242 234 259 250 300 296 285 297 278 345 347 387 364 349 399 362 414 422 430 452 428 532 544 641 664 598 696 721 758 819 858 882 797 784 770 771 809 834 794 851 911 869 688 560 473 357 325 279 230 201 175 142 141 138 117 148 112 126 108 124 112 157 150 177 128 154 159 122 148 136 168 179 150 121 137 155 172 141 146 157 161 154 136 156 168 158 171 150 168 144 152 145 129 147 130 141 141 153 152 126 158 154 139 152 146 126 142 152 109 114 102 105 136 119 107 151 130 133 138 138 125 144 140 124 140 112 122 117 109 141 137 141 122 133 148 120 114 139 120 111 132 126 112 109 113 120 124 113 105 86 104 101 114 99 110 126 137 95 113 93 114 103 99 117 119 129 137 116 117 127 150 133 125 116 128 123 115 120 125 124 90 121 99 100 120 118 128 129 131 101 127 118 120 128 131 130 134 123 121 160 88 117 97 109 127 266 219 119 123 125 148 189 163 175 173 185 202 169 185 191 208 209 176 222 196 218 184 185 133 133 102 113 119 162 168 171 154 153 141 146 119 171 172 164 167 178 198 189 207 194 174 147 181 172 181 176 170 152 171 194 175 179 147 191 147 165 155 194 155 160 171 200 149 157 139 199 228 192 187 174 185 208 190 143 149 131 126 148 105 110 99 113 104 101 110 115 113 113 110 130 122 97 111 149 118 119 93 139 140 131 122 125 125 120 128 124 133 131 133 139 115 146 135 129 157 121 127 147 147 166 137 136 143 163 148 145 150 159 156 151 152 163 139 158 147 158 155 180 166 183 225 222 174 241 245 257 265 287 241 232 227 187 178 182 166 157 139 130 133 132 111 122 125 139 117 99 120 128 150 123 126 142 148 134 158 152 130 126 105 111 101 124 92 109 99 91 91 85 98 110 87 60 60 69 77 71 102 64 85 88 88 66 97 122 104 106 128 93 103 109 102 82 88 101 109 85 88 92 85 88 86 84 81 99 98 82 84 98 93 84 67 79 74 82 73 75 80 85 85 67 64 75 84 62 92 73 75 95 102 106 77 104 105 75 80 67 92 87 96 98 82 82 100 82 73 76 71 72 60 65 95 88 94 73 58 57 73 80 87 99 80 87 103 98 103 78 89 77 87 93 84 86 77 83 64 70 87 85 77 77 77 81 82 66 71 79 82 69 66 68 61 58 51 82 55 42 41 44 41 47 49 42 54 46 49 66 34 45 54 44 50 65 45 45 46 66 44 45 36 38 46 54 43 41 38 38 34 49 38 41 49 51 43 50 41 45 46 40 31 38 59 59 55 68 63 58 71 61 49 41 69 55 60 64 74 57 60 81 68 54 67 69 44 59 53 48 54 54 40 48 52 50 51 52 41 63 47 44 49 55 52 39 46 55 53 57 37 30 35 47 30 35 34 36 48 42 46 37 41 40 50 45 41 42 57 59 42 42 52 44 44 42 42 46 46 50 53 56 59 47 61 67 54 67 65 42 60 57 58 61 68 65 70 56 77 62 64 64 72 57 61 69 77 72 98 74 84 78 92 80 67 103 79 74 70 65 61 54 69 54 50 64 62 52 53 45 48 47 56 66 62 57 57 52 65 50 50 46 42 64 56 58 52 60 45 52 54 45 45 50 51 57 59 73 59 52 58 58 64 59 40 51 38 61 55 54 64 60 56 53 52 81 97 77 83 77 75 75 81 78 74 68 69 49 58 64 49 49 84 51 47 63 37 35 36 54 36 29 45 45 47 49 61 50 30 58 54 56 45 58 52 58 47 55 62 43 52 45 52 51 54 55 
];
B = [
0 0 0
 755935 509103 246832
 887783 660762 227021
 778936 580624 198312
 1281530 1062798 218732
 520484 393714 126770
 2141003 1917320 223683
 778305 672374 105931
 298342 232652 65690
 680852 607829 73023
 227037 182112 44925
 121477 91835 29642
 95412 73205 22207
 127371 105607 21764
 906460 848149 58311
 872627 816958 55669
 470591 426221 44370
 2569294 2442984 126310
 625594 575825 49769
 1103698 1041257 62441
 417924 383566 34358
 1171572 1111638 59934
 1139144 1083297 55847
 415451 384951 30500
 1125874 1072532 53342
 422346 393821 28525
 1943701 1862500 81201
 1182250 1129384 52866
 402481 377826 24655
 1187682 1136810 50872
 398965 375738 23227
 1188622 1140111 48511
 1142590 1096720 45870
 418137 396472 21665
 1451746 1395518 56228
 450258 428262 21996
 1150331 1106201 44130
 422357 395588 26769
 1134598 1093011 41587
 1130656 1089001 41655
 465679 440838 24841
 1091483 1052372 39111
 446306 423961 22345
 1178882 1139092 39790
 1057913 1022206 35707
 415348 395132 20216
 1078105 1042876 35229
 446919 426744 20175
 1055000 1021599 33401
 441345 422625 18720
 984835 953974 30861
 1079814 1045095 34719
 367349 353250 14099
 1009547 977448 32099
 362414 349753 12661
 1010472 978299 32173
 901910 873268 28642
 455860 442206 13654
 962235 933122 29113
 361126 350871 10255
 84999725 83891535 1108190
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
177 165 3 3
113 26 1 0
133 87 0 0
140 62 2 0
81 60 3 1
94 82 6 3
2348 139 35 8
14585 123 112 37
68455 148 556 105
285147 218 899 250
896870 244 1066 381
2586288 312 1399 626
6082402 433 1728 854
12214146 655 2036 1223
18816442 920 2346 1625
24261494 1157 2523 2046
24668236 1462 2844 2550
19927427 1991 3109 3116
11652894 2490 3768 3788
4295526 3078 4515 4652
833404 3814 5247 5403
69989 4690 6025 6288
10446 5746 6757 7075
9315 6880 7483 7656
9802 7984 8357 8121
10750 9330 8951 8699
11455 10806 9777 9626
12974 12246 10684 10747
13701 13118 11299 12074
14068 13436 12262 12781
18048 17014 12803 12989
16629 16225 13270 13361
16022 15340 13372 13846
14583 15303 13046 13289
15171 16494 13052 13292
15705 16822 12971 13482
14375 19643 12614 13929
14227 14016 12352 12282
14395 14660 12365 12336
13463 13676 12614 12477
14871 14157 12667 12611
14007 14111 13065 13300
16826 16392 15588 15905
14354 14637 14394 14310
18021 17660 14665 14665
17047 16957 14915 14860
15613 15505 15173 14908
14974 15132 15043 15005
14685 14716 15258 15291
14360 14333 14869 15047
14004 13986 14613 14798
12523 12500 13488 13626
11894 12185 12537 12533
10375 10262 11330 11301
9066 8923 9495 9507
8074 8247 8433 8629
7266 7165 8103 8627
6887 6873 7905 8109
5711 5745 6976 6845
5678 5502 6642 6705
5327 5370 5361 5339
5337 5284 5489 5353
4890 5037 5628 5726
5172 5319 5590 5440
5223 5270 5860 5932
5293 5155 5191 5346
5222 5131 5468 5568
12291 12206 8948 9823
6339 6323 6745 6769
6786 7012 7173 7125
8659 8451 8976 8906
8334 8627 10610 10351
9079 9119 9001 8878
9152 9130 9646 9448
9227 9232 8883 8935
9472 9445 8748 8559
7749 7646 7556 7504
6425 6318 6176 6269
5587 5532 5680 5590
4500 4347 4417 4334
2900 2852 2861 2862
1783 1791 1989 1920
84 83 112 93
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
