在太阳系的一颗行星上,大气大学里,许多学生都是宾果游戏的爱好者。
众所周知,这个星球上的一个月由 $$$n^2$$$ 天组成,因此由 $$$n$$$ 表示为方阵 $$$n$$$ 的日历非常受欢迎。
天气状况更加不寻常。由于大气的独特组成,当与阳光相互作用时,每天的天空呈现三种颜色之一:蓝色、绿色或红色。
要玩宾果游戏,您需要观察天空一个月——每天之后,其单元格都会涂上当天天空的颜色,即蓝色、绿色或红色。
月底,学生检查日历。如果至少一行或一列仅包含一种颜色的单元格,则该月称为幸运月。
如果至少一个单元格具有不同的颜色,我们可以将日历的两种颜色称为不同的颜色。很容易看出有 $$$3^{n \cdot n}$$$ 不同的颜色。他们中有多少人是幸运的?由于这个数字可能相当大,因此打印它对 $$$998244353$$$ 取模。
输入
输入的第一行也是唯一一行包含一个整数 $$$n$$$ ($$$1 \le n \le 1000\,000$$$) — 日历中的行数和列数。
输出
打印一个数字 — 日历的幸运颜色数以 $$$998244353$$$ 为模
示例
输入 #1
1
输出 #1
3
输入 #2
2
输出 #2
63
输入 #3
3
输出 #3
9933
注意
在第一个示例中,任何颜色都是幸运的,因为唯一的列仅包含一种颜色的单元格。
在第二个样本中,有很多幸运着色,特别是以下幸运着色:
虽然这些颜色并不幸运: