You are given an integer $$$n$$$, and you need to construct an array $$$a$$$ of size $$$n$$$ satisfying:

• $$$1 \le a_i \le 2n$$$ for all $$$1 \le i \le n$$$.
• There are not two distinct indices $$$i$$$ and $$$j$$$ $$$(1 \le i,j \le n,$$$ $$$i \neq j)$$$ such that $$$a_i$$$ can be divided by $$$a_j$$$.

The Fibonacci sequence, where each number is the sum of the two preceding ones, is well-known in mathematics. Consider a sequence $$$a$$$ that follows a similar pattern but with subtraction instead of addition.

Given three integers $$$n$$$, $$$a_1$$$, and $$$a_2$$$. For $$$i \geq 3$$$, $$$a_i = a_{i-1} - a_{i-2}$$$.

Your task is to find

$$$$$$\sum_{i = 1}^{n} a_i \mod (10^9 + 7)$$$$$$

You are given two integers $$$k$$$, $$$n$$$ and a polynomial $$$P(x) = a_0+a_1x+a_2x^2+....+a_nx^n$$$.

Note

• $$$P^{1}(x) = P(x)$$$

• $$$P^{2}(x) = P(x)\cdot P(x)$$$

• $$$P^{3}(x)=P(x) \cdot P(x) \cdot P(x)$$$
• ...

• $$$P^i(x) = \underbrace{P(x) \cdot P(x) \cdot \dots \cdot P(x)}_{\text{i times}}$$$

Your task is to find the value of total sum of the coefficients of $$$P^k(x)$$$ modulo $$$(10^9 + 7)$$$.

There is an array $$$a$$$. Initially, $$$a = [0]$$$.

Assume that you can perform several operations. In the $$$i$$$-th operation, you can do exactly one of the following two operations:

• Set $$$a_1 := a_1 + 1$$$;
• Choose an index $$$j$$$ ($$$1 \leq j \leq |a|$$$), and insert the value $$$i$$$ after $$$a_j$$$.

You are given $$$q$$$ independent queries. For each query, you are given three integers $$$x$$$, $$$l$$$, and $$$r$$$ ($$$1 \leq$$$ $$$\boldsymbol{x \leq l}$$$ $$$\leq r$$$). Your task is to count the number of distinct arrays $$$a$$$ that satisfy the following conditions:

• $$$a_1 \leq x$$$;
• The number of operations performed is in the range $$$[l, r]$$$.

Since the answers may be large, you need to output them modulo $$$998\,244\,353$$$.

Given $$$a_1$$$ and $$$n$$$, find the number of sequences of positive integers $$$a_2, a_3, \dots, a_n$$$ that satisfy the following condition:

$$$$$$ \frac{\operatorname{lcm}(a_1, a_2, \ldots, a_n)}{\gcd(a_1, a_2, \ldots, a_n)} = a_1 $$$$$$

Here, $$$\gcd(a_1, a_2, \dots, a_n)$$$ denotes the greatest common divisor, which is the largest positive integer that divides each number in the sequence, and $$$\operatorname{lcm}(a_1, a_2, \dots, a_n)$$$ denotes the least common multiple, which is the smallest positive integer that is divisible by each number in the sequence.

Since the answer can be large, output it modulo $$$998\,244\,353$$$. It can be proven that the answer is finite.

You are given two polynomials $$$f(x) = Ax + B$$$ and $$$g(x) = Cx^n + Dx^{n-1}$$$. Your task is to find the minimum integer $$$k$$$, such that $$$g^{(k)}(x)$$$ is divisible by $$$f(x)$$$.

Here, $$$g^{(k)}(x)$$$ represents taking the derivative of $$$g(x)$$$ exactly $$$k$$$ times.

Formally,

• $$$g^{(0)}(x) = g(x)$$$,
• $$$g^{(k)}(x) = \frac{d}{dx} \left( g^{(k-1)}(x) \right)$$$ for $$$k \geq 1$$$,

and

• $$$\frac{d}{dx} \left( Ex^m + Fx^{m-1} \right) = mEx^{m-1} + (m-1)Fx^{m-2}$$$ for $$$m \gt 1$$$,
• $$$\frac{d}{dx} \left( Gx \right) = G$$$,
• $$$\frac{d}{dx} \left( G \right) = 0$$$,

where $$$E$$$, $$$F$$$, and $$$G$$$ are constants.

For example, for $$$g(x) = x^3 + 3x^2$$$, we can find that:

• $$$g^{(1)}(x) = 3x^2 + 6x$$$,
• $$$g^{(2)}(x) = 6x + 6$$$,
• $$$g^{(3)}(x) = 6$$$,
• $$$g^{(4)}(x) = 0$$$.

We say that a polynomial $$$P_1(x)$$$ is divisible by $$$P_2(x)$$$ if and only if there exists a polynomial $$$Q(x)$$$ such that $$$P_1(x) = Q(x)P_2(x)$$$, where the coefficients of $$$Q$$$ are integers.

You are given an array $$$a$$$ of length $$$n$$$. You can perform the following two operations any number of times, in any order:

1. Choose an index $$$i$$$ such that $$$a_i \gt 0$$$, and decrement $$$a_i$$$ by $$$1$$$. In other words, assign $$$a_i := a_i - 1$$$.
2. Select $$$k \geq 2$$$ distinct indices $$$i_1, i_2, \dots, i_k$$$ such that there exists at least one pair of indices $$$i_x$$$ and $$$i_y$$$ satisfying $$$a_{i_x} \neq a_{i_y}$$$. In other words, not all the values in the picked indices are the same. Then simultaneously set the values of all of $$$a_{i_1},a_{i_2},\dots,a_{i_k}$$$ to $$$(\max(a_{i_1}, a_{i_2}, \dots, a_{i_k})$$$ $$$- \min(a_{i_1}, a_{i_2}, \dots, a_{i_k}) - 1)$$$.

   For example, given $$$a = [1,0,1,9,1]$$$, choosing $$$a_1, a_3, a_4$$$ for operation $$$2$$$ results in $$$a=[7,0,7,7,1]$$$. However, choosing $$$a_1, a_3, a_5$$$ for operation $$$2$$$ is invalid, as their values are the same.

You want to choose a sequence of operations that maximizes the total number of operations. Find the maximum number of operations possible. Since the answer can be large, output it modulo $$$998\,244\,353$$$.