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$。