0455 - ホゲナッチ数列

ストーリー

思いつかなかった...＞＜

問題

• A₁=a
  
• A₂=b
  
• A_n = (A_n-1 + A_n-2) Mod 10007
  

で表される数列Aがある.
n と A_n が与えられた時, A_n 未満の a, b の組み合わせの通り数 p を求めよ.

入力

n
An

1 行目に整数 n が与えられる.

2 行目に整数 A_n が与えられる.

出力

A_n = (A_n-1 + A_n-2) Mod 10007 を満たす A_n 未満の a, b の組み合わせの通り数 p を求めよ.
出力の最後に改行を入れること.
※なお,a = bの時は重複して通り数に数えない.

制約

制約は以下のとおりである.

• 0 ≦ A_n ＜ 10007(=10⁴+7)
• 0 ≦ a, b ＜ A_n
• 3 ≦ n ≦ 100000000(=10⁸)

---

入出力例

入力例1

10
55

出力例1

1

解説

An = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55}

上記の数列のみが考えられる.
a = bなので重複して通り数に数えない事に注意.

---

入力例2

3
3

出力例2

2

解説

An = {1, 2, 3}

An = {2, 1, 3}

上記の2通りが考えられる.

---

入力例3

100000000
10006

出力例3

10005

---

• 工夫して計算すれば誰でも解けるはず(一応数学強い人なら解けるはず)
• 制限時間厳しめかもしれないのでC/C++推奨(ei1333が爆速で通してた.)
• 実はこの問題はあるアルゴリズムの典型問題らしい(全く想定していなかった)