CF300C Beautiful Numbers

Vitaly 是一个非常奇怪的人。他有两个最喜欢的数字 $a$ 和 $b$。如果一个正整数的十进制表示只包含数字 $a$ 和 $b$，Vitaly 称这个数为“好数”。如果一个“好数”的各位数字之和也是“好数”，那么 Vitaly 称它为“优秀数”。 例如，假如 Vitaly 最喜欢的数字是 $1$ 和 $3$，那么数字 $12$ 不是好数，而数字 $13$ 或 $311$ 是好数。另外，$111$ 是优秀数，而 $11$ 不是。 现在 Vitaly 想知道，长度恰好为 $n$ 的优秀数有多少个。由于这个数字可能很大，请你计算它对 $1000000007$（$10^9 + 7$）取余后的结果。 一个数的长度是其十进制表示中不含前导零的数字个数。

第一行包含三个整数：$a$、$b$、$n$（$1 \leq a < b \leq 9,\,1 \leq n \leq 10^{6}$）。

输出一个整数，表示长度恰好为 $n$ 的优秀数个数，结果对 $1000000007$ ($10^9 + 7$) 取余。

由 ChatGPT 5 翻译