Детермінант

Комбінаторною матрицею 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.

Приклади