Background

小\(\operatorname{L}\)养了一只\(\operatorname{R}\)，并和这只\(\operatorname{R}\)玩起了智力游戏。

Description

小\(\operatorname{L}\) 想让他的\(\operatorname{R}\)计算
\((x^n+y^n)\mod p\)。

经过珂爱的\(\operatorname{R}\)的百般恳求，小\(\operatorname{L}\) 终于答应说出 \(x+y, x\times y\) 和 \(n\)。

这只\(\operatorname{R}\)找到了小\(\operatorname{C}\)，请小\(\operatorname{C}\)告诉它结果的值。

但是小\(\operatorname{C}\)不会算，所以请你告诉他结果。如果你算出来，\(\operatorname{CRL}\)会给你 \(e^{i\pi} + 1\) 袋中华牌\(\operatorname{R}\)食。

Format

Input

第一行 \(4\) 个正整数，分别为 \(x\times y,x+y,n,p\) 。

Output

一行一个整数表示 \(x^n+y^n \bmod p\) 的值。

Sample 1

Input

30 11 3 37

Output

8

Limitation

数据保证 \(xy,x+y,n\) 均为正整数，

对于 \(30\%\) 的测试点，保证 \(x, y\) 均为正整数。

对于 \(100\%\) 的测试点，满足 \(n\leq 5\times 10^7 , x\times y\leq 10^4, x+y\leq 10^3, p\leq 10^9\)。