East 2 Will Not Come to This Match! 9

This problem is identical to Problem 1 with the same title, except for the tile types and counts, the number of tiles in the wall, and the modulus of the answer.

Mahjong+ is a game where you collect 14 tiles to build a dragon. To build a dragon, you need to know about tiles, heads, and bodies.

• Tile (牌): Mahjong+ has 100,000 copies of each tile, and each tile shows a number from 1 to $10\,000$ inclusive.
• Head: A combination of 2 tiles with the same number (e.g. ).
• Body: A combination of 3 tiles with consecutive numbers that differ by 1 (e.g. ), or 3 tiles with the same number (e.g. ). The order of the tiles does not matter.

The following table shows examples of what is and is not a head or body.

To build a dragon, you need 14 tiles arranged either as 1 head and 4 bodies, or as 7 different heads.

The following table shows examples of dragons and non-dragons.

• The same tile cannot belong to two or more heads or bodies at the same time. | | : Dragon | | - A dragon with head $(5,5)$ and bodies $(1,2,3) ;(1,2,3) ;(7,8,9) ;(7,8,9)$.

• It can also be seen as a dragon with 7 different heads $(1,1) ;(2,2) ;(3,3) ;(5,5) ;(7,7) ;(8,8) ;(9,9)$. | | : Not a dragon | | * Making 7 heads requires two duplicate heads $(1,1)$, so it cannot have 7 heads.

• No way to split these tiles gives 1 head and 4 bodies. |

The wall holds $N$ tiles, and the $i$-th tile shows $A_i$. You want to know how many ways there are to draw 14 tiles from the wall and build a dragon.

The first line contains the number of tiles $N$ in the wall. $(14\le N\le 100\,000)$

The second line contains $A_1,A_2,\cdots ,A_N$, separated by spaces. $(1\le A_i\le 10\,000)$

Print the number of ways to draw 14 tiles from the wall and build a dragon, modulo $998\,244\,353$ $(=119 \times 2^{23}+1)$. $998\,244\,353$ is prime.

• Two draws with the same tile numbers still count as different cases if the tiles came from different positions.
• If 14 tiles can form a dragon in several ways, it still counts as one case.