Determinant

A combinatorial matrix of order N is a square matrix with N rows and N columns, where each element is determined by the formula:

A_{i, j} = X + δ_{i, j}·Y, with X and Y being arbitrary numbers.

Your task is to compute the determinant of this combinatorial matrix of order N, given the numbers X and Y. Since the result can be very large, you should provide the determinant modulo K.

Input

The input consists of a single line containing four integers: N, X, Y, and K.

2 ≤ N ≤ 2^31-1; X ≤ 1000; Y ≤ 1000; 1 ≤ K ≤ 10000.

Output

Output a single integer, which is the remainder when the determinant of the combinatorial matrix is divided by K.

Examples