ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Ural Championship 2012

About     Problems     Submit solution     Judge status     Standings
Contest is over

D. Unidentified Ships

Time limit: 1.0 second
Memory limit: 64 MB
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.
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's 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't it?


The first line contains integers n and t that is the number of unidentified ships before and after the hyperjump (1 ≤ t < n ≤ 5000). The second line contains integers c1, …, cn that are the classes of the ships according to the Universal Military Classifier (1 ≤ ci ≤ 5000). The third line contains integers k and x: the number of the identified ship and its position in the chain (1 ≤ kn; 1 ≤ xt). 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.


Output the number of possible sets of the remaining ships modulo 109 + 7.


5 3
2 1 1 3 1
2 3
4 2
1 1 1 1
1 2


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}.
Problem Author: Alex Samsonov (prepared by Alexander Fetisov)
Problem Source: Ural Championship 2012
To submit the solution for this problem go to the Problem set: 1903. Unidentified Ships