C. Sky Full of Stars

Codeforces

IDCF997C

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>

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

**Definitions** Let $ n \in \mathbb{Z}^+ $ with $ 1 \leq n \leq 10^6 $. Let $ C $ be the set of all colorings of an $ n \times n $ grid, where each cell is colored one of three colors: blue, green, or red. Thus, $ |C| = 3^{n^2} $. A coloring is **lucky** if at least one row or one column is monochromatic (i.e., all cells in that row/column have the same color). **Constraints** - Each cell independently takes one of 3 colors. - The total number of colorings is $ 3^{n^2} $. **Objective** Compute the number of lucky colorings modulo $ 998244353 $, i.e., $$ \left| \bigcup_{i=1}^n R_i \cup \bigcup_{j=1}^n C_j \right| \mod 998244353 $$ where: - $ R_i $ is the set of colorings where row $ i $ is monochromatic, - $ C_j $ is the set of colorings where column $ j $ is monochromatic. Use inclusion-exclusion over the $ 2n $ events ( $ n $ rows and $ n $ columns ).

Samples

Input #1

Output #1

Input #2

Output #2

Input #3

Output #3

API Response (JSON)

{
  "problem": {
    "name": "C. 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": "CF997C"
  },
  "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": "在太阳系的一颗行星上，大气大学的许多学生都是宾果游戏的粉丝。\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}^+ $ with $ 1 \\leq n \\leq 10^6 $.  \nLet $ C $ be the set of all colorings of an $ n \\times n $ grid, where each cell is colored one of three colors: blue, green...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments