Not East Two in This Match! 1

Time limit1sMemory limit1024 MB

Summary

Count the ways to pick 14 of the N drawn tiles that split into 1 pair and 4 sets, or into 7 distinct pairs.

Rules

Mahjong is a game where you collect $14$ tiles to make a dragon. To make a dragon, you need to understand tiles, pairs, and sets.

Tile: Mahjong has $4$ tiles for each number from $1$ to $9$ .
Pair: Two tiles with the same number.
Set: Three tiles with consecutive numbers that differ by $1$ , or three tiles with the same number. The order of the tiles does not matter.

The table below shows which combinations are pairs or sets and which are not.

Example	Type	Explanation
	-	A single tile cannot be a pair or a set.
	Pair	Two tiles with the same number form a pair.
	Set	$7$ , $8$ , $9$ are consecutive numbers that differ by $1$ , so these three tiles form a set.
	-	$1$ , $3$ , $5$ are not consecutive numbers that differ by $1$ , so these three tiles are not a set.
	-	$9$ and $1$ are not consecutive numbers.
	Set	Three tiles with the same number form a set.
	-	$4$ , $4$ , $5$ are not consecutive numbers that differ by $1$ , so these three tiles are not a set.
	-	Four tiles cannot be a pair or a set.

To make a dragon, you must arrange $14$ tiles into $1$ pair and $4$ sets, or into $7$ different pairs.

The examples below show a dragon and a non-dragon.

Example
Dragon: Pair $(3,3)$ and sets $(4,4,4)$ , $(5,6,7)$ , $(6,7,8)$ , $(7,8,9)$ .
Not a dragon: No way to split these tiles into $1$ pair and $4$ sets, or into $7$ pairs. The same tile cannot belong to two or more pairs or sets at the same time.
Dragon: Pair $(5,5)$ and sets $(1,2,3)$ , $(1,2,3)$ , $(7,8,9)$ , $(7,8,9)$ . It can also be read as $7$ different pairs $(1,1)$ , $(2,2)$ , $(3,3)$ , $(5,5)$ , $(7,7)$ , $(8,8)$ , $(9,9)$ .
Not a dragon: Making $7$ pairs requires two copies of the pair $(1,1)$ , so this cannot be a dragon with $7$ pairs. It also cannot be split into $1$ pair and $4$ sets.

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

The second line contains $A_1, A_2, \cdots, A_N$ separated by spaces. $(1 \le A_i \le 9)$ No tile type appears more than $4$ times.

Print the number of ways to draw $14$ tiles from the wall so that they form a dragon.

Two draws that produce the same numbers but use tiles at different positions are counted as different ways.
If a set of $14$ tiles can form a dragon in several ways, it is counted once.

Example 2

Input

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

Expected output

445632532