Background

胖头鱼珍藏了许许多多的 OI 资料，可惜他把密码忘记了。

Description

胖头鱼只记得他的密码是 \(x^n+y^n \bmod p\)，具体的 \(x,y\) 他都忘记了，但是他还记得 \(x\times y,x +y\) 和 \(n\)。需要注意的是，这个数可能太大了，需要对 \(p\) 取模。

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\)。

Source

SeekLuna Original