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

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

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

K. Вечер ностальгии

Ограничение времени: 2.0 секунды
Ограничение памяти: 256 МБ
Саша и Слава живут в солнечной Калифорнии, работают в успешных крупных компаниях и довольны жизнью. Но периодически они тоскуют по родине.
Именно поэтому они до сих пор организуют АСМ-соревнования в России и даже принимают в них участие. Ещё они любят посидеть возле камина на крыше небоскрёба, обсудить последние новости из России и немного поностальгировать. Как-то само собой вошло в традицию завершать «вечер ностальгии» настольной игрой Tunnel Towards Rutracker (TTR).
Для игры используется колода карт k+1 различных цветов (цвета нумеруются от 0 до k). Цвет 0 является особым, что будет подробно описано в правилах ниже.
Игра происходит следующим образом. Вначале Саша берет себе в руку несколько карт и показывает их Славе. Затем Слава тасует оставшиеся карты и выдаёт Саше «вслепую» t верхних карт (эти карты может смотреть только Саша). Далее Слава придумывает и говорит вслух два числа x и y — параметры туннеля, который предстоит построить Саше.
Саша, глядя на свои карты, выбирает и называет цвет color (1 ≤ colork), используемый для постройки туннеля. После этого Слава открывает y верхних карт из колоды, выбирает из них все карты цветов 0 и color и кладёт их на стол. Затем Саша проделывает ту же процедуру с картами из его руки: выбирает из них все карты цветов 0 и color и кладёт их на стол. Если Саша положил на стол как минимум на x карт больше Славы, то он считается победителем, иначе — проигравшим.
При выборе цвета, используемого для постройки, Саша, естественно, выбирает тот, при котором вероятность его выигрыша максимальна.
Славе надоело придумывать параметры x и y наугад. Теперь перед тем, как произнести их вслух, он хочет посчитать вероятность, с которой Саша победит. Известно, что Слава тасует карты честно — все расклады возникают с равной вероятностью. Также Слава знает, что Саша играет по указанной выше стратегии.

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

В первой строке через пробел записаны два целых числа k и t (1 ≤ k ≤ 100, 0 ≤ t ≤ 100)  — максимальный возможный цвет и количество карт, которые Слава выдал Саше «вслепую».
Во второй строке через пробел записаны целые числа c0, …, ck, где ci — количество карт i-го цвета в колоде (0 ≤ ci). Общее число карт в колоде не превышает 100.
В третьей строке через пробел записаны целые s0, …, sk, где si — количество карт i-го цвета, которые Саша взял себе в руку в начале игры (0 ≤ sici).
В четвёртой строке через пробел записаны два целых числа x и y (0 ≤ x, y ≤ 100)  — параметры туннеля, которые придумал Слава.
Гарантируется, что после того, как Саша получил все свои карты, в колоде осталось не менее y карт.

Результат

Найдите вероятность, с которой Саша выиграет. Пусть итоговая вероятность в виде несократимой дроби имеет вид p/q, тогда выведите число p·(q)−1 по модулю 109+7.

Примеры

исходные данныерезультат
3 1
1 2 0 1
0 1 0 0
1 2
666666672
2 3
6 5 3
2 2 0
5 3
176428573

Замечания

В первом примере у Саши могут быть следующие наборы карт: {0, 1}, {1, 1} и {1, 3} (каждый из вариантов имеет вероятность 1/3). При постройке туннеля будет открыто ещё 2 карты, то есть все оставшиеся в колоде. При любых своих картах Саша попытается построить туннель картами цвета 1, и в двух случаях из трёх ему это удастся. Таким образом, ответ 2/3.
Перейдём ко второму примеру. Рассмотрим случай, в котором Саше достаются 3 карты цвета 0. Он произойдёт с вероятностью 1/30. При таком раскладе он выберет цвет 1, так как при выборе цвета 1 вероятность победы будет 31/35, а цвета 2  — 1/35. В случае, когда Саше достаются 3 карты цвета 2 (это произойдёт с вероятностью 1/120), Саша выберет цвет 2, так как при выборе цвета 1 вероятность победы будет 0, а цвета 2  — 1/35. Разобрав другие расклады аналогичным образом, получим итоговую вероятность, равную 471/1400.
Автор задачи: Евгений Курпилянский
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 2088. Вечер ностальгии