Description

可以证明，$\sqrt{2}+1$ 的任意次幂都可以写成 $m\sqrt{2}+n$ 的形式，现在你需要计算出 $(\sqrt{2}+1)^k$ 的 $n$ 的值。

由于答案可能很大，因此你的答案对$998244353$取模

Format

Input

一个整数$k(0\le k\le 10^7)$ 。

Output

一个整数$n$，为正确答案对$998244353$取模的值。

Samples

3

7