На день рождения Маше как обычно подарили массив \(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\).
В первом примере числа можно разбить на тройки двумя способами: {\((2, 2, 2)\), \((3, 3, 3)\), \((4, 4, 4)\)} и {\((2, 3, 4)\), \((2, 3, 4)\), \((2, 3, 4)\)}.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
9 4
3 4 2 4 4 2 3 3 2
|
2
|
|
2
|
6 3
1 2 3 1 2 1
|
0
|