eolymp
bolt
Try our new interface for solving problems
Problems

Детерминант

Детерминант

Time limit 1 second
Memory limit 64 MiB

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

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

Нужно по заданным числам X и Y вычислить детерминант комбинаторной матрицы N-го порядка. Так как ответ может получится очень большим, нужно вычислить его по модулю K.

Input data

В единственной строке входного файла записаны четыре целых числа N, X, Y и K.

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

Output data

Вывести одно единственное число - остаток от деления детерминанта комбинаторной матрицы на число K.

Examples

Input example #1
1 0 1 10000
Output example #1
1
Source Всеукраинская студенческая олимпиада по программированию, ФИНАЛ, Харьков 15 октября 2011, 2-я лига