Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 100 点
問題文
埼大君はMaximum小学校の職員で、給食の献立作成担当をしています。
そろそろ献立表を作らなくてはいけない時期になってきたので、埼大君は献立表を考えることにしました。
献立はバランスが大事です。和食ばかりの献立や、洋食ばかりの献立では生徒に飽きられてしまいます。
そこで、まずその日に出すメニューのジャンルを決めることにしました。メニューは、
- 和食のメニュー
- 洋食のメニュー
- 中華のメニュー
- 和食洋食混合のメニュー
- 和食中華混合のメニュー
- 洋食中華混合のメニュー
- 和・洋・中ごちゃまぜメニュー
の7種類です。
今回考えたいのは「どの連続したK日間でも同じジャンルが含まれるメニューを出す日をL日以下」という条件を満たしたN日間の給食の献立です。
ここで、混合メニューやごちゃまぜメニューを出すと、その中に含まれるすべてのジャンルを出したことになります。
例えば和洋混合メニューを出したとすると、その日は和食メニューと洋食メニューを両方出したことになります。
詳しくは下の表を参照してください。
さて、それを見ていた組み合わせマスターのあなたはふと思いました。
「これは、何通り考えられるだろう、、、???」
この条件を満たす献立の組み合わせの総数を求めてください。
なお、答えは非常に大きくなる可能性があるため、1000000007の余りの形で出力してください。
条件について
N = 5, K = 5, L = 3として考えます。
この時、例1ではすべてのジャンル(和食・洋食・中華)が5日間のうち3日以内になってい るので、条件を満たしています。
一方、例2では洋食が5日間のうち4日間登場してしまっているので、条件を満たせていないこと になります。
1日目 | 2日目 | 3日目 | 4日目 | 5日目 | |
例1 | 和食のメニュー | 和食中華混合のメニュー | 中華のメニュー | 洋食のメニュー | 中華のメニュー |
例2 | 洋食のメニュー | 和食洋食混合のメニュー | 洋食中華混合のメニュー | 和食のメニュー | 和・洋・中ごちゃまぜメニュー |
制約
- K \leq N \leq 365
- 2 \leq K \leq 5
- 1 \leq L \leq K
入力
入力は以下の形式で標準入力から与えられます。
N K L
出力
答えを1行で出力してください。
入力例 1
3 3 1
出力例 1
6
入力例 2
15 3 2
出力例 2
213221133
1000000007の余りの形で出力してください。
入力例 3
365 5 3
出力例 3
792323641
入力例 4
5 5 1
出力例 4
0
献立が作れない可能性もあります。