Xét biểu thức sau: \((x + a)^n\) (với \(a,n\) là số được cho).

Yêu cầu: Khai triển biểu thức trên, tính hệ số bậc \(k\)?

Input

• Một dòng chứa ba số nguyên \(a,n,k\) (\(0 \le a \le 10^9; 1 \le n \le 2 \times 10^5; 0 \le k \le n\)).

Output

• Một dòng chứa một số nguyên duy nhất là kết quả bài toán, do kết quả có thể rất lớn, bạn cần đưa ra kết quả chia lấy phần dư cho \(10^9+7\).

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(a = 1, n \le 10\).
• Subtask \(2\) (\(25\%\) số điểm): \(n \le 10\).
• Subtask \(3\) (\(25\%\) số điểm): \(a = 1\).
• Subtask \(4\) (\(25\%\) số điểm): không có ràng buộc gì thêm.

Example

1 2 1

2