Description

n×n的01矩阵，你需要找到满足每一行和每一列的1的个数都是2的矩阵的个数。

设对于n的答案为fn，你需要输出的是∑=fi(1<=i<=n)对998244353取模。

Format

Input

一行一个整数n,n ≤ 10^7

Output

一行一个整数表示答案

Samples

2

1