You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

翻译自 ROIR 2024 D2T3。

在生日那天，玛莎像往常一样收到了一个由 $n$ 个数组成的数组 $a$，其中每个数字都在 $1$ 到 $m$ 之间。玛莎非常喜欢数字 $3$，因此数组的长度能被 $3$ 整除。

玛莎决定将这些数字分组为三元组：每个三元组要么由三个相同的数字组成，要么由三个连续的数字组成。换句话说，每个三元组的形式要么是 $(x, x, x)$，要么是 $(x, x + 1, x + 2)$，其中 $x$ 是一个正整数。

玛莎想要研究这个礼物中的数组，她想知道将数组中的数字分成这样的三元组的方式有多少种。如果不能为第一个分组中的每个三元组与第二个分组中的每个三元组建立一一对应关系，使得对应三元组中的数字相等，则两个分组方式被认为是不同的。由于分组方式可能非常多，玛莎只需知道其模 $10^9 + 7$ 的余数。

题目描述

帮助玛莎计算将数组中的数字分成三元组的方式的数量，对 $10^9 + 7$ 取模。

输入格式

第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 5000$，$1 \leq m \leq 5000$，$n$ 是 $3$ 的倍数）。

第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$，表示数组中的数字（$1 \leq a_i \leq m$）。

输出格式

输出一行一个整数，即将数组中的数字分成三元组的方式的数量，对 $10^9 + 7$ 取模。

9 4
3 4 2 4 4 2 3 3 2

2

6 3
1 2 3 1 2 1

0

提示

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

对于 $100\%$ 的数据，$1 \leq n \leq 5000$，$1 \leq a_i \leq m \leq 5000$，$n$ 是 $3$ 的倍数。