A9046 | Beautiful Numbers

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 favourite digits are $1$ and $3$ , then number $12$ isn't good and numbers $13$ or $311$ are. Also, number $111$ is excellent and 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.

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

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