AT_maximum_cup_2018_f 献立表制作

[problemUrl]: https://atcoder.jp/contests/maximum-cup-2018/tasks/maximum_cup_2018_f 埼大君は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 $ 洋食のメニュー 和食洋食混合のメニュー 洋食中華混合のメニュー 和食のメニュー 和・洋・中ごちゃまぜメニュー

入力は以下の形式で標準入力から与えられます。 > $ N $ $ K $ $ L $

答えを$ 1 $行で出力してください。

### 制約 - $ K\ \leq\ N\ \leq\ 365 $ - $ 2\ \leq\ K\ \leq\ 5 $ - $ 1\ \leq\ L\ \leq\ K $ $ Sample\ Explanation\ 2 $ 1000000007 $の余りの形で出力してください。### Sample Explanation 4 献立が作れない可能性もあります。