eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Детермінант

Детермінант

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Комбінаторною матрицею N-го порядку називається квадратна матриця із N рядків та N стовпців, елементи якої обчислюються за формулою:

A_{i, j} = X + δ_{i, j}·Y, де , X, Y - довільні числа.

Потрібно по заданих числах X та Y обчислити детермінант комбінаторної матриці N-го порядку. Оскільки відповідь може вийти дуже великою, потрібно обчислити його по модулю K.

Вхідні дані

У єдиному рядку вхідного файлу записані чотири цілих числа N, X, Y і K.

2N2^31-1; X1000; Y1000; 1K10000.

Вихідні дані

Вивести одне єдине число - залишок від ділення детермінанта комбінаторної матриці на число K.

Приклад

Вхідні дані #1
1 0 1 10000
Вихідні дані #1
1
Джерело Всеукраїнська студентська олімпіада з програмування, ФІНАЛ, Харків 15 жовтня 2011, 2-га ліга