7. Split into Triplets
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

As usual, Masha recieved an array $$$a$$$ consisting of $$$n$$$ positive integers for her birthday. Every number in the array is greater or equal to $$$1$$$ and less or equal to $$$m$$$. Masha is fond of the number three, so the length of the array is divisble by three.

Masha decided to combine the numbers into triplets: each triplet must be formed of either three equal numbers or three consecutive numbers. In other words, each triplet looks like $$$(x, x, x)$$$ or $$$(x, x+1, x+2)$$$, where $$$x$$$ is an arbitrary positive integer.

Masha wants to play with the gifted array, and she wants to know the number of ways to split the numbers of the array into such triplets. Two ways of splitting are considered distinct if it is not possible to find a one-one mapping between the triplets of the first splitting and the triplets of the second splitting in the way that the number in the corresponding triplets are equal to each other. Since the number of ways to split the array can be large, Masha only wishes to know it modulo $$$10^9+7$$$.

Please help Masha count the number of ways to split the numbers of the gifted array into triplets (modulo $$$10^9+7$$$).

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 5000$$$, $$$1 \le m \le 5000$$$, $$$n=3\cdot k$$$ for some integer $$$k$$$).

The second line contains $$$n$$$ integers $$$a_i$$$ — the numbers of the array ($$$1 \le a_i \le m$$$).

Output

In a single line output one number — the number of ways to split the numbers of the array into triplets modulo $$$10^9+7$$$.

Scoring

The points for each subtask are earned only if all tests passed for that subtask and all required subtasks.

|c|c|}

Subtask

Points Additional constraints Required subtasks Information about testing
110 $$$m \le 3$$$first error
28 $$$m \le 4$$$1first error
310 each number from $$$1$$$ to $$$m$$$ occurs in
the array no more than two timesfirst error
412 the array $$$a$$$ does not contain
numbers, which are divisible by $$$4$$$1first error
529 $$$n \leqslant 500$$$, $$$m \leqslant 500$$$first error
631—1, 2, 3, 4, 5first error
Examples
Input
9 4
3 4 2 4 4 2 3 3 2
Output
2
Input
6 3
1 2 3 1 2 1
Output
0
Note

There are two ways to split the numbers into triplets in the first sample: {$$$(2, 2, 2)$$$, $$$(3, 3, 3)$$$, $$$(4, 4, 4)$$$} and {$$$(2, 3, 4)$$$, $$$(2, 3, 4)$$$, $$$(2, 3, 4)$$$}.