Професор і помогатор (helper)
Незабаром у фіксіків очікуються престижні змагання з ремонту складного обладнання. Як відомо, для усунення особливо складних поломок обладнання фіксікі використовують помогатор, однак їм треба вміти користуватися досконало!
Професор Геній Євгенович винайшов нову експериментальну модель помогатора. І всі хочуть з нею терміново ознайомитися. Але ... у професора відпустка! Сімка почала вмовляти його дати помогатор учням і після довгих умовлянь професор погодився, але з деякими умовами:
- Геній Євгенович віддасть пристрій фіксіку X і хоче забрати його після відпустки у фіксіка Y.
- Кожен день помогатор повинен міняти свого власника.
Всього в класі навчається M учнів, а відпустка професора триває N днів.
Дім Дімичу відразу стало цікаво, які можуть бути варіанти «подорожі» помогатора по учнях, а Сімка – скільки всього існує таких варіантів.
Формат введення виведення:
Програма helper зчитує з клавіатура (стандартного пристрою уведення) чотири цілих числа N, M (1 ≤ N, M ≤ 109), X, Y (1 ≤ X, Y ≤ M).
Програма helper виводить на екран (стандартний пристрій виведення) єдине число – кількість можливих варіантів «подорожі» помогатора по учнях, за заданими правилами. Оскільки число може бути дуже великим, виведіть залишок від ділення цього числа на 109 + 7.
Приклад вхідних та вихідних даних
Введення |
Виведення |
4 3 1 2 |
5
|
3 5 2 2 |
12 |
4 5 1 5 |
51 |
Примітка. У першому прикладі існують такі варіанти «подорожі» помогатора по учнях:
1 2 1 3 2
1 2 3 1 2
1 3 1 3 2
1 3 2 3 2
1 3 2 1 2
© LIKT 1998-2018