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