Визначник#2694
Комбінаторна матриця порядку — це квадратна матриця з рядків і стовпців, де кожен елемент визначається за формулою:
A_{i, j} = X + \delta_{i, j} \cdot Y, де і — довільні числа.
Ваше завдання — обчислити визначник такої комбінаторної матриці порядку , знаючи числа та . Оскільки результат може бути дуже великим, потрібно вивести визначник по модулю .
Вхідні дані містять один рядок із чотирма цілими числами: , , та .
2 \leq N \leq 2^{31} - 1; X \leq 1000; Y \leq 1000; 1 \leq K \leq 10000.
Виведіть одне ціле число — залишок від ділення визначника комбінаторної матриці на .
Приклад 1