28563번 - Проблемы с костюмом 다국어

문제

Все знают, что сделать качественный костюм на Хэллоуин довольно сложно. В этом году Джек начал готовиться к Хэллоуину сильно заранее, чтобы успеть сделать самый интересный костюм пугала, который только можно представить.

Он уже твердо решил, что у его костюма будет ровно пять конечностей и ровно три головы. Выбирая составляющие своего костюма, Джек наткнулся на сайт пугал, на котором продавались $n$ понравившихся ему типов конечностей и $m$ типов голов. Таким образом, каждая из пяти конечностей может быть любого из $n$ типов независимо от других, и каждая голова, аналогично, может быть любого из $m$ типов независимо от других.

К сожалению, когда Джек заказывал все <<детали>>, на складе что-то перепутали и собрали ему в заказ $a$ случайных конечностей и $b$ случайных голов. Каждая конечность была выбрана независимо и равновероятно, то есть тип каждой конечности может быть любым с вероятностью $\frac{1}{n},ドル и аналогично для голов.

Изменить заказ уже, разумеется, нельзя, поэтому Джеку стало интересно, каково математическое ожидание количества различных костюмов, которые он сможет собрать из деталей в заказе. Помогите ему найти эту величину. Два костюма считаются различными, если они отличаются хотя бы одной конечностью или хотя бы одной головой с учетом их порядка (<<нога, рука>> -- не то же самое, что и <<рука, нога>>).

Поскольку посчитать эту величину достаточно точно может быть невозможно, выполняйте все арифметические операции в поле остатков по простому модулю $p = 1073676287$. Это означает, что если точный ответ представляется рациональной дробью $\frac{x}{y},ドル вам стоит вывести такое $z,ドル что $z \cdot y \equiv x \mod p$.

입력

В первой строке через пробел даны два целых числа $n$ и $m$ (1ドル \leq n, m \leq 666$) --- количество типов конечностей и типов голов, соответственно.

Во второй строке через пробел даны два целых числа $a$ и $b$ (5ドル \leq a \leq 10^9$; 3ドル \leq b \leq 10^9$) --- количество конечностей и голов в заказе, который отправлен Джеку.

출력

Выведите единственное целое число --- математическое ожидание количества различных костюмов, которые может составить Джек из такого заказа, если любой набор типов конечностей и голов в заказе равновероятен.

Выведенное целое число должно быть результатом вычисления рациональной дроби, равной математическому ожиданию, в поле остатков по модулю $p$.

제한

노트

Во втором примере из условия ответ равен $\frac{20}{8}$ или $\frac{5}{2}$. Несложно убедиться, что 536838146ドル \cdot 2 = p + 5$.