题目描述

Vitaly 有一些奇怪的癖好，比如他特别爱两个小于 $10$ 的数字 $a$ 和 $b$。Vitaly 定义十进制表示下每一位都是 $a$ 或 $b$ 的数为好数，一个每一位数加起来为好数的好数被称为极好的数。

举个栗子，如果偏爱数字为 $1$ 和 $3$，那么 $1212$ 不是好数，$13$ 和 $311$ 是好数，$111$ 是极好的数。

现在 Vitaly 想知道，长度为 $n$（长度不包括前导 $0$）的极好的数有多少个，对 $10^9+7$ 取模。

输入格式

一行三个整数 $a,b,n$，$1\le a<b\le 9$，$1\le n\le 10^6$。

输出格式

输出一个整数表示答案，对 $10^9+7$ 取模。

1 3 3

1

2 3 10

165