Задачі
Детермінант
Детермінант
Комбінаторною матрицею N-го порядку називається квадратна матриця із N рядків та N стовпців, елементи якої обчислюються за формулою:
A_{i, j} = X + δ_{i, j}·Y, де , X, Y - довільні числа.
Потрібно по заданих числах X та Y обчислити детермінант комбінаторної матриці N-го порядку. Оскільки відповідь може вийти дуже великою, потрібно обчислити його по модулю K.
Вхідні дані
У єдиному рядку вхідного файлу записані чотири цілих числа N, X, Y і K.
2 ≤ N ≤ 2^31-1; X ≤ 1000; Y ≤ 1000; 1 ≤ K ≤ 10000.
Вихідні дані
Вивести одне єдине число - залишок від ділення детермінанта комбінаторної матриці на число K.
Приклад
Вхідні дані #1
1 0 1 10000
Вихідні дані #1
1