N bonacci Sequence

2 secs 1024 MB
OxOmiso

問題文


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

制約



入力


出力


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

入力例


2 5

出力例


5

入力例


4 10

出力例


94

入力例


5 2

出力例


1

入力例


100 1000000000000000000

出力例


255580063

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

Submit


Go (1.14)