{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"problem_par\"\u003e\n \u003cdiv class\u003d\"problem_par_normal\"\u003e\n The First Galactic Fleet flagship Eltreum was patrolling near the center of the Milky Way. Unidentified ships appeared in this sector some time ago and the crew of Eltreum kept a close watch on them. All ships have been counted and classified by the Universal Military Classifier, but their mission and identity remained unclear.\n \u003c/div\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"problem_par\"\u003e\n \u003cdiv class\u003d\"problem_par_normal\"\u003e\n Suddenly, after nearly a week of staying at one place the unidentified ships began to move. Some of them went straight into hyperspace, and one of the remaining ships activated a jamming device that rendered Eltreum\u0027s radars useless. Visual observation showed that all the remaining ships rushed away from Eltreum, lining up in a chain in non-descending order of their classes: the lightest ships were ahead and the heaviest ships closed the procession. Unfortunately, only one of the ships in this chain has been precisely identified—the one with a jammer device. The classes of the other ships were not identified. But, perhaps, information gained from the visual observation could help infer something about the remaining ships, couldn\u0027t it?\n \u003c/div\u003e\n \u003c/div\u003e\n "}},{"title":"Input","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"problem_par\"\u003e\n \u003cdiv class\u003d\"problem_par_normal\"\u003e\n The first line contains integers \u003ci\u003en\u003c/i\u003e and \u003ci\u003et\u003c/i\u003e that is the number of unidentified ships before and after the hyperjump (1 ≤ \u003ci\u003et\u003c/i\u003e \u0026lt; \u003ci\u003en\u003c/i\u003e ≤ 5000). The second line contains integers \u003ci\u003ec\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e, …, \u003ci\u003ec\u003c/i\u003e\u003csub\u003e\u003ci\u003en\u003c/i\u003e\u003c/sub\u003e that are the classes of the ships according to the Universal Military Classifier (1 ≤ \u003ci\u003ec\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 5000). The third line contains integers \u003ci\u003ek\u003c/i\u003e and \u003ci\u003ex\u003c/i\u003e: the number of the identified ship and its position in the chain (1 ≤ \u003ci\u003ek\u003c/i\u003e ≤ \u003ci\u003en\u003c/i\u003e; \u003cnobr\u003e1 ≤ \u003ci\u003ex\u003c/i\u003e ≤ \u003ci\u003et\u003c/i\u003e\u003c/nobr\u003e). The number of the identified ship is its position in the list in the second line. Chain positions are numbered from the head of the procession, that is, the list begins with the smallest class number.\n \u003c/div\u003e\n \u003c/div\u003e\n "}},{"title":"Output","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"problem_par\"\u003e\n \u003cdiv class\u003d\"problem_par_normal\"\u003e\n Output the number of possible sets of the remaining ships modulo 10\u003csup\u003e9\u003c/sup\u003e + 7.\n \u003c/div\u003e\n \u003c/div\u003e\n "}},{"title":"Sample 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5 3\r\n2 1 1 3 1\r\n2 3\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Sample 2","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4 2\r\n1 1 1 1\r\n1 2\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Notes","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"problem_par\"\u003e\n \u003cdiv class\u003d\"problem_par_normal\"\u003e\n In the first example only the set {2, 3, 5} of ships could remain after the hyper-leap. In the second example the following sets could remain: {1, 2}, {1, 3}, {1, 4}.\n \u003c/div\u003e\n \u003c/div\u003e\n "}}]}