Beautiful Numbers

Vitaly有一些奇怪的癖好，比如他特别爱两个小于10的数字a和b。Vitaly定义十进制表示下每一位都是a或b的数为“好数”，一个每一位数加起来为“好数”的“好数”被称为“极好的数”。 举个栗子=w=，如果偏爱数字为1和3，那么1212不是“好数”，13和311是“好数”，111是“极好的数”。 现在Vitaly想知道，长度为n（长度不包括前导0）的“极好的数”有多少个。对1e9+7取模。 $n \leq 10^6$

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) $ .

1 3 3

1

2 3 10

165