A = [
5765 1497 3094 1374 1449 1445 1444 1412 1437 1277 1349 1309 1332 1322 1396 1485 1410 1553 1500 1529 1549 1618 1490 1483 1566 1958 1809 1934 2327 2473 2539 2507 2499 2596 2567 2578 2635 2460 2468 2408 2540 2440 2469 2318 2509 2396 2393 2454 2375 2421 2423 2493 2271 2437 2344 2191 2287 2256 2164 2263 2194 2229 2323 2114 1993 2149 2218 1950 2054 2039 2083 2009 2063 2013 2020 2013 2083 2032 2037 1890 2071 1914 1938 2014 2047 1961 1992 2075 2004 1862 1807 1790 1819 1787 1802 1799 1709 1800 1752 1706 1652 1608 1571 1743 1662 1536 1597 1670 1617 1457 1488 1522 1519 1643 1527 1539 1642 1560 1524 1496 1620 1642 1576 1803 1493 1455 1476 1434 1512 1537 1511 1468 1397 1529 1439 1451 1360 1386 1445 1509 1425 1504 1408 1411 1470 1395 1394 1447 1390 1458 1509 1415 1390 1392 1387 1459 1399 1399 1315 1398 1426 1449 1350 1428 1397 1397 1258 1293 1438 1271 1291 1383 1219 1274 1244 1210 1271 1295 1227 1311 1245 1298 1241 1187 1215 1217 1184 1119 1159 1144 1065 1237 1237 1380 1311 1267 1173 1153 1269 1185 1237 1183 1333 1120 1247 1178 1126 1088 1239 1189 1204 1207 1146 1171 1207 1137 1154 1204 1135 1133 1162 1085 1108 1107 1087 1144 1221 1166 1156 1108 1017 1249 1034 1091 1122 1118 1070 1005 978 1052 1027 1074 1088 1059 986 1023 1012 1001 1043 915 910 975 966 961 989 941 937 1000 1004 995 1051 1004 982 960 986 1040 989 999 913 1025 971 1047 1086 974 1031 1074 1029 969 1016 962 980 978 1071 947 1031 1008 918 908 936 992 923 936 1030 931 955 1012 937 926 990 916 986 926 990 878 876 959 906 938 882 860 856 893 897 887 988 852 821 865 827 824 770 851 848 809 895 809 802 811 813 792 759 795 816 795 766 809 764 896 782 719 803 738 763 702 805 782 813 720 689 730 826 697 730 824 785 740 714 682 717 743 728 733 738 743 742 747 725 668 750 805 791 806 716 686 693 723 674 695 711 826 836 738 813 709 837 727 700 811 695 723 822 667 781 752 750 810 762 754 753 836 750 704 787 693 687 790 749 756 791 736 730 733 710 750 790 727 712 685 773 727 750 688 745 681 765 781 719 789 695 727 678 718 710 766 737 687 756 709 749 670 763 705 707 732 800 707 677 714 725 690 702 690 725 735 741 690 664 734 703 754 655 728 680 657 646 733 670 654 719 725 679 674 697 752 691 754 787 805 664 706 674 694 742 720 694 643 747 767 745 812 642 711 796 703 718 713 767 722 763 753 722 693 756 727 743 659 742 574 685 688 720 728 680 735 712 756 690 691 676 695 615 667 656 658 752 711 695 686 757 765 713 703 650 712 657 712 696 639 642 644 765 693 671 627 721 648 635 657 671 628 595 635 702 623 700 680 697 684 676 682 715 614 574 716 619 648 612 689 663 623 645 618 626 676 643 603 687 663 654 644 653 646 730 642 605 673 638 658 698 573 666 656 649 620 639 658 704 614 618 684 667 703 701 611 645 670 619 697 640 625 647 640 693 707 702 611 633 679 741 649 671 636 647 706 632 662 616 653 695 623 626 698 604 702 641 598 728 688 713 693 671 662 709 719 700 749 681 683 670 683 672 704 641 639 747 651 667 710 674 679 671 669 655 646 652 635 672 644 686 606 642 680 626 612 684 678 706 751 687 688 651 660 632 679 669 810 713 692 718 606 641 659 643 664 665 651 726 704 626 730 688 741 691 857 805 720 733 718 751 652 672 641 643 638 685 644 647 693 655 683 590 644 676 611 618 579 633 591 568 680 619 652 643 609 606 647 617 703 625 655 666 654 622 618 635 653 659 648 627 612 611 664 595 639 631 725 715 591 636 640 690 643 648 636 609 621 643 575 702 618 598 609 660 580 713 606 651 664 631 608 703 659 698 637 644 703 747 675 616 646 691 657 584 616 659 679 728 728 637 681 679 681 594 617 646 722 640 684 720 646 631 665 641 648 613 684 644 681 688 658 661 693 728 698 683 769 649 726 712 700 658 657 741 703 634 695 661 724 772 656 652 673 695 694 693 692 703 747 740 666 892 786 710 781 718 665 714 733 667 718 779 687 712 685 701 696 665 608 627 700 649 643 573 683 710 639 669 660 681 703 641 648 656 655 683 686 593 652 636 658 635 747 788 656 777 719 644 706 725 679 686 668 791 728 700 683 638 670 621 653 655 738 682 649 692 639 646 696 640 681 682 773 665 741 687 644 750 628 660 717 692 810 704 714 771 766 783 722 723 724 719 711 776 697 765 701 668 732 733 736 794 740 720 728 726 719 723 726 682 705 699 672 665 785 738 770 777 762 751 654 715 905 763 765 785 718 748 765 695 774 735 728 758 719 714 756 653 725 703 710 756 722 703 716 682 733 688 760 762 728 767 746 748 760 806 690 694 724 861 657 736 886 712 747 768 736 666 797 773 695 711 665 764 737 831 742 733 749 752 773 746 822 759 783 772 729 783 752 684 658 662 664 658 689 736 659 615 665 692 629 684 709 671 703 728 711 783 614 632 681 679 791 784 713 711 1158 670 662 639 654 680 661 651 696 580 598 706 664 732 680 738 741 663 609 635 759 676 644 658 647 582 657 678 617 635 670 607 625 674 678 673 647 656 662 666 693 672 689 722 721 670 665 706 686 699 707 744 669 736 744 729 1008 703 717 681 663 688 686 653 760 697 733 756 681 783 701 721 722 662 692 673 789 704 726 768 760 726 642 708 773 791 690 812 753 711 911 670 651 664 599 650 685 660 689 711 669 644 681 630 719 668 712 672 672 647 916 597 671 679 656 612 662 704 677 623 652 579 658 668 692 656 670 603 671 621 623 765 650 594 736 655 646 626 644 638 705 706 658 622 665 693 730 720 617 713 648 648 759 669 646 624 591 661 679 677 745 643 707 696 661 640 645 661 699 630 715 630 611 735 764 689 669 655 741 707 648 651 630 635 625 643 617 683 714 650 631 649 650 686 620 615 621 695 639 710 676 654 642 670 650 668 587 642 679 617 675 586 631 600 637 670 625 654 620 613 632 641 646 717 660 622 682 649 606 651 571 656 600 619 634 639 637 625 594 762 663 640 635 636 642 621 614 606 605 642 602 648 613 628 616 633 569 581 649 546 677 623 526 653 609 639 567 598 596 645 671 635 628 658 617 657 653 629 580 641 648 612 637 669 632 613 658 799 600 627 627 705 614 693 684 664 702 644 677 667 732 682 699 735 721 667 657 617 677 691 676 734 703 676 699 712 668 695 665 676 685 680 752 741 646 715 739 751 690 739 693 708 709 817 689 667 684 629 602 693 611 621 622 669 606 654 625 638 664 602 695 614 607 678 676 623 624 752 659 715 677 600 676 645 633 622 712 667 607 591 595 695 627 612 706 610 647 778 664 629 654 632 599 657 677 583 641 670 671 645 633 730 697 690 631 695 661 668 672 667 687 650 711 709 659 674 694 678 703 702 681 691 660 641 660 702 606 739 697 630 632 625 669 729 705 756 684 695 613 703 779 684 706 777 753 706 693 644 708 678 720 700 689 712 673 708 722 694 708 695 688 632 713 695 709 749 725 683 706 746 775 761 680 706 753 693 760 722 736 769 765 710 722 764 743 717 668 711 679 677 682 758 654 731 671 706 744 732 701 668 653 683 652 662 715 720 822 684 568 716 623 643 595 699 705 624 649 681 636 698 745 760 764 726 712 717 665 763 732 667 745 728 750 713 626 705 676 641 648 690 670 630 699 690 665 686 629 656 686 680 698 668 691 669 711 667 712 703 645 688 590 685 812 659 666 642 735 674 620 607 633 668 607 685 658 678 672 603 722 672 687 649 633 634 643 667 623 738 662 640 690 665 622 673 764 641 669 688 635 597 654 653 658 587 665 631 643 676 619 647 660 601 701 712 648 652 747 625 632 640 651 690 622 686 717 651 618 633 655 648 642 599 626 638 664 705 720 624 674 625 606 652 683 600 651 707 590 634 626 666 602 679 647 659 630 630 688 660 714 674 663 758 718 730 864 716 703 756 759 798 753 811 800 626 728 806 764 723 785 901 772 703 791 786 745 747 753 728 732 958 741 697 760 743 816 763 719 731 719 788 736 736 747 756 829 695 768 761 683 757 788 730 776 663 743 663 666 677 704 726 730 717 715 714 754 707 806 731 710 697 675 729 882 702 745 678 704 709 706 650 693 675 715 720 659 662 634 644 648 689 644 646 689 664 625 671 645 678 705 795 704 689 803 735 717 656 674 701 742 692 779 746 777 790 711 749 759 784 745 798 753 738 763 733 686 665 603 654 683 748 739 711 792 805 731 690 689 643 744 717 694 729 877 701 724 669 754 848 760 828 794 883 866 704 667 756 753 705 736 669 660 659 623 663 657 652 656 725 612 701 741 717 663 568 673 623 610 662 633 652 671 649 626 667 667 630 750 670 640 631 638 634 661 649 684 740 709 658 686 698 677 688 700 712 651 652 821 747 722 660 626 671 683 676 621 684 614 620 645 582 691 588 576 640 609 669 644 623 684 626 671 703 628 607 616 702 663 759 657 682 671 645 635 718 654 655 668 646 710 740 681 653 677 643 681 644 686 744 704 675 638 668 643 650 645 677 705 641 679 728 695 673 736 678 749 766 780 648 658 679 694 695 681 627 685 
];
B = [
0 0 0
 3587864 925497 2662367
 2761371 711563 2049808
 5739586 1710425 4029161
 2487663 627003 1860660
 2732256 706231 2026025
 3394659 893081 2501578
 3925900 1094116 2831784
 3613935 959093 2654842
 7304955 2174513 5130442
 3693882 1073784 2620098
 6566527 2016526 4550001
 3384315 1096096 2288219
 3992947 1251991 2740956
 2258168 720423 1537745
 4887850 1681307 3206543
 2045962 622725 1423237
 2286346 755105 1531241
 2125236 704198 1421038
 4079538 1340704 2738834
 2399710 766116 1633594
 6091589 2146446 3945143
 4129666 1302371 2827295
 3984662 1295738 2688924
 6754920 2093329 4661591
 9319175 3026593 6292582
 2729765 931929 1797836
 25342646 8644847 16697799
 1585212 634313 950899
 4016053 1500547 2515506
 2100511 841167 1259344
 2656695 1084127 1572568
 1715306 685856 1029450
 6113424 2497051 3616373
 1535494 637257 898237
 2367640 964117 1403523
 1900504 785304 1115200
 2210916 923002 1287914
 1632261 667806 964455
 7065302 2943366 4121936
 1076897 448735 628162
 1911089 813311 1097778
 1212414 512705 699709
 3512024 1431939 2080085
 1713454 746178 967276
 964773 418725 546048
 1776465 792796 983669
 1806068 773102 1032966
 11259480 4820126 6439354
 2154176 976284 1177892
 1122590 499710 622880
 1735800 829441 906359
 1954432 849986 1104446
 1805884 785632 1020252
 13053942 5806118 7247824
 1936078 835463 1100615
 4629932 2396282 2233650
 1506810 709887 796923
 6178145 2631688 3546457
 5937385 2649742 3287643
 803398452 422821511 380576941
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
75242 85040 1602 1483
40836 4828 154 169
53139 6461 251 255
40130 7629 372 335
18614 6954 417 350
15848 8499 838 759
215530 10784 1749 1716
1120427 11664 2434 2356
3933282 13598 3693 3674
10702312 17486 5586 5452
17413745 21595 7199 7101
26173371 32835 9879 9783
34822100 53831 13159 12798
43150446 99676 17787 17649
44769262 174519 23628 23005
42141749 294617 31365 31655
34060780 438780 41397 41174
24005290 568552 52898 53007
14156253 666171 67020 66040
5967351 710746 82298 80834
1576644 713142 95639 96251
362215 680672 109501 109951
215297 605738 122665 121663
199200 492186 133249 132833
192611 375937 143363 142274
193377 295059 153549 153200
196537 246969 163419 164609
199064 225456 174318 173759
209020 219604 185805 186641
214625 222154 200499 200538
228067 230465 215135 216383
246204 244536 232057 232442
274909 269075 249537 250231
299904 290454 272688 273232
323484 316963 301551 302262
348784 345606 334340 332051
388371 381793 369844 370834
429224 425696 413681 414823
471961 468033 463679 463116
520808 519939 514568 514541
584571 584194 578241 578174
653536 654229 654213 651513
732949 732969 732845 730657
821802 821802 821879 822534
926855 926718 927410 925579
1045331 1047902 1045988 1049439
1171022 1175682 1173983 1174101
1296965 1298796 1300763 1298835
1437838 1438442 1438730 1436662
1580364 1579666 1577819 1577101
1710257 1707648 1708955 1705538
1821460 1823436 1820526 1820447
1925444 1926241 1920798 1919446
2019356 2017305 2018944 2014990
2115288 2111664 2113026 2114977
2179117 2178350 2176756 2178335
2277785 2272006 2268559 2266704
2345226 2345318 2344533 2339199
2401460 2397752 2403848 2394674
2446791 2449959 2452300 2445495
2490110 2494987 2485329 2486747
2431103 2422626 2422322 2422184
2251433 2253104 2253604 2250933
1900227 1901887 1908062 1906845
1382473 1386350 1391520 1380003
796403 794695 799649 788932
394754 400802 397127 395399
282087 276488 276280 275335
262725 256014 251262 258439
238139 236676 241634 231434
179665 174766 164731 187198
123365 108669 103832 127946
9584 9253 8707 9376
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
