← 返回题目列表

Codeforces · 300/C

C. 美丽的数字

中文机器翻译题面 查看原题

维塔利是一个非常奇怪的人。他有两个最喜欢的数字a和b。如果一个正整数的十进制表示只包含数字 a 和 b,Vitaly 称该整数为好。如果一个好数字的数字之和是一个好数字,维塔利就称这个数字为优秀。

例如,假设 Vitaly 最喜欢的数字是 1 和 3,那么数字 12 就不好,数字 13 或 311 就可以。另外,111 号很优秀,而 11 号则不然。

现在维塔利想知道,有多少个长度恰好为 n 的优秀数。由于这个数字可能相当大,所以他要求你计算除以1000000007(109 + 7)后的余数。

数字的长度是其十进制表示形式中不带前导零的位数。

输入

第一行包含三个整数:a、b、n (1 ≤ a < b ≤ 9, 1 ≤ n ≤ 106)。

输出

打印一个整数——问题的答案以 1000000007 (109 + 7) 为模。

示例

输入 #1

1 3 3

输出 #1

1

输入 #2

2 3 10

输出 #2

165