hyper fibonacci sequence

問題

以下の初期値及び漸化式で定まる数列 $(A_n)_{n \geq 1}$ の第 $k$ 項 ($= A_k$) を $M$ で割った余りを求めてください。

$\left\{\begin{array}{l} A_1 = a \\ A_2 = b \\ A_n = (A_{n - 2})^m + (A_{n - 1})^m \hspace{0.5em} (\mathrm{for} \hspace{0.4em} n \geq 3) \end{array}\right.$

制約

• $2 \leq M \leq 500$
• $0 \leq a < M$
• $0 \leq b < M$
• $1 \leq m \leq 10^9$
• $1 \leq k \leq 10^9$
• 入力は全て整数

入力

入力は標準入力から以下の形式で与えられます。

出力

数列の第 $k$ 項を $M$ で割った余り($0$ 以上 $M$ 未満の整数となります)を標準出力に出力してください。

入出力例

例 1

500 1 1 1 7

13

数列は $1, \, 1, \, 2, \, 3, \, 5, \, 8, \, 13, \dots$ と続きます。

例 2

2 1 1 10 100000

1

$M$ で割った余りを出力してください。