問題
ピアノの白鍵で隣り合った音をつなぎ、木魚を鳴らし、以下の条件でメロディを作る。
ドを≪開始音≫とし、p音高い音を≪終了音≫とする
メロディはn個の音と木魚の音からできている
≪開始音≫よりも低い音は使わない
メロディの途中にm回ぴったり木魚の音を入れなければならない
木魚は一つの音の最中に1回しか鳴らすことが出来ない
条件を満たすメロディは何パターンあるか
ただしパターンの数を100005の余りで出力せよ
入力
p n m
1 行で整数 p n mが与えられる
出力
x を出力せよ。出力の最後に改行を入れること
制約
全ての入出力ケースについて以下を満たす。
- 0 ≦ p < n ≦100
- 0 ≦ m ≦ n ≦ 100
入出力例
入力例1
3 12 1
出力例1
1980
解説
p=3(ファ)を終了音として、n=12個の音をつなぎ、木魚を１回鳴らすメロディは
1980パターンある。
入力例2
4 5 5
出力例2
1
解説
p=4(ソ)を終了音として、n=5個の音をつなぎ、木魚を５回鳴らすメロディは
ド→レ→ミ→ファ→ソで、各音で１回ずつ木魚を鳴らした１パターンのみである。
入力例3
1 3 3
出力例3
0
解説
p=1(レ)を終了音として、n=3個の音をつなぐメロディは存在しない。