题目描述

有一个 $3\times n$ 的网格。行从上到下编号为 $1,2,3$，列从左到右编号为 $1,2,\ldots,n$。

一种染色方案需要满足：

• 每一列恰好有一个黑格，其余两个格子为白格；
• 相邻两列的黑格不在同一行。

从所有满足条件的染色方案中等概率随机选择一种。若两个白格共用一条边，则可以在它们之间移动；能够通过若干次这样的移动互相到达的白格属于同一个连通块。

令随机变量 $X$ 表示最大白色连通块包含的格子数。求 $X$ 的期望。

输入格式

输入一行一个整数 $n$。

输出格式

输出期望对 $998244353$ 取模的结果。

具体而言，可以证明期望能够写成最简分数 $p/q$，且 $q$ 不被 $998244353$ 整除。输出唯一的整数 $x\in[0,998244353)$，满足

数据范围

对于所有测试数据，保证 $1\le n\le 500$。

子任务

样例 1

2

332748121

样例 1 说明

共有 $6$ 种合法染色方案。它们的最大白色连通块大小之和为 $20$，因此期望为 $20/6=10/3$；其模意义结果为 $332748121$。