该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

Constantine被武汉的天气整麻了,在迷糊之中有了一个idea.

题目描述

在一个 $n * n$的正方形点阵上,选取点构造两个正方形,要求如下:

• 正方形的顶点与点阵的点重合
• 正方形的边水平或竖直
• 两个正方形有且仅有一个公共点,且公共点为两个正方形的顶点
• 两个正方形没有相邻的边

请问对于一个 $n * n$ 的点阵,有多少种符合上述条件的构造方案,由于答案可能很大,请对 $998244353$ 取模后输出.

为明确题意,有以下几个例子:

由于两个正方形存在相邻边,所以这种构造是非法的.

由于两个正方形存在相邻边,所以这种构造是非法的.

由于蓝色正方形的边不满足水平或者竖直,所以这种构造是非法的

这个构造方式是合法的.

对于 $n = 3$ 的情况,我们有以下 $2$ 种合法构造方案

输入格式

一行,一个整数 $n$.

输出格式

一行,一个整数,代表合法方案数.

样例 #1

样例输入 #1

3

样例输出 #1

2

样例 #2

样例输入 #2

4

样例输出 #2

12

提示

对于 $20\%$ 的数据,$n\le 1e3$

对于 $60\%$ 的数据,$n\le 1e6$

对于 $100\%$ 的数据,$n\le 1e9$