对于给定的数字 $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$ 满足要求