Олимпиадный тренинг

Задача . E. Студенческий лагерь

Задача

Примерный студент МАИ Алёша получил путёвку в студенческий лагерь Алушта на берегу моря. К сожалению, рядом с лагерем наступила пора сильного бриза, и он рискует быть разрушенным!

Здание лагеря представляет собой прямоугольник высотой n + 2 бетонных блока и шириной m блоков. Каждый день бриз дует с моря, и каждый блок, кроме блоков верхнего и нижнего ряда, левее которого нет других неразрушенных блоков, разрушается с вероятностью $\text{[math]}$ . Аналогично каждую ночь сильный бриз дует на море, и каждый блок, кроме верхнего и нижнего ряда, правее которого нет других неразрушенных блоков, разрушается с той же вероятностью p. Обратите внимание, что верхние и нижние блоки неразрушимы, то есть всего существует n·m разрушимых блоков.

Время бурь продлится k дней и k ночей. В случае если за это время здание лагеря разделится на хотя бы две компоненты связности, оно разрушится, и Алёше придется искать другое времяпрепровождение на лето.

Найдите вероятность того, что Алёше не придётся искать новое занятие на лето, и он сможет отдохнуть в летнем лагере.

Входные данные

В первой строке входных данных заданы два целых числа n и m (1 ≤ n, m ≤ 1500), определяющие размеры разрушимой части здания.

Во второй строке заданы два целых числа a и b (1 ≤ a ≤ b ≤ 10⁹), задающих вероятность разрушения блоков. Гарантируется, что числа a и b взаимно просты.

В третьей строке задано целое число k (0 ≤ k ≤ 100 000) — количество дней и ночей, в течение которых будет дуть сильный ветер.

Выходные данные

Пусть ответ в виде несократимой дроби равен $\text{[math]}$ . Выведите одно целое число, равное $\text{[math]}$ . Гарантируется, что при данных ограничениях $\text{[math]}$ .

Примечание

В первом тестовом примере каждый из четырёх блоков разрушается с вероятностью $\text{[math]}$ . Для того чтобы здание не разрушилось, существует 7 вариантов того, как может выглядеть здание после одного дня, если оно не потеряло связность, то есть искомая вероятность равна $\text{[math]}$ , а значит нужно вывести $\text{[math]}$

$\text{[math]}$

Примеры

№	Входные данные	Выходные данные
1	2 2 1 2 1	937500007
2	5 1 3 10 1	95964640
3	3 3 1 10 5	927188454

time 3000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

	Кол-во
С++ Mingw-w64	5

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Загруженные файлы

Нет