CF997C Sky Full of Stars

在太阳系的某个星球上，大气大学的许多学生都是宾果游戏的爱好者。 众所周知，这个星球上的一个月有 $n^2$ 天，因此以 $n \times n$ 的方阵形式表示的日历非常流行。 这里的天气条件也非常奇特。由于大气成分的独特性，每天与阳光相互作用后，天空会呈现三种颜色之一：蓝色、绿色或红色。 为了玩宾果游戏，你需要观察天空一个月——每一天结束后，将当天的天空颜色涂在日历的对应格子上，即蓝色、绿色或红色。 在月底，学生们会检查日历。如果至少有一行或一列的所有格子颜色都相同，那么这个月就被称为“幸运月”。 我们称两种日历的涂色不同，当且仅当至少有一个格子的颜色不同。显然，总共有 $3^{n \cdot n}$ 种不同的涂色方式。请问有多少种涂色方式是幸运的？由于答案可能很大，请输出对 $998244353$ 取模后的结果。

输入的第一行包含一个整数 $n$（$1 \le n \le 1000000$），表示日历的行数和列数。

输出一个整数，表示幸运涂色方式的数量，对 $998244353$ 取模。

在第一个样例中，任何一种涂色方式都是幸运的，因为唯一的一列中的所有格子颜色必然相同。 在第二个样例中，有很多幸运的涂色方式，特别是如下的涂色方式是幸运的：  而如下的涂色方式不是幸运的：  由 ChatGPT 4.1 翻译