Migrated from Lutece 3251 繁星点点

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

求有多少个阶为 $n$ 的方阵 $[a_{ij}]$，满足至少有一行或者一列的元全部相等。

其中 $a_{ij}\in \{0,1,2\}$。答案对 $998244353$ 取模。

Input

一行，一个正整数，表示 $n$。

Output

Samples

2

63

Constraints

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

Note

$1\leq n\leq 10^6$

Resources

2024 UESTC ICPC Training for Math