用三元组 $(a,d,n)$ 表示长度为 $n$ 的递增等差正整数序列 $\{a, a+d, a+2d \ldots a+(n-1)d\}$。给定 $(a,d,n)$，要求构造 $(b,e,n)$ 满足：

• $b,e < 2^{64}$，且是正整数
• 对于所有 $0 \leq i < n$，$a+id$ 的十进制表示是 $F_{b+ie}$ 的十进制表示的后 $18$ 位的子串（如果没有 $18$ 位自动补前导零）。其中 $F_i$ 是指斐波那契数列的第 $i$ 项。

$1 \leq a+(n-1)d \leq 10^6$。

题解

设 $P = 10^6$，则有 $\pi(P) \mid 6P$，尝试得取 $n = 3P$ 是 $\bmod P$ 意义下的周期。

则有 $F_{n} \equiv 0 \pmod P$，$F_{n+1} \equiv 1 \pmod P$。考虑：

• $F_{2n+1} \equiv F_n^2 + F_{n+1}^2 \equiv F_{n+1}^2 \pmod {P^2}$
• $F_{3n+1} \equiv F_n F_{2n} + F_{n+1} F_{2n+1} \equiv F_{n+1}^3 \pmod {P^2}$
• $\ldots$
• $F_{kn+1} \equiv F_{n+1}^k \pmod {P^2}$

此例中，我们有 $F_{n+1} \equiv 2 t P + 1 \pmod P^2$，其中 $t$ 是与 $P$ 互质的整数。

则 $F_{kn+1} \equiv F_{n+1}^k \equiv 2kt P + 1$，取 $k = 5 k' t^{-1}$，则枚举 $1 \leq k' < 10^6$ 即可解决本题。

代码

def exgcd(a, b):
    if b == 0:
        return 1, 0
    x, y = exgcd(b, a % b)
    return y, x - y * (a // b)


def inv(a, p):
    x, y = exgcd(a, p)
    return (x % p + p) % p


def xmul(a, b):
    c = [[0, 0], [0, 0]]
    for i in range(0, 2):
        for j in range(0, 2):
            for k in range(0, 2):
                c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % (10**12)
    return c


def xpow(a, b):
    s = [[1, 0], [0, 1]]
    while b:
        if b % 2:
            s = xmul(s, a)
        a = xmul(a, a)
        b //= 2
    return s


def fib(n):
    if n <= 1:
        return n
    return xmul([[1, 0], [0, 0]], xpow([[1, 1], [1, 0]], n - 1))[0][0]


if __name__ == "__main__":
    t = fib(3 * (10**6) + 1) // (10**6)
    u = 15 * inv(t // 2, 10**6)
    n, a, d = map(int, input().split())
    b = a * u * (10**6) + 1
    e = d * u * (10**6)
    print(b, e)