Trong giờ học lý thuyết số, thầy giáo giao cho Per bài toán sau.

Cho hai chữ số ~a~ và ~b~ khác nhau. Một số tốt là số nguyên dương mà biểu diễn thập phân của nó chỉ gồm hai chữ số ~a~ và ~b~ (có thể chỉ dùng một trong hai). Một số Siu là một số tốt mà tổng các chữ số của nó cũng là một số tốt.

Hỏi trong các số có đúng ~n~ chữ số, có bao nhiêu số là số Siu?

Vì số lượng rất lớn nên hãy chia dư đáp án cho ~10^9 + 7~.

Dữ liệu vào

Dòng đầu tiên và duy nhất chứa ba số nguyên ~a~, ~b~ và ~n~.

Kết quả

In ra số lượng số Siu có đúng ~n~ chữ số, đã chia dư cho ~10^9 + 7~.

Ví dụ

Đầu vào:

1 3 3

Đầu ra:

1

Giải thích: Các số tốt có ~3~ chữ số là ~111, 113, 131, 133, 311, 313, 331, 333~. Tổng các chữ số của chúng lần lượt là ~3, 5, 5, 7, 5, 7, 7, 9~. Chỉ có ~3~ là số tốt (chỉ gồm chữ số ~3~), nên số Siu duy nhất là ~111~.

Giới hạn

• ~1 \le a, b \le 9~ và ~a \ne b~
• ~1 \le n \le 10^6~

Nhận xét quan trọng: một số tốt có ~n~ chữ số được xác định bởi số lượng chữ số ~a~ trong nó. Nếu có ~k~ chữ số ~a~ và ~n - k~ chữ số ~b~ thì tổng các chữ số luôn bằng

~S(k) = k \cdot a + (n - k) \cdot b~

không phụ thuộc vào vị trí các chữ số. Có đúng ~\dbinom{n}{k}~ số tốt như vậy.

Vậy chỉ cần lặp ~k~ từ ~0~ đến ~n~, kiểm tra xem ~S(k)~ có phải số tốt hay không (chỉ mất ~O(7)~ vì ~S(k) \le 9 \cdot 10^6~), rồi cộng ~\dbinom{n}{k}~ vào đáp án.