E. Sky Full of Stars

Codeforces

IDCF998E

Time4000ms

Memory256MB

Difficulty—

combinatoricsmath

English · Original

Chinese · Translation

Formal · Original

On one of the planets of Solar system, in Atmosphere University, many students are fans of bingo game. It is well known that one month on this planet consists of $n^2$ days, so calendars, represented as square matrix $n$ by $n$ are extremely popular. Weather conditions are even more unusual. Due to the unique composition of the atmosphere, when interacting with sunlight, every day sky takes one of three colors: blue, green or red. To play the bingo, you need to observe the sky for one month — after each day, its cell is painted with the color of the sky in that day, that is, blue, green or red. At the end of the month, students examine the calendar. If at least one row or column contains only cells of one color, that month is called lucky. Let's call two colorings of calendar different, if at least one cell has different colors in them. It is easy to see that there are $3^{n \cdot n}$ different colorings. How much of them are lucky? Since this number can be quite large, print it modulo $998244353$. ## Input The first and only line of input contains a single integer $n$ ($1 \le n \le 1000\,000$) — the number of rows and columns in the calendar. ## Output Print one number — number of lucky colorings of the calendar modulo $998244353$ [samples] ## Note In the first sample any coloring is lucky, since the only column contains cells of only one color. In the second sample, there are a lot of lucky colorings, in particular, the following colorings are lucky: <center>![image](https://espresso.codeforces.com/0b3b95494fedde7de6c36a5ff89abcf1da16026a.png)</center>While these colorings are not lucky: <center>![image](https://espresso.codeforces.com/548e65dd41f7f774a35a4cf310a56d3ae4148e80.png)</center>

[{"iden":"statement","content":"在太阳系的某颗行星上，Atmosphere 大学的许多学生都是宾果游戏的粉丝。\n\n众所周知，这颗行星上一个月由 $n^2$ 天组成，因此以 $n \\times n$ 方阵形式表示的日历极为流行。\n\n天气条件更加异常。由于大气的独特成分，当与阳光相互作用时，每天的天空会呈现三种颜色之一：蓝色、绿色或红色。\n\n要玩宾果游戏，你需要观察一整个月的天空——每天结束后，将日历中对应单元格涂上当天天空的颜色，即蓝色、绿色或红色。\n\n月末时，学生们会检查日历。如果至少有一行或一列中的所有单元格颜色相同，则这个月被称为“幸运月”。\n\n我们称两种日历着色不同，当且仅当至少有一个单元格的颜色不同。容易看出，总共有 $3^{n \\cdot n}$ 种不同的着色方式。其中有多少种是“幸运”的？由于这个数字可能很大，请对 $998244353$ 取模输出。\n\n输入的第一行也是唯一一行包含一个整数 $n$（$1 \\leq n \\leq 1000000$）——表示日历的行数和列数。\n\n请输出一个数——日历的“幸运”着色方案数，对 $998244353$ 取模。\n\n在第一个样例中，任何着色都是幸运的，因为唯一的列中所有单元格颜色相同。\n\n在第二个样例中，存在大量幸运着色，例如以下着色是幸运的：\n\n而以下着色不是幸运的：\n\n"},{"iden":"input","content":"输入的第一行也是唯一一行包含一个整数 $n$（$1 \\leq n \\leq 1000000$）——表示日历的行数和列数。"},{"iden":"output","content":"请输出一个数——日历的“幸运”着色方案数，对 $998244353$ 取模"},{"iden":"examples","content":"输入1输出3输入2输出63输入3输出9933"},{"iden":"note","content":"在第一个样例中，任何着色都是幸运的，因为唯一的列中所有单元格颜色相同。在第二个样例中，存在大量幸运着色，例如以下着色是幸运的：而以下着色不是幸运的： "}]}

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the dimension of an $ n \times n $ grid. Each cell is colored with one of three colors: blue, green, or red. A coloring is *lucky* if at least one row or one column is monochromatic (all cells in that row/column have the same color). Let $ \mathcal{C} $ be the set of all possible colorings: $ |\mathcal{C}| = 3^{n^2} $. Let $ R_i $ be the set of colorings where row $ i $ is monochromatic, for $ i \in \{1, \dots, n\} $. Let $ C_j $ be the set of colorings where column $ j $ is monochromatic, for $ j \in \{1, \dots, n\} $. **Constraints** $ 1 \leq n \leq 10^6 $ **Objective** Compute the number of lucky colorings: $$ \left| \bigcup_{i=1}^n R_i \cup \bigcup_{j=1}^n C_j \right| \mod 998244353 $$

Samples

Input #1

Output #1

Input #2

Output #2

Input #3

Output #3

API Response (JSON)

{
  "problem": {
    "name": "E. Sky Full of Stars",
    "description": {
      "content": "On one of the planets of Solar system, in Atmosphere University, many students are fans of bingo game. It is well known that one month on this planet consists of $n^2$ days, so calendars, represented",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF998E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "On one of the planets of Solar system, in Atmosphere University, many students are fans of bingo game.\n\nIt is well known that one month on this planet consists of $n^2$ days, so calendars, represented...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "[{\"iden\":\"statement\",\"content\":\"在太阳系的某颗行星上，Atmosphere 大学的许多学生都是宾果游戏的粉丝。\\n\\n众所周知，这颗行星上一个月由 $n^2$ 天组成，因此以 $n \\\\times n$ 方阵形式表示的日历极为流行。\\n\\n天气条件更加异常。由于大气的独特成分，当与阳光相互作用时，每天的天空会呈现三种颜色之一：蓝色、绿色或红色。\\n\\n要玩宾果游戏，...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the dimension of an $ n \\times n $ grid.  \nEach cell is colored with one of three colors: blue, green, or red.  \nA coloring is *lucky* if at least one r...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments