Empire là một trò chơi chiến thuật rất phổ biến trên thế giới. Người chơi sẽ xây dựng và chỉ huy quân đội của mình chiến đấu với đối phương. Kì nghỉ hè đã đến, Empire trở thành trò chơi yêu thích của Raldono và Balitello. Bản đồ của trò chơi được chia thành ~N~ vùng đất nằm trên một đường thẳng và được đánh số từ ~1~ đến ~N~. Trước khi trò chơi bắt đầu, mỗi người sẽ chọn cho mình một số vùng đất (tối thiểu là ~1~ vùng đất) để tiến hành xây dựng căn cứ sao cho mỗi vùng đất chỉ được chọn bởi tối đa một người. Ngoài ra, các vùng đất được chọn phải thỏa các điều kiện sau:

• Balitello muốn trong bất kì ~K~ vùng đất liên tiếp, Raldono không được chọn quá ~2~ vùng đất.
• Ngược lại, Raldono cũng muốn trong một dãy bất kì các vùng đất liên tiếp, nếu có ít nhất ~M~ vùng đất được chọn bởi Balitello thì phải có ít nhất ~1~ vùng đất được chọn bởi Raldono.

Mỗi lần chơi, Raldono và Balitello sẽ chọn các vùng đất theo một cách mà họ chưa từng chọn trước đó. Do vậy, họ muốn biết có bao nhiêu cách khác nhau để chọn các vùng đất trong trò chơi. Hai cách được gọi là khác nhau khi tồn tại một người có tập các vùng đất được chọn là khác nhau trong hai cách đó. Vì số cách có thể rất lớn nên bạn chỉ cần tìm phần dư của số cách khi chia cho ~1000000007~ (~10^{9}~ + ~7~).

Input

Một dòng duy nhất chứa ~3~ số nguyên dương ~N~, ~M~ và ~K~.

Output

Một số nguyên là phần dư của số cách tìm được khi chia cho ~1000000007~.

Giới hạn

Ràng buộc:

• Trong tất cả các test, ~N~, ~M~, ~K \leq 10000~ và ~K \leq N~.
• Trong 15% số test, ~N~, ~M~, ~K \leq 15~.
• Trong 50% số test, ~N~, ~M~, ~K \leq 500~.

Sample Input 1

2 2 2

Sample Output 1

2

Sample Input 2

3 2 3

Sample Output 2

10

Note

Hình minh họa cho 2 test mẫu, vùng đất Raldono chọn được tô màu đỏ, vùng đất Balitello chọn được tô màu xanh: