Số đẹp

Cho hai chữ số $a$ và $b$ (với $a<b$). Một số nguyên dương được gọi là số đẹp nếu biểu diễn thập phân của nó chỉ chứa các chữ số $a$ và $b$ (không chứa bất kỳ chữ số nào khác).

Một số đẹp được gọi là số tuyệt vời nếu tổng các chữ số của nó cũng là một số đẹp.

Ví dụ, nếu $a=1$ và $b=3$ thì số $12$ không đẹp, còn $13$ và $311$ là các số đẹp. Ngoài ra, số $111$ là số tuyệt vời (tổng chữ số bằng $3$, là số đẹp), còn số $11$ thì không (tổng chữ số bằng $2$, không phải số đẹp).

Hãy đếm số lượng số tuyệt vời có đúng $n$ chữ số. Vì kết quả có thể rất lớn, hãy in ra phần dư khi chia cho ${10}^9+7$.

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

Dữ liệu vào

Một dòng duy nhất chứa ba số nguyên $a$, $b$, $n$.

Dữ liệu ra

In ra một số nguyên duy nhất: số lượng số tuyệt vời có đúng $n$ chữ số, lấy phần dư khi chia cho ${10}^9+7$.

Ràng buộc

• $1\le a<b\le 9$
• $1\le n\le {10}^6$

Ví dụ