問題
$x^{y^{z}}$を$w$で割った余りを出力せよ。
$x^{y^{z}}$は$(x^{y})^{z}$ではないことに留意せよ。
入力
入力は以下の形式で標準入力から与えられる。
$x$ $y$ $z$ $w$
出力
$x^{y^{z}}$を$w$で割った余りを出力せよ。
出力の最後に改行を入れること。
制約
全ての入出力ケースについて以下を満たす。
- $1 \leq x,y,z,w \leq 10^{6}$ 与えられる数はすべて整数である。
入出力例
入力例1
90 5 5 7
出力例1
6
$90^{3125}$≡$-1^{3125}≡-1(mod7)$なので余りは6です。