N bonacci Sequence

以上の正の整数 と 以上の正の整数 が与えられます。
以下のように定義される ボナッチ数列 の第 項である を で割った余りを求めてください。

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

2 5

5

4 10

94

5 2

1

100 1000000000000000000

255580063

つ目の例は， です。 より， を出力すればよいです。
つ目の例は， です。 より， を出力すればよいです。
つ目の例は， です。 より， を出力すればよいです。