题目描述

Vitaly is a very weird man. He's got two favorite digits $a$ and $b$. Vitaly calls a positive integer good, if the decimal representation of this integer only contains digits $a$ and $b$. Vitaly calls a good number excellent, if the sum of its digits is a good number.

For example, let's say that Vitaly's favorite digits are 1 and 3, then the number 12 isn't good and the numbers 13 or 311 are. Also, the number 111 is excellent and the number 11 isn't.

Now Vitaly is wondering, how many excellent numbers of length exactly $n$ are there. As this number can be rather large, he asks you to count the remainder after dividing it by $1000000007$ ($10^9 + 7$).

A number's length is the number of digits in its decimal representation without leading zeroes.

中问题意

给定两个不同的数字$a,b（1≤a<b≤9）$。

好数：只包含数字$a$和$b$的正整数。

极好数：既是好数，且其数位和也是好数的正整数。

求有多少个恰好n位的极好数？答案对$10^9+7$取模。 数据范围：$1≤a<b≤9，1≤n≤10^6$

输入

The first line contains three integers: $a$, $b$, $n$ ($1 \leq a < b \leq 9$, $1 \leq n \leq 10^6$).

输出

Print a single integer — the answer to the problem modulo $1000000007$ ($10^9 + 7$).

样例

1 3 3

1

2 3 10

165