题目描述

译自 ROI Regional 2024 Day2 T3. Разбиение на тройки

在玛莎的生日那天，她像往常一样收到一个包含 $n$ 个自然数的数组 $a$，其中每个数字都在 $1$ 到 $m$ 之间。玛莎非常喜欢数字 $3$，因此数组的长度是 $3$ 的倍数。

玛莎决定将数字组合成三元组：每个三元组要么由三个相同的数字组成，要么由三个连续的数字组成。换句话说，每个三元组的形式要么是 $(x, x, x)$，要么是 $(x, x+1, x+2)$，其中 $x$ 是某个自然数。

玛莎想要玩这个礼物数组，她想知道有多少种方法可以将数组中的数字划分为这样的三元组。如果两个划分方式不能通过一一对应的方式使得每个三元组中的数字相同，则认为这两种划分方式不同。由于划分的数量可能非常大，玛莎只需要知道其对 $10^9+7$ 取模的结果。

请帮助玛莎计算将数组划分为三元组的方法数，并对 $10^9+7$ 取模。

输入格式

第一行输入包含两个整数 $n$ 和 $m$（$1 \le n \le 5000$，$1 \le m \le 5000$，$n=3\cdot k$ 对于某个自然数 $k$）。

第二行包含 $n$ 个整数 $a_i$ $(1 \le a_i \le m)$，表示数组中的数字。

输出格式

输出一个整数，表示将数组划分为三元组的方法数，并对 $10^9+7$ 取模。

9 4
3 4 2 4 4 2 3 3 2

2

在第一个样例中，有两种方法可以将数字划分为三元组： $\{(2, 2, 2), (3, 3, 3), (4, 4, 4)\}$ 和 $\{(2, 3, 4), (2, 3, 4), (2, 3, 4)\}$。

6 3
1 2 3 1 2 1

0

数据范围与提示

详细子任务附加限制及分值如下表所示。