B. Fraction Conversion
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана десятичная дробь, то есть число, содержащее целую часть и дробную часть, в котором обе части записаны в десятичной системе счисления. К сожалению, в ней может быть период, а работать с дробями с периодами не очень удобно.

Дробь с периодом записывается в формате $$$a.b(c)$$$, что соответствует $$$a.bccc\ldots$$$, где $$$c$$$ повторяется бесконечное число раз. Например, $$$1.25(13)$$$ задает число $$$$$$1 + \tfrac{2}{10} + \tfrac{5}{10^2} + \tfrac{1}{10^3} + \tfrac{3}{10^4} + \tfrac{1}{10^5} + \tfrac{3}{10^6} + \ldots$$$$$$

Найдите минимальное положительное основание системы счисления, в которой то же самое число задается непериодичной дробью.

Число представляется в виде непериодичной дроби в системе счисления с основанием $$$c$$$, если оно представимо в виде конечной суммы $$$\sum\limits_{i} \frac{a_i}{c^i}$$$. В частности, мы считаем, что для целого числа ответом на задачу будет $$$c = 1$$$.

Входные данные

В первой строке ввода через пробел перечислены три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ — количество цифр в целой части, непериодичной дробной части и в периоде, соответственно ($$$1 \le n \le 12$$$; $$$0 \le m, k \le 12$$$).

Во второй, третьей и четвертой строках даны целые числа $$$a$$$, $$$b$$$ и $$$c$$$ — целая часть, дробная часть и период числа, соответственно ($$$0 \le a, b, c \le 10^{12}$$$).

Обратите внимание, что запись каждой из частей может быть как пустой строкой, так и числом с ведущими нулями, так как количество занимаемых позиций в числе имеет значение ($$$1.01 \neq 1.1$$$).

Выходные данные

Выведите единственное целое число — минимальное основание системы счисления, в которой данное число записывается без периода. Выведите ответ по модулю $$$10^9 + 7$$$.

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.

ПодзадачаБаллыОграниченияНеобходимые подзадачи
0–примеры из условия
110$$$m = 0$$$, $$$k \le 1$$$
210$$$m \le 1$$$, $$$k \le 1$$$1
314$$$m \le 6$$$, $$$k = 0$$$
416$$$m = 0$$$, $$$k \le 6$$$1
523$$$m + k \le 12$$$0 – 4
627$$$m, k \le 12$$$0 – 5
Примеры
Входные данные
2 1 0
10
1

Выходные данные
10
Входные данные
1 2 1
0
25
0
Выходные данные
2
Входные данные
1 0 1
1

5
Выходные данные
3
Примечание

В C++ для считывания строки до конца можно использовать std::getline.