|
Разбиение на тройки
(Время: 1 сек. Память: 128 Мб Сложность: 66%)
На день рождения Маше как обычно подарили массив a из n натуральных чисел, в котором каждое число находится в пределах от 1 до m включительно. Маша очень любит число три, поэтому длина массива делится на три.
Маша решила объединять числа в тройки: каждая тройка чисел должна состоять или из трех одинаковых чисел, или из трех последовательных чисел. Другими словами, каждая тройка имеет или вид (x, x, x), или (x, x+1, x+2), где x – какое-то натуральное число.
Маша хочет поиграть с подаренным массивом, и ее интересует количество способов разбить числа этого массива на такие тройки. Два способа разбиения считаются различными, если нельзя установить взаимно-однозначное соответствие между тройками первого разбиения и тройками второго разбиения, что числа внутри соответствующих троек равны. Так как количество разбиений
может быть большим, Маше достаточно знать его остаток по модулю 109+7.
Помогите Маше посчитать количество способов разбить числа подаренного ей массива на тройки по модулю 109+7.
Входные данные
Первая строка входного файла INPUT.TXT содержит два целых числа n и m (1 ≤ n ≤ 5000, 1 ≤ m ≤ 5000, n = 3×k для какого-то натурального k).
Вторая строка содержит n целых чисел ai – числа массива (1 ≤ ai ≤ m).
Выходные данные
В единственную строку выходного файла OUTPUT.TXT выведите одно целое число – количество способов разбить числа массива на тройки по модулю 109+7.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 9 4
3 4 2 4 4 2 3 3 2 | 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)}.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
