7. Разбиение на тройки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На день рождения Маше как обычно подарили массив $$$a$$$ из $$$n$$$ натуральных чисел, в котором каждое число находится в пределах от $$$1$$$ до $$$m$$$ включительно. Маша очень любит число три, поэтому длина массива делится на три.

Маша решила объединять числа в тройки: каждая тройка чисел должна состоять или из трех одинаковых чисел, или из трех последовательных чисел. Другими словами, каждая тройка имеет или вид $$$(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$$$.

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены

|c|c|}

Подзадача

Баллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
110 $$$m \le 3$$$первая ошибка
28 $$$m \le 4$$$1первая ошибка
310 каждое число от $$$1$$$ до $$$m$$$
встречается не более двух разпервая ошибка
412 массив $$$a$$$ не содержит чисел,
которые делятся на $$$4$$$1первая ошибка
529 $$$n \leqslant 500$$$, $$$m \leqslant 500$$$первая ошибка
631—1, 2, 3, 4, 5первая ошибка
Примеры
Входные данные
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)$$$}.