Description

Jiutiao Kelian is a girl who loves playing Mahjong. So she made a Mahjong-related problem, hoping this problem will not make your love for Mahjong disappear completely.

Today, Kelian wants to play Mahjong, but all her friends went to play Auto Chess, so Kelian can only play alone. Kelian found a special Mahjong set. It has $n(n\ge 5)$ different tile values, with values from $1$ to $n$. For each value, there are $4$ tiles.

A meld is defined as three tiles that are either all the same value or consecutive values, i.e., with values of the form $i,i,i(1 \le i \le n)$ or $i,i+1,i+2(1\le i\le n-2)$. A pair is defined as two tiles of the same value, i.e., with values of the form $i,i(1 \le i \le n)$.

A multiset of Mahjong tiles $S$ is said to be winning if and only if its size is $14$ and it satisfies at least one of the following two conditions:

• $S$ can be partitioned into five multisets $S_1$ to $S_5$, where $S_1$ is a pair, and $S_2$ to $S_5$ are melds.
• $S$ can be partitioned into seven multisets $S_1$ to $S_7$, all of which are pairs, and their corresponding values are pairwise distinct.

For example, the following multisets are all winning (only the values are shown here):

• $\{1,1,1,1,2,3,4,5,6,7,8,9,9,9\}$
• $\{1,1,2,2,4,4,5,5,6,6,7,7,8,8\}$
• $\{1,1,2,2,3,3,4,4,5,5,6,6,7,7\}$

And the following multisets are all not winning:

• $\{1,1,1,2,3,4,5,6,7,8,9,9,9\}$
• $\{1,1,1,1,4,4,5,5,6,6,7,7,8,8\}$
• $\{1,1,1,2,3,4,5,6,7,8,9,9,9,11\}$

Kelian first draws $13$ tiles, and then randomly shuffles the remaining $4n-13$ tiles. The shuffling is uniformly random, i.e., all $(4n-13)!$ permutations occur with equal probability.

For a permutation $P$, Kelian defines $S_i$ as the multiset formed by the $13$ tiles she drew in advance plus the first $i$ tiles in $P$. The weight of $P$ is defined as the minimum $i$ such that $S_i$ has a subset that is winning. If you are familiar with Mahjong, it is not hard to see that the weight of $P$ is the earliest theoretical turn to win. Note that when $n\ge 5$, $S_{4n-13}$ always has a winning subset, so the weight of $P$ is well-defined.

Now Kelian wants to train her tile efficiency, so she hopes you can first compute the expected value of the weight of $P$.

Input Format

The first line contains an integer $n$, indicating the number of different tile values in this special Mahjong set.

Then follow $13$ lines, each containing two integers $w,t(1 \le w \le n,1 \le t \le 4)$, indicating that the $i$-th tile Kelian initially drew is the $t$-th tile of value $w$. It is guaranteed that the pairs $(w,t)$ are pairwise distinct.

Output Format

Output one line containing one integer, indicating the answer modulo $998244353$. That is, if the answer in lowest terms is $\frac{x}{y}(x \ge 0,y \ge 1,gcd(x,y) = 1)$, you need to output $x\times y^{-1}\ \mathrm{mod}\: 998244353$.

9
1 1
1 2
1 3
2 1
3 1
4 1
5 1
6 1
7 1
8 1
9 1
9 2
9 3

1

Hint

The above hand type is called Pure Nine Gates. It is not hard to see that no matter what tile you add, it is winning. Therefore, for all permutations $P$, the weight is $1$, so the expected weight is $1$.

For $20\%$ of the testdata, $n = 5$.

For $50\%$ of the testdata, $n\le 13$.

For another $20\%$ of the testdata, $n \le 100,w_i = i,t_i = 1$.

For another $20\%$ of the testdata, $n \le 100,w_i = \lceil \frac{i}{4} \rceil ,t_i= i\ \mathrm{mod}\ 4 + 1$.

For $100\%$ of the testdata, $5 \le n \le 100$.

Translated by ChatGPT 5