Sky Full of Stars
Contest: Codeforces Round 493 (Div. 1)
Difficulty rating: 2500
Tags: combinatorics, math

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 format:
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 format:
Print one number — number of lucky colorings of the calendar modulo $$$998244353$$$

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

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:

While these colorings are not lucky:

Example input:
1

Example output:
3

Example input:
2

Example output:
63

Editorial:
Let $$$A_i$$$ be the set of all colorings, where $$$i$$$-th line contains only one color, and $$$B_i$$$ be the set of colorings, where $$$i$$$-th column contains only one color.
This way, you need to calculate $$$|A_1 \cup A_2 \ldots A_n \cup B_1 \cup B_2 \ldots B_n|$$$.
As usual, we can use inclusion-exclusion formula to reduce the calculation of multiplications to calculation all possible intersections of sets above.
More over, due to the obvious symmetry, to calculate the size of intersection of some set of $$$A_i$$$ and $$$B_i$$$ it is not important to know exact indices — only number of taken $$$A$$$-s and number of $$$B$$$-s.
This way $$$ans = \sum_{i=0 \ldots n, j=0 \ldots n, i + j > 0} C_n^i C_n^j (-1)^{i + j + 1} f(i, j)$$$
Where $$$f(i, j)$$$ — is the number of colorings, where first $$$i$$$ rows and first $$$j$$$ columns are onecolored.
It turns out, that formula for $$$f$$$ differs significantly depending on presence of zero in it's arguments.
Let's examine the case where zero is present, the $$$f(0, k) = 3^k \cdot 3^{n (n - k)}$$$.
Indeed, you should choose one color in each of the first $$$k$$$ columns, and the rest should be painted in any way.
——
If both arguments are $$$> 0$$$, that is, there is at least one one-colored column and at least one-colored row, than we can notice, that all one-colored rows and columns are in fact of one color.
This way, $$$f(i, j) = 3 \cdot 3^{(n - i)(n - j)}$$$
Since we should first select the globally common color, and then paint all the rest in any way.
Summation of all $$$f$$$-s gives solution with $$$\mathcal{O}(n^2)$$$ or $$$\mathcal{O}(n^2 \log)$$$ complexity, depending on implementation.
But we need to go faster.
—–
Let's sum all summands with $$$i = 0$$$ or $$$j = 0$$$ in a stupid way, in $$$\mathcal{O}(n)$$$.
Then examine all other summands. We have a formula:
$$$ans = \sum_{i=1}^{n} \sum_{j=1}^{n} C_n^i C_n^j (-1)^{i + j + 1} 3 \cdot 3^{(n - i)(n - j)}$$$
Let's replace our variables: $$$i \to n - i$$$, $$$j \to n - j$$$.
$$$ans = 3 \sum_{i=0}^{n - 1} \sum_{j = 0}^{n - 1} C_n^{n - i} C_n^{n - j} (-1)^{n - i + n - j + 1} \cdot 3^{ij}$$$
Since $$$C_n^{n - i} = C_n^i$$$, $$$(-1)^{2n} = 1$$$, $$$(-1)^{-i} = (-1)^{i}$$$ we have
$$$ans = 3 \sum_{i=0}^{n - 1} \sum_{j = 0}^{n - 1} C_n^i C_n^j (-1)^{i + j + 1} \cdot 3^{ij}$$$
Note, that $$$(a + b)^n = \sum_{i = 0}^{n} C_n^i a^i b^{n - i}$$$.
Using this, we can collect all summands for fixed $$$i$$$, however with fixed $$$i$$$ we have not $$$n$$$ summands, but $$$n - 1$$$. We can workaround it by adding and removing the missing summand.
—–
Let's go:
$$$ans = 3 \sum_{i=0}^{n - 1} \sum_{j = 0}^{n - 1} C_n^i C_n^j (-1)^{i + j + 1} \cdot 3^{ij}$$$
$$$ans = 3 \sum_{i=0}^{n - 1} C_n^i (-1)^{i+1} \sum_{j = 0}^{n - 1} C_n^j (-1)^{j} \cdot (3^i)^j$$$
$$$ans = 3 \sum_{i=0}^{n - 1} C_n^i (-1)^{i+1} \sum_{j = 0}^{n - 1} C_n^j (- 3^i)^j$$$
$$$ans = 3 \sum_{i=0}^{n - 1} C_n^i (-1)^{i+1} [(1 + (-3^i))^n - (-3^i)^n]$$$
—–
This formula has only $$$\mathcal{O}(n)$$$ summands, аnd hence can be evaluated fast enough.
To calculate powers of number fast, we can use binary pow method.