#P5481. 矩阵

    ID: 4484 传统题 2000ms 512MiB 尝试: 49 已通过: 28 难度: 7 上传者: 标签>CF2300提高+/省选-二分图建模重复元素除重指数生成函数导数积分转化递推计数滚动数组

矩阵

Description

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

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

Format

Input

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

Output

一行一个整数表示答案

Samples

2
1