F - 献立表制作

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

献立が作れない可能性もあります。