对于给定的数字 $a$ , $b$ ,当整数 $n$ 在十进制下的所有数位都为 $a$ 或 $b$ 时，我们称 $n$ 是“好数”

对于好数 $n$ ，当 $n$ 在十进制下每一位的数字之和也为“好数”时，我们称 $n$ 是一个“完美数”

请你求出有多少 $m$ 位数是“完美数”

输入格式

输入一行三个整数 $a$ , $b$ , $m$ , 含义如题面所示 $(1 \leq m \leq 10^6 , 1 \leq a , b \leq 9)$。

输出格式

输出一行一个整数表示完美数的数量 ， 由于答案可能很大 ， 请你将答案对 $10^9 + 7$ 取模

样例输入

5 1 5

样例输出

1

样例解释

只有 $11111$ 满足要求