問題
長さ$N$の数列$A$と整数$K$が与えられる。
$A_1^{A_2^{.^{.^{.^{A_N}}}}}$を$K$で割った余りを出力せよ。
具体的には$i = N-1,N-2$ $...$ $2,1$について以下の操作をした後の$A_1$を$K$で割った余りを出力せよ。
・$A_i$を$A_i^{A_(i+1)}$に置き換える。
入力
入力は以下の形式で標準入力から与えられる。
$N$ $K$ $A_1$ $A_2$ ... $A_N$
出力
出力の最後に改行を入れること。
制約
全ての入出力ケースについて以下を満たす。
- $1 \leq N,K \leq 1000$
- $1 \leq A_i \leq 10^{9}$ 与えられる数はすべて整数である。
入出力例
入力例1
4 7 2 2 2 2
出力例1
2
$2^{2^{2^{2}}}=65536≡2(mod7)$