You are given a decimal fraction, that is, a number containing an integer part and a fractional part, in which both parts are written in the decimal number system. Unfortunately it may have a repeating decimal (fraction period) and working with fractions with repeating decimals is not very convenient.
A fraction with a repeating decimal is written in the format $$$a.b(c)$$$, which corresponds to $$$a.bccc\ldots$$$, where $$$c$$$ is repeated infinitely. For example, $$$1.25(13)$$$ represents the number $$$$$$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$$$$$$
Find the minimum positive base of the number system in which the same number is represented by a non-repeating fraction.
A number is represented as a non-repeating fraction in the number system with base $$$c$$$ if it can be represented as a finite sum $$$\sum\limits_{i} \frac{a_i}{c^i}$$$. In particular, we consider that for an integer the answer to the problem will be $$$c = 1$$$.
The first line of input contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ separated by a space — the number of digits in the integer part, non-repeating fractional part, and the repeating part, respectively ($$$1 \le n \le 12$$$; $$$0 \le m, k \le 12$$$).
The second, third, and fourth lines contain integers $$$a$$$, $$$b$$$, and $$$c$$$ — the integer part, fractional part, and period of the number, respectively ($$$0 \le a, b, c \le 10^{12}$$$).
Note that the representation of each part can be either an empty string or a number with leading zeros, as the number of occupied positions in the number is important ($$$1.01 \neq 1.1$$$).
Output a single integer — the minimum base of the number system in which the given number is represented without a repeating decimal. Print the answer by modulo $$$10^9 + 7$$$.
Points for each subtask are awarded only if all the tests of this subtask and the required subtasks are successfully passed.
| Subtask | Points | Constraints | Required Subtasks |
| 0 | – | examples from the statement | |
| 1 | 10 | $$$m = 0$$$, $$$k \le 1$$$ | |
| 2 | 10 | $$$m \le 1$$$, $$$k \le 1$$$ | 1 |
| 3 | 14 | $$$m \le 6$$$, $$$k = 0$$$ | |
| 4 | 16 | $$$m = 0$$$, $$$k \le 6$$$ | 1 |
| 5 | 23 | $$$m + k \le 12$$$ | 0 – 4 |
| 6 | 27 | $$$m, k \le 12$$$ | 0 – 5 |
2 1 0101
10
1 2 10250
2
1 0 115
3
In C++, to read a string until the end, you can use std::getline.
