Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P144SUMC - ROUND 4C - Số tuyệt đẹp

Tèo có một sở thích đặc biệt khi rất thích các số được tạo bởi 2 số a, b, cậu gọi các số như vậy là số đẹp. Đặc biệt hơn nữa, các số đẹp có tổng các chữ số là một số đẹp, cậu gọi là số tuyệt đẹp.

Ví dụ: Tèo thích các số 1 và 3, số 11, 311 là số đẹp còn 12 thì không.

Số 111 là số tuyệt đẹp, 11 thì không phải.

Giờ Tèo muốn biết có bao nhiêu số tuyệt đẹp có n chữ số, tất nhiên chữ số 0 không đứng ở đầu.

Kết quả được lấy dư cho (10^9 + 7).

Input

Dòng duy nhất có 3 số nguyên a, b, n ( 1 <= a, b <=9, 1 <=n <= 10^6).

Output

In ra kết quả của bài toán.

Example

Test 1:

Input:

1 3 3

Output:

1

 

Test 2:

Input:

2 3 10

Output:

165


Được gửi lên bởi:adm
Ngày:2014-07-17
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP CPP C++ 4.3.2 CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.