Background

土拨鼠译正正在做算术题 但是这道题的计算量太大了, 于是他向你求助.

Description

给定正整数$x, n, k, P$, 请求出下式的计算结果:

$(x^{0k}+x^{1k}+x^{2k}+...+x^{nk})\ mod\ P$

其中$x^n$是幂次运算, 代表$n$个$x$相乘的结果.

$x\ mod\ n$代表的是取余运算.

Format

Input

第一行输入四个正整数$x, n, k, p$

Output

输出一个非负整数表示答案

Samples

5 2 3 17

9

$(5^{0 \cdot 3}+5^{1 \cdot 3} + 5^{2 \cdot 3})\space mod \space 17 = 9$

Limitation

$1 <= x <= 10^9$

$1 <= n <= 10^6$

$1 <= k <= 10^6$

$1 <= P <= 10^9$, 确保P为质数