ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Чемпионат Урала 2012

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

D. Неопознанные корабли

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Флагманский корабль Первого галактического флота Эльтреум нёс боевое дежурство возле центра Млечного Пути. В этом секторе некоторое время назад объявились неопознанные корабли, и экипаж Эльтреума вёл пристальное наблюдение за ними. Вскоре все корабли были пересчитаны и классифицированы по универсальному военному классификатору, однако их цель и принадлежность так и не были установлены.
Неожиданно после уже почти недельной стоянки на одном месте неопознанные корабли начали движение. Часть их ушла в гиперпространство, а на одном из оставшихся было включено какое-то устройство, которое забило все радары Эльтреума помехами. Визуальное наблюдение показало, что все оставшиеся корабли устремились прочь от Эльтреума, выстроившись в цепочку в порядке неубывания их классов — впереди следовали самые лёгкие корабли, замыкали процессию самые тяжёлые. К сожалению, в этой цепочке удалось точно идентифицировать лишь один из кораблей — тот, на котором работало устройство, создающее помехи. У остальных кораблей не удалось точно определить даже их класс. Но, может быть, по полученной при визуальном наблюдении информации можно что-то сказать об оставшихся кораблях?

Исходные данные

В первой строке записаны целые числа n и t — количество неопознанных кораблей до гиперпрыжка и после него (1 ≤ t < n ≤ 5000). Во второй строке через пробел следуют целые числа c1, …, cn — классы всех кораблей по универсальному военному классификатору (1 ≤ ci ≤ 5000). В третьей строке записаны целые числа k и x — номер корабля, который удалось опознать, и его позиция в строю (1 ≤ kn; 1 ≤ xt). Номер корабля — это его номер в списке, приведённом во второй строке. Позиция в строю считается с головы процессии, то есть меньшим номерам классов соответствуют меньшие позиции.

Результат

Выведите единственное целое число — количество возможных наборов оставшихся кораблей по модулю 109 + 7.

Примеры

исходные данныерезультат
5 3
2 1 1 3 1
2 3
1
4 2
1 1 1 1
1 2
3

Замечания

В первом примере после гиперпрыжка мог остаться только набор кораблей {2, 3, 5}. Во втором примере могли остаться следующие наборы: {1, 2}, {1, 3}, {1, 4}.
Автор задачи: Алексей Самсонов (подготовка — Александр Фетисов)
Источник задачи: XVI Открытый чемпионат Урала по спортивному программированию (апрель, 2012)
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1903. Неопознанные корабли