問題文

埼大君はMaximum小学校の職員で、給食の献立作成担当をしています。
そろそろ献立表を作らなくてはいけない時期になってきたので、埼大君は献立表を考えることにしました。
献立はバランスが大事です。和食ばかりの献立や、洋食ばかりの献立では生徒に飽きられてしまいます。

そこで、まずその日に出すメニューのジャンルを決めることにしました。メニューは、

• 和食のメニュー
• 洋食のメニュー
• 中華のメニュー
• 和食洋食混合のメニュー
• 和食中華混合のメニュー
• 洋食中華混合のメニュー
• 和・洋・中ごちゃまぜメニュー

の7種類です。

今回考えたいのは「どの連続したK日間でも同じジャンルが含まれるメニューを出す日をL日以下」という条件を満たしたN日間の給食の献立です。

ここで、混合メニューやごちゃまぜメニューを出すと、その中に含まれるすべてのジャンルを出したことになります。
例えば和洋混合メニューを出したとすると、その日は和食メニューと洋食メニューを両方出したことになります。
詳しくは下の表を参照してください。

さて、それを見ていた組み合わせマスターのあなたはふと思いました。

「これは、何通り考えられるだろう、、、？？？」

この条件を満たす献立の組み合わせの総数を求めてください。

なお、答えは非常に大きくなる可能性があるため、1000000007の余りの形で出力してください。

条件について

N = 5, K = 5, L = 3として考えます。

この時、例1ではすべてのジャンル(和食・洋食・中華)が5日間のうち3日以内になってい るので、条件を満たしています。

一方、例2では洋食が5日間のうち4日間登場してしまっているので、条件を満たせていないこと になります。

制約

• K \leq N \leq 365
• 2 \leq K \leq 5
• 1 \leq L \leq K

入力例 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

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