006 - メロディ作り

問題

ピアノの白鍵で隣り合った音をつなぎ、以下の条件でメロディを作る

  
ドを≪開始音≫とし、p音高い音を≪終了音≫とする
  
メロディはn個の音からできている
  
≪開始音≫よりも低い音は使わない

条件を満たすメロディは何パターンあるか

ただしパターンの数を100005の余りで出力せよ

入力

p n

1 行で整数 p n が与えられる

出力

x を出力せよ。出力の最後に改行を入れること

制約

全ての入出力ケースについて以下を満たす

• 0 ≦ p < n ≦ 100

入出力例

入力例1

3 12

出力例1

165

解説

p=3(ファ)を終了音として、n=12個の音をつなぐメロディにする

ド→レ→ド→レ→ミ→レ→ド→レ→ミ→ファ→ソ→ファ

は条件を満たす

しかし

ド→レ→ミ→ド→レ→ミ→ミ→……

の様なメロディは条件を満たさない

ミ→ド や ミ→ミ のように隣り合わない音を使っているからである

入力例2

4 5

出力例2

1

解説

p=4(ソ)を終了音として、n=5個の音をつなぐメロディは

ド→レ→ミ→ファ→ソ　のみである

入力例3

1 3

出力例3

0

解説

p=1(レ)を終了音として、n=3個の音をつなぐメロディは存在しない