Bạn có \(n\) xí ngầu và mỗi viên có \(k\) mặt \((1 \le n, k \le 30)\). Hãy đếm số cách lắc xí ngầu sao cho tổng số mặt ra được \(s\) điểm (\(1 \le s \le 10^3\)). Kết quả lưu trong modulo \(10^9+7\).

Input

• Một dòng chứa 3 số nguyên: \(n\) \(k\) \(s\).
• \(n\) là số viên xí ngầu, \(k\) là số mặt của mỗi viên, \(s\) là số điểm cần đạt được.

Example

Sample input 1

1 6 3

Sample output 1

1

Giải thích 1

Có 1 viên xí ngầu có 6 mặt và chỉ có 1 cách lắc ra được 3 điểm.

Sample input 2

2 6 7

Sample output 2

6

Giải thích 2

Có 2 viên xí ngầu có 6 mặt. Kết quả có 6 cách lắc ra 7 điểm: 1+6, 2+5, 3+4, 4+3, 5+2, 6+1.

Sample input 3

30 30 500

Sample output 3

222616187