Perfect Number

Problem Description

For given digits $a, b$, when every decimal digit of an integer $n$ is either $a$ or $b$, we call $n$ a "good number".

For a good number $n$, when the sum of all its decimal digits is also a "good number", we call $n$ a "perfect number".

Find how many $m$-digit numbers are "perfect numbers".

Input Format

A single line containing three integers $a, b, m$ ($1 \le m \le 10^6$, $1 \le a, b \le 9$).

Output Format

Output one integer: the number of perfect numbers. Since the answer may be very large, output it modulo $10^9 + 7$.

Sample Input

5 1 5

Sample Output

1

Sample Explanation

Only $11111$ satisfies the requirement.