問題
以下の初期値及び漸化式で定まる数列 (An)n≥1 の第 k 項 (=Ak) を M で割った余りを求めてください。
⎩⎨⎧A1=aA2=bAn=(An−2)m+(An−1)m(forn≥3)
制約
- 2≤M≤500
- 0≤a<M
- 0≤b<M
- 1≤m≤109
- 1≤k≤109
- 入力は全て整数
入力
入力は標準入力から以下の形式で与えられます。
出力
数列の第 k 項を M で割った余り(0 以上 M 未満の整数となります)を標準出力に出力してください。
入出力例
例 1
数列は 1,1,2,3,5,8,13,… と続きます。
例 2
M で割った余りを出力してください。