Problem Statement

Output the remainder when $(a^2-398)^{2^n}$ is divided by $M$.

...Oops, for various reasons, $a$ and $M$ will not be given in the input. $a$ is determined in advance, but you may choose $M$ as you like. However, $M$ must be an integer satisfying $10^7 \le M \le 10^{18}$.

Note that exponentiation is evaluated from the top. That is, $x^{y^z} = x^{(y^z)}$ (it is not $(x^y)^z$).

Input

$n$

[Constraints]

• $a,\ n$ are integers
• $20\le a\le 5000$
• $100\le n \le 10^9$

Output

$M$
$ans$

On line $1$, output $M$. $M$ must be an integer satisfying $10^7 \le M \le 10^{18}$.
On line $2$, output the answer $ans$ to the problem, that is, the remainder when $(a^2-398)^{2^n}$ is divided by $M$.
Print a newline at the end.

For the $a$ determined in advance for each test case and the $M$ given on line $1$ of the output, you get AC if the remainder when $(a^2-398)^{2^n}$ is divided by $M$ matches the $ans$ given on line $2$ of the output.

Sample

1

998244353
4