Jiutiao Keli is a girl who loves playing Mahjong. Therefore, she has created a Mahjong-related problem, hoping that this problem will not make your passion for Mahjong disappear completely.

Today, Keli wants to play Mahjong, but her friends have all gone to play Auto Chess, so Keli has to play by herself. Keli found a special set of Mahjong tiles, which has $n$ ($n \ge 5$) different types of tiles, with sizes ranging from 1 to $n$, and there are 4 tiles of each type.

A "meld" (面子) is defined as three tiles of the same size or three tiles of consecutive sizes, i.e., sizes like $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 size, i.e., sizes like $i, i$ ($1 \le i \le n$).

A set of Mahjong tiles $S$ is considered "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 sets $S_1$ to $S_5$, where $S_1$ is a pair and $S_2$ through $S_5$ are melds. $S$ can be partitioned into seven sets $S_1$ to $S_7$, all of which are pairs, and their corresponding sizes are all distinct.

For example, the following sets are winning (only sizes are marked 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 sets are 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\}$

Keli first draws 13 tiles and shuffles the remaining $4n - 13$ tiles randomly. The shuffling is uniformly random, meaning all $(4n - 13)!$ permutations are equally likely to occur.

For a permutation $P$, Keli defines $S_i$ as the set consisting of the 13 tiles Keli initially drew plus the first $i$ tiles from $P$. The weight of $P$ is defined as the minimum $i$ such that $S_i$ contains a winning subset. If you are familiar with Mahjong, it is not hard to see that the weight of $P$ is the theoretical number of turns until the earliest win. Note that when $n \ge 5$, $S_{4n-13}$ always contains a winning subset, so the weight of $P$ is well-defined.

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

Input

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

The next 13 lines each contain two integers $w, t$ ($1 \le w \le n, 1 \le t \le 4$), representing that the $i$-th tile Keli initially drew is the $t$-th tile of size $w$. It is guaranteed that all $(w, t)$ pairs are distinct.

Output

Output a single integer representing the answer modulo 998244353. That is, if the simplest fractional representation of the answer is $\frac{x}{y}$ ($x \ge 0, y \ge 1, \gcd(x, y) = 1$), you need to output $x \times y^{-1} \pmod{998244353}$.

Examples

Input 1

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

Output 1

1

Note 1

The hand pattern above is called "Pure Nine Gates" (纯正九莲宝灯). It is not hard to see that no matter what tile is added, it is a winning hand. Therefore, for all permutations $P$, the weight is 1, so the expected value of the weight is 1.

Constraints

• For 20% of the data, $n = 5$.
• For 50% of the data, $n \le 13$.
• For another 20% of the data, $n \le 100, w_i = i, t_i = 1$.
• For another 20% of the data, $n \le 100, w_i = \lceil \frac{i}{4} \rceil, t_i = i \pmod 4 + 1$.
• For 100% of the data, $5 \le n \le 100$.