Tú Anh rất thích hai chữ số là \(a\) và \(b\). Bạn ấy định nghĩa một số nguyên dương là số tốt nếu trong biểu diễn thập phân của nó chỉ chứa 2 loại chữ số là \(a\) và \(b\). Một số tốt được cho là tuyệt vời nếu tổng các chữ số của nó là một số tốt. Ví dụ \(a = 2\), \(b = 5\) thì \(15\) không phải số tốt, \(25\) là số tốt, \(55555\) là số tuyệt vời.

Tú Anh muốn biết có bao nhiêu số tuyệt vời có độ dài \(n\). Vì kết quả có thể rất lớn nên bạn ấy muốn lấy kết quả module \(1000000007 (10^9 + 7)\)

Độ dài của một số là số các chữ số trong biểu diễn thập phân của nó không tính các số \(0\) ở đầu.

Input

• Một dòng chứa ba số nguyên dương \(a, b, n\).

Output

• In ra một số nguyên là kết quả module \(1000000007 (10^9 + 7)\)

Constraints

• \(0 \le a < b \le 9\)

• \(1 \le n \le 10^6\)

Example

Sample Input

2 3 10

Sample Output

165