問題
ピアノの白鍵で隣り合った音をつなぎ、以下の条件でメロディを作る。
ドを≪開始音≫とし、p音高い音を≪終了音≫とする。
メロディは4/4拍子のn小節上の音からできている。
音は８分音符、４分音符、２分音符を使用できる。
音は間隔を開けずにならし、休符はない物とする。
≪開始音≫よりも低い音は使わない
※補足
音楽詳しくない人のために説明します
一小節は４拍で、８分音符は0.5拍、４分音符は１拍、２分音符は２拍の長さだよ。
これは８分音符を一小節におけるだけおいてみた例だよ
かえるのうたのでサンプルを作ってみたよ これで一小節分だよ
条件を満たすメロディは何パターンあるか
ただしパターンの数を100005の余りで出力せよ
入力
p n
1 行で整数 p nが与えられる
出力
x を出力せよ。出力の最後に改行を入れること
制約
全ての入出力ケースについて以下を満たす。
- 0 ≦ p , n ≦100
入出力例
入力例1
1 1
出力例1
116
解説
p=1(レ)を終了音とする、n=1小節の中で出来るメロディは
116パターンある。
入力例2
1 14
出力例2
81521
入力例2
5 14
出力例3
76689