思路与结论

• 等价条件：涂色有效当且仅当不存在蓝格子 $(i_b,j_b)$ 与红格子 $(i_r,j_r)$ 使得 $i_b\le i_r$ 且 $j_b\le j_r$。即不存在“蓝在红的左下”。

• 设红色集合的向下闭包（在坐标偏序下）为理想 $I$。每个有效涂色唯一对应到某个理想 $I$，并且：

  • $I$ 内不可为蓝；所有 $I$ 的极大元必须为红；其余（在 $I$ 内）可红/白；$I$ 外不可为红，可蓝/白。
  • 对固定 $I$ 的方案数为 $2^{n^{2}-m(I)}$，其中 $m(I)$ 是 $I$ 的极大元个数。

• 理想与从 $(0,0)$ 到 $(n,n)$ 的单调路径一一对应；$m(I)$ 等于该路径中“右转下（R→D）”拐角数 $k$。

• 含 $k$ 个 R→D 拐角的路径条数为 $\binom{n}{k}^{2}$。

• 因而总答案为

题目内容

给定一个由 $n+1$ 条横线、$n+1$ 条竖线构成的网格 (即划分成 $n×n$ 个单元格、$(n+1)×(n+1)$ 个格点)，我们使用 $(i,j)$ 表示网格中从上往下数第 $i$ 条直线和从左往右数第 $j$ 条直线交叉所在的格点，下标从 $0$ 开始。

每个单元格可以被染成蓝色、红色或白色中的一种颜色，故我们一共有 $3^{n×n}$ 种不同的涂色方案。

你从起点格点 $(0,0)$ 出发。假设当前格点为 $(x,y)$ ，你可以执行以下两种操作之一：

• 如果 $x<n$，沿竖线向下移动到格点 $(x +1,y)$ ；

• 如果 $y< n$ ，沿横线向右移动到格点 $(x,y+ 1)$ 。

当到达终点格点 $(n,n)$ 时，所经过的路径将网格中的单元格分为两部分：路径的左下方和右上方区域：

• 左下方区域：格点 $(0,0)、(n,0)、(n,n)$ 沿路径返回 $(0,0)$ 的区域；

• 右上方区域：格点 $(0,0)、(0,n)、(n,n)$ 沿路径返回 $(0,0)$ 的区域。

显然，一个单元格要么属于路径的左下方区域，要么属于路径的右上方区域。

定义：如果右上方区域不包含任何红色单元格且左下方区域不包含任何蓝色单元格，则称该路径为「良好路径」。如果对于某种涂色方案，存在至少一条「良好路径」，则认为该涂色方案是有效的。

在所有 $3^{n×n}$ 种涂色方案中，计算有效涂色方案的数量。由于答案可能很大，请将答案对 $998$ $244$ $353$ 取模后输出。

输入描述

输入共一行，包含一个整数 $n(1≤n≤5000)$ ，表示网格的大小。

输出描述

输出一个整数，表示有效涂色方案的数量对 $998$ $244$ $353$ 取模后的结果。

样例1

输入

1

输出

3

样例2

输入

2

输出

52

样例3

输入

3

输出

4032