维塔利是一个非常奇怪的人。他有两个最喜欢的数字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