A = [
434618 439324 2057439 129843 128784 119685 117210 120159 124408 130852 167354 199137 220572 268952 309871 318830 316708 314398 307760 302767 297019 290076 282426 283570 293864 382292 395197 418196 502030 451327 462625 457962 412505 425939 420704 421745 418073 405673 404520 400205 401058 397723 400878 406153 403447 405910 396248 391038 384640 375527 370015 369628 371431 370981 371020 371273 370885 366986 366856 364058 361354 361279 359498 357922 359670 358726 356203 358202 352082 349789 348312 344480 342620 341223 338906 335598 335659 334320 330148 327393 326191 320864 320852 317902 311316 311988 311769 306646 307265 303900 297997 296552 291159 288404 287942 286071 281369 281260 276561 273769 272284 267371 263742 262118 258931 254442 253027 251638 248584 246101 243655 239233 236190 232182 230024 228052 225994 222570 222022 219333 217297 215872 211596 209089 204977 201955 200000 198264 195874 194837 191058 189620 186361 184785 180611 177949 176294 174422 171956 170592 168283 165689 164329 162877 158966 157952 154919 152947 152121 150030 148009 147650 144363 142609 140166 138902 136425 134955 133926 131792 131276 128321 127432 125943 123604 120983 120179 117377 116001 116094 114099 112980 111817 110428 108131 107236 104868 103167 101872 99979 98518 98311 97347 95584 94323 93939 91553 90272 88307 87167 86249 85005 83458 83831 81245 80092 79770 77762 76984 75769 75504 73993 73227 71884 70060 69869 68345 67544 66628 65802 64717 64279 63282 61822 61965 60239 59481 58330 57414 56512 55623 55288 54711 53905 53290 51798 51350 50240 49635 49141 47848 47535 47121 46551 46110 45102 44830 43618 43581 42519 41421 41129 40667 40445 39028 39015 38649 38557 37206 36120 36257 35334 35174 34779 34223 33854 33423 32734 32247 32801 31550 30765 30422 30266 29313 28726 28520 28665 28567 27400 26532 26029 26310 25871 25173 25035 24302 24103 24087 23375 23170 23064 22625 22248 21725 21391 21129 20876 20248 19990 19543 19114 19039 18751 18492 18355 18028 17507 17490 17112 17164 16625 16131 15900 15865 15705 15565 15212 14621 14981 14572 13964 13831 13886 13622 13633 13051 12887 12975 12812 12378 12798 11982 11777 11450 11478 11463 11190 11004 10803 10687 10574 10377 10242 10159 9891 9772 9464 9622 9426 9201 9156 9026 8999 8624 8662 8367 8178 8189 8072 8061 7719 7652 7552 7536 7414 7155 7104 7080 6879 6658 6817 6910 6567 6457 6363 6310 6270 6121 5948 5922 5913 5780 5718 5709 5586 5575 5523 5358 5393 5268 5179 5104 5050 4950 5017 4828 4907 4964 5032 4724 4619 4523 4532 4383 4335 4483 4401 4368 4445 4168 4316 4125 4117 4270 3955 3861 3661 3720 4010 3713 3706 3709 3528 3795 3646 3523 3474 3392 3481 3563 3302 3363 3218 3099 3113 3117 3072 3087 3192 3070 3051 3028 2978 3071 3200 2959 3011 2951 3001 2929 2868 2766 2824 2818 2663 2700 2738 2647 2693 2724 2660 2495 2590 2583 2478 2511 2471 2477 2488 2444 2427 2420 2378 2472 2439 2503 2295 2336 2392 2304 2332 2303 2150 2172 2221 2514 2273 2234 2129 2173 2105 2186 2258 2201 2183 2154 1985 2155 2518 1935 1945 1910 2003 1999 1996 2067 2024 1922 1952 1961 1887 1976 1937 1888 1790 1846 1946 1830 1870 1743 1843 1777 1674 1687 1816 1726 1784 1734 1824 1701 1871 1673 1715 1780 1704 1747 1630 1711 1615 1582 1631 1675 1627 1562 1548 1607 1531 1598 1591 1529 1547 1510 1473 1603 1482 1609 1576 1614 1528 1502 1493 1570 1486 1517 1487 1529 1581 1513 1509 1518 1568 1453 1501 1487 1456 1461 1419 1492 1431 1339 1358 1383 1406 1412 1444 1516 1400 1389 1428 1446 1426 1393 1403 1514 1436 1401 1362 1376 1396 1330 1435 1392 1370 1384 1449 1364 1382 1342 1489 1280 1377 1325 1319 1332 1275 1238 1378 1309 1264 1276 1260 1323 1271 1258 1203 1189 1282 1270 1261 1192 1254 1242 1239 1239 1183 1210 1198 1154 1229 1150 1177 1117 1176 1180 1086 1086 993 1058 1102 1005 987 1063 1066 1038 1131 1201 1006 1059 1049 982 1046 1028 1043 936 997 1013 1041 986 978 1009 1028 1431 1094 1080 1334 1043 996 1131 1028 1023 1033 1015 1073 1002 1040 1015 953 1011 935 1002 971 1011 947 929 944 905 992 982 912 922 999 858 873 858 935 956 891 912 907 850 926 892 901 865 874 917 863 853 920 863 781 863 864 886 964 874 861 879 880 877 887 894 849 915 942 1020 901 904 914 862 919 875 1039 902 901 1118 931 953 890 918 909 912 898 944 958 912 907 969 906 891 968 913 852 928 844 875 845 884 819 893 824 821 885 848 847 899 872 777 844 863 842 840 824 827 824 849 912 762 719 763 750 755 798 752 757 740 871 708 750 747 823 653 690 683 781 723 703 739 745 790 706 784 741 781 744 754 699 753 751 1072 827 704 665 710 681 778 636 621 647 613 667 733 656 697 579 601 586 650 604 625 628 676 610 630 674 689 647 709 640 613 625 664 648 627 557 621 623 637 613 644 638 783 578 661 626 584 699 641 602 579 623 643 664 609 555 631 690 593 658 1073 560 569 568 610 605 571 537 570 565 641 516 494 606 555 601 567 569 562 535 574 595 611 531 547 530 693 523 558 568 480 558 502 580 493 506 565 567 517 525 486 472 550 578 535 515 526 572 622 609 554 584 665 585 624 554 554 566 764 536 627 560 559 531 528 527 566 527 526 475 491 542 488 512 493 507 498 537 523 490 529 482 507 513 486 483 492 465 501 477 515 470 504 513 485 486 538 536 522 548 488 520 509 465 523 499 504 486 538 590 558 490 504 516 538 516 522 557 569 1057 528 546 502 499 462 443 515 451 450 467 498 461 481 493 504 477 428 726 536 428 437 465 460 430 395 434 442 400 452 470 375 444 539 450 441 402 417 428 389 404 376 380 380 352 350 348 293 343 333 283 326 325 347 326 351 340 348 334 312 337 305 304 312 314 302 291 310 463 330 301 330 297 326 297 286 313 271 281 302 337 316 294 263 323 300 338 323 359 310 319 332 329 316 338 347 438 534 329 340 395 411 406 371 491 349 410 430 382 373 377 382 363 406 350 358 331 317 368 353 347 353 318 404 359 373 373 372 355 371 327 347 339 343 381 339 325 327 289 334 304 329 283 315 333 286 314 319 277 311 277 246 273 233 202 232 206 210 247 203 210 240 214 185 186 202 165 214 208 212 191 183 220 196 184 174 218 195 208 199 219 219 209 280 228 221 226 198 203 223 202 207 242 220 177 191 190 222 245 200 216 183 175 168 197 147 183 149 157 160 141 158 160 137 178 160 168 178 163 146 151 168 167 152 151 149 190 150 153 155 184 194 178 193 177 152 168 163 148 153 156 146 155 167 181 160 128 140 172 220 146 150 127 134 130 161 120 143 136 153 128 162 209 156 168 166 156 208 178 153 151 152 152 159 137 148 143 136 150 168 146 147 136 150 135 146 115 122 159 151 168 160 144 141 132 138 171 166 186 157 146 156 161 171 168 155 150 156 157 150 159 135 161 190 160 157 173 151 159 148 147 164 160 198 137 139 162 180 171 167 195 141 144 131 142 151 170 131 111 145 135 127 171 143 149 122 185 178 96 144 117 139 116 113 119 149 98 137 149 114 115 120 117 118 104 111 114 134 143 92 111 128 127 116 104 121 131 168 167 178 177 149 122 143 145 136 139 155 145 126 140 143 151 103 81 107 120 127 99 92 120 105 116 124 119 133 130 136 141 106 114 120 124 171 100 97 97 86 88 82 72 89 126 72 61 78 83 79 72 118 55 96 48 75 103 94 75 87 103 104 88 100 108 94 120 158 101 112 93 115 109 146 109 84 118 111 100 81 78 92 91 92 92 88 89 62 66 73 79 82 93 113 88 88 90 111 65 87 96 67 107 100 84 66 81 91 76 94 74 84 73 104 71 93 91 92 89 76 79 79 61 80 80 72 71 71 91 74 75 94 77 75 78 77 86 60 58 55 64 71 76 67 74 47 51 57 56 58 47 62 40 56 57 54 51 58 52 47 52 44 70 46 50 46 46 57 52 51 53 50 46 52 45 46 43 36 63 54 57 67 65 53 55 56 71 57 56 62 56 60 57 62 65 47 59 62 50 50 52 61 59 58 56 49 54 58 47 57 50 51 66 41 62 52 47 63 65 55 61 57 48 63 49 54 58 63 52 51 40 64 45 40 36 43 35 50 38 42 48 55 41 40 35 27 44 32 56 46 39 29 45 63 47 52 53 50 59 46 50 73 97 48 50 41 42 81 58 43 32 46 42 36 46 48 27 39 32 58 39 34 39 66 44 40 39 30 38 40 42 35 46 34 29 43 31 33 41 35 43 41 36 53 48 53 42 53 50 49 55 65 49 55 56 62 57 65 59 56 63 71 58 67 86 79 74 80 80 67 73 64 83 92 82 85 60 63 89 77 58 85 87 91 71 75 90 91 83 91 80 74 73 74 71 59 64 62 64 70 57 56 66 60 39 47 55 62 57 63 53 57 38 57 43 66 67 51 39 48 57 66 45 44 45 31 34 37 40 39 37 41 37 37 32 39 32 26 30 35 28 32 40 44 41 58 39 31 26 31 62 39 36 42 33 36 36 44 35 38 41 34 47 40 42 37 45 35 26 41 43 51 38 43 61 55 50 58 60 53 45 47 51 41 45 42 51 42 47 51 43 38 52 41 55 41 38 32 43 33 44 36 38 37 27 36 25 31 35 31 21 33 26 28 32 20 38 33 31 24 22 34 29 20 27 24 18 24 18 25 24 19 20 20 31 30 19 20 23 23 14 19 28 20 18 20 23 30 21 20 22 13 20 20 17 14 24 20 27 14 31 24 23 22 21 26 28 15 19 32 39 33 25 21 19 30 34 22 33 29 22 28 22 31 36 32 35 32 35 37 29 34 30 26 21 23 23 23 21 11 33 18 25 14 26 24 16 14 16 20 21 20 17 11 5 11 9 13 8 14 11 13 10 15 27 10 41 9 19 23 23 18 18 26 17 21 16 17 19 16 10 15 18 15 17 13 17 16 22 13 27 16 22 20 24 26 22 15 21 17 22 26 19 20 19 16 18 24 33 23 22 18 29 
];
B = [
0 0 0
 88774 18542 70232
 104623 22849 81774
 110283 27096 83187
 93837 21250 72587
 107315 24930 82385
 131142 31433 99709
 143514 33612 109902
 166300 40504 125796
 218660 58381 160279
 146480 39130 107350
 374089 126259 247830
 104561 31335 73226
 80342 25051 55291
 54811 17378 37433
 40478 11820 28658
 30090 7635 22455
 32536 8903 23633
 22459 5629 16830
 32816 8348 24468
 31509 7538 23971
 54401 14160 40241
 54007 13198 40809
 63675 17539 46136
 52436 13096 39340
 74983 20463 54520
 66188 18206 47982
 133468 41390 92078
 45298 14185 31113
 120628 38022 82606
 50307 16405 33902
 49824 15101 34723
 43256 14882 28374
 50642 17856 32786
 38997 13087 25910
 43131 15063 28068
 41939 13743 28196
 34292 12021 22271
 51676 18080 33596
 44132 15946 28186
 37961 14281 23680
 56738 19771 36967
 35809 14223 21586
 87244 30526 56718
 49471 20014 29457
 32782 13697 19085
 45202 17247 27955
 49735 21602 28133
 52216 20475 31741
 58332 25509 32823
 39078 16330 22748
 41701 17438 24263
 63617 27821 35796
 39878 16824 23054
 82794 38407 44387
 58034 24272 33762
 83888 34532 49356
 46280 23130 23150
 62559 27023 35536
 126323 65547 60776
 24867827 15216876 9650951
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
6 43 1 0
1 10 3 0
4 12 1 1
6 16 4 0
10 10 4 3
11 24 13 5
21 24 22 7
96 40 63 14
573 45 270 66
7562 81 418 148
60912 83 546 244
240326 136 708 360
504267 181 965 590
766881 345 1255 893
893843 539 1626 1369
933379 780 2317 2131
816037 1268 2991 2941
570186 1873 3988 3874
272280 2684 5316 5248
64657 3805 6652 6669
12987 5196 8312 8574
11154 7383 10280 10365
13073 9664 12332 12364
15394 12630 14874 14745
18115 15896 17573 17372
21194 19453 20717 20682
24915 23541 24107 24319
29141 28503 28111 28252
33669 32328 32309 32653
38092 37439 37532 37459
43674 42336 42329 42436
48576 47765 47451 47438
53619 53376 52781 52877
58542 58767 58349 58700
64691 64788 63839 64310
69575 69710 68922 69044
74819 74626 74451 74903
79734 79678 79188 79214
84097 84264 83506 84049
89336 89704 88365 88347
92219 92438 91640 92494
95584 95498 96067 95984
98706 98304 98993 98716
101083 101961 101943 102378
104783 104984 104399 104172
108373 108915 107523 107531
110583 110109 109564 109574
111749 111894 111059 111193
110893 111188 110629 110880
109148 109423 108653 108959
105536 105064 105074 104562
101662 102074 102237 102468
98378 99070 99231 99071
94752 95300 94458 95355
91120 90713 91155 91202
86355 86138 86288 86254
80952 81065 80669 80813
72498 73446 72878 73192
63047 64154 63088 63689
53289 53803 53484 53939
45500 46595 46312 45744
29668 30432 30511 30299
14528 14757 14626 14487
3849 3647 3694 3595
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
