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-я лига