Giải bài trực tuyến

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⁹ + 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

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

Chấm bài

Bài của bạn sẽ được chấm trên thang điểm 100. Điểm mà bạn nhận được sẽ tương ứng với % test mà bạn giải đúng.

Trong quá trình thi, bài của bạn sẽ chỉ được chấm với 2 test ví dụ có trong đề bài.

Khi vòng thi kết thúc, bài của bạn sẽ được chấm với bộ test đầy đủ.

Example

Input

2 2 2

Output

2

Input

3 2 3

Output

10

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: