#903 Yet Another Prefix Sum Problem

Statement

Statement language

You are given positive integers $A,D,N$ and a prime number $p$ .

Compute the following value:

\left(\sum_{i=0}^{N-1}(A+iD)^{A+iD}\right)\bmod p

The input is given in the following format:

$A\ D\ N\ p$

Print the computed value on one line.

Sample 1

Input

1 1 5 7

Output

4

The five terms are $1^1,2^2,3^3,4^4,5^5$ . Their sum has remainder modulo .