Детерминант

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

Примеры