Задача №115220. Разбиение на тройки
На день рождения Маше как обычно подарили массив \(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\).
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены
| Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке |
| 1 | 10 | \(m \le 3\) | первая ошибка | |
| 2 | 8 | \(m \le 4\) | 1 | первая ошибка |
| 3 | 10 | каждое число от \(1\) до \(m\) встречается не более двух раз | первая ошибка | |
| 4 | 12 | массив \(a\) не содержит чисел, которые делятся на \(4\) | 1 | первая ошибка |
| 5 | 29 | \(n \leqslant 500\), \(m \leqslant 500\) | первая ошибка | |
| 6 | 31 | — | 1, 2, 3, 4, 5 | первая ошибка |
В первом примере числа можно разбить на тройки двумя способами: {\((2, 2, 2)\), \((3, 3, 3)\), \((4, 4, 4)\)} и {\((2, 3, 4)\), \((2, 3, 4)\), \((2, 3, 4)\)}.
9 4 3 4 2 4 4 2 3 3 2
2
6 3 1 2 3 1 2 1
0