005 - メロディ作りα

問題

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

    
ドを≪開始音≫とし、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個の音をつなぐメロディは存在しない。