Vitaly là một người rất kỳ lạ. Anh ta có hai chữ số yêu thích là \(a\) và \(b\). Vitaly gọi một số nguyên dương tốt, nếu biểu diễn thập phân của số này chỉ chứa các chữ số \(a\) và \(b\). Vitaly gọi một số xuất sắc nếu số tốt đó cổng các chữ số là một số tốt.
Ví dụ, giả sử các chữ số yêu thích Vitaly là \(1\) và \(3\), thì số \(12\) không phải là số tốt, nhưng các số \(13\) hoặc \(311\) là số tốt. Ngoài ra, số \(111\) là số xuất sắc, nhưng số \(11\) thì không.
Bây giờ, Vitaly tự hỏi có bao nhiêu số xuất sắc có độ dài đúng bằng \(n\). Vì con số này có thể rất lớn, anh ta yêu cầu bạn tính số dư sau khi chia kết quả cho \(10^9 + 7\)
Độ dài của một số là số lượng các chữ số trong biểu diễn thập phân của nó mà không có số 0 đứng đầu.

INPUT

• Một dòng duy nhất chứa ba số nguyên \(a,b,n (1 \leq a < b \leq 9, 1 \leq n \leq \ 10^6)\)

OUTPUT

• In ra một số nguyên duy nhất là kết quả bài toán sau khi lấy dưa cho \(10^9 + 7\)

Example

1 3 3

1

2 3 10

165