C. Прекрасные числа
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Виталий очень странный человек. У него есть две любимые цифры a и b. Виталий называет целое положительное число хорошим, если в десятичной записи этого числа используются только цифры a и b. Виталий называет хорошее число замечательным, если сумма его цифр является хорошим числом.

Например, пусть у Виталия любимые цифры 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 3 3
Выходные данные
1
Входные данные
2 3 10
Выходные данные
165