hyper fibonacci sequence

2 secs 1024 MB
naskya

問題


以下の初期値及び漸化式で定まる数列 の第 項 () を で割った余りを求めてください。

制約


  • 入力は全て整数

入力


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

出力


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

入出力例


例 1


入力
500 1 1 1 7
出力
13

数列は と続きます。

例 2


入力
2 1 1 10 100000
出力
1

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

提出


Go (1.14)