← 返回题目列表

Codeforces · 997/C

C. 满天繁星

中文机器翻译题面 查看原题

在太阳系的一颗行星上,大气大学里,许多学生都是宾果游戏的爱好者。

众所周知,这个星球上的一个月由 $$$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

注意

在第一个示例中,任何颜色都是幸运的,因为唯一的列仅包含一种颜色的单元格。

在第二个样本中,有很多幸运着色,特别是以下幸运着色:

虽然这些颜色并不幸运: