4435. and I am home(数据加强)

【题目背景】

来吧 相视而笑吧

单纯天真的脸庞

拥抱着混乱不堪的思念

就连迷路的地点 都无比温柔

无论几次都会呼喊你的名字

就算面对不可确定的未来

只要想起那些不愿放手的东西就会心痛

我就在这里哦

我就在这里哦

你的归所不是就在这里哟?

无论何时都不会改变

留下永恒的思念

【题目描述】

Kyouko 想要找到回家的路，但是走了太远，她也失去了最后一点方向。

Kyouko 的家在一个二维平面上，网格上的坐标用整数对 $(i,j)$ 表示。她的移动则可以视为随机游走，她从 $(0,0)$ 出发，共移动了 $n$ 步，当她位于坐标 $(i,j)$ 时，她会随机选择移动到 $(i-1,j),(i+1,j),(i,j-1),(i,j+1)$ 这些位置之一，她选择任何一个方向的概率均为 $\frac{1}{4}$。

为了找回残存的记忆，Kyouko 希望你告诉她游走过程中访问过的单元格的期望数量（同一个单元格访问多次算作一次）。设 $E$ 为随机游走过程中访问过的单元格的期望数量。计算 $E \times 4^n$ 对 $998244353$ 取模的结果（该值保证为整数）。注意，$(0,0)$ 始终视为被访问过。

【输入格式】

一行一个正整数 $n$。

【输出格式】

一行一个整数，表示答案。

【样例输入 1】

2

【样例输出 1】

44

【样例输入 2】

10

【样例输出 2】

8264208

【样例输入 3】

50

【样例输出 3】

310724701

【样例输入 4】

1000

【样例输出 4】

168286304

【样例输入 5】

100000

【样例输出 5】

328125651

【样例输入 6】

444976

【样例输出 6】

850295589

【样例说明】

对于样例 $1$：共有 $16$ 种游走的方法。

其中，有 $4$ 种游走方法返回 $(0,0)$，每种方法经过 $2$ 个格子。

剩余的 $12$ 种游走方法，每种均经过 $3$ 个格子。

答案为 $2\times 4+3\times 12=44$。

【数据规模与约定】

对于 $20\%$ 的数据，满足 $n\le 10$。

对于 $30\%$ 的数据，满足 $n\le 20$。

对于 $40\%$ 的数据，满足 $n\le 50$。

对于 $50\%$ 的数据，满足 $n\le 100$。

对于 $60\%$ 的数据，满足 $n\le 500$。

对于 $70\%$ 的数据，满足 $n\le 1000$。

对于 $90\%$ 的数据，满足 $n\le 10^5$。

对于 $100\%$ 的数据，满足 $n\le 5\times 10^5$。

本题相比于原题增加了 $n\ge 10^5$ 部分的数据。

【来源】

？？？。

样例里面有小彩蛋（