{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThe First Galactic Fleet flagship Eltreum was patrolling near \r\nthe center of the Milky Way. Unidentified ships appeared in this sector \r\nsome time ago and the crew of Eltreum kept a close watch on them. \r\nAll ships have been counted and classified by the Universal\r\nMilitary Classifier, but their mission and identity remained unclear. \u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eSuddenly, after nearly a week of staying at one place the unidentified ships began to move.\r\nSome of them went straight into hyperspace, and one of the remaining ships activated a \r\njamming device that rendered Eltreum\u0027s radars useless. \r\nVisual observation showed that all the remaining ships rushed away from \r\nEltreum, lining up in a chain in non-descending order of their classes:\r\nthe lightest ships were ahead and the heaviest ships closed the \r\nprocession. Unfortunately, only one of the ships in this chain has been \r\nprecisely identified—the one with a jammer device. The classes of the other ships were not identified. \r\nBut, perhaps, information gained from the visual observation could help infer something about the remaining ships, couldn\u0027t it? \u003c/div\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThe first line contains integers \u003ci\u003en\u003c/i\u003e and \u003ci\u003et\u003c/i\u003e that is the number of\r\nunidentified ships before and after the hyperjump (1 ≤ \u003ci\u003et\u003c/i\u003e \u0026lt; \u003ci\u003en\u003c/i\u003e ≤ 5000).\r\nThe 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 \r\nof 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). \r\nThe 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;\r\n\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.\u003c/div\u003e\u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eOutput the number of possible sets of the remaining\r\nships modulo 10\u003csup\u003e9\u003c/sup\u003e + 7.\u003c/div\u003e\u003c/div\u003e"}},{"title":"Sample","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\u003cbr\u003e\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":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eIn 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}.\r\n\u003c/div\u003e\u003c/div\u003e"}}]}