D. Три подотрезка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив целых чисел $$$a_1, a_2, \dots, a_n$$$, все числа в массиве от $$$1$$$ до $$$m$$$.

Посчитайте количество способов выбрать три непустых непересекающихся отрезка $$$a$$$ так, чтобы количество вхождений каждого числа от $$$1$$$ до $$$m$$$ в объединение этих трёх отрезков было одним и тем же чётным числом.

Входные данные

Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$3 \le n \le 300; 1 \le m \le n$$$) — размер массива и ограничение на максимальный элемент в нём соответственно.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le m$$$) — элементы массива $$$a$$$.

Выходные данные

В единственной строке выведите ответ на задачу — количество способов выбрать три непустых непересекающихся отрезка массива так, чтобы количество вхождений каждого числа от $$$1$$$ до $$$m$$$ в объединение этих трёх отрезков было одним и тем же чётным числом.

Примеры
Входные данные
5 2
2 1 2 2 1
Выходные данные
7
Входные данные
12 3
1 2 3 2 1 3 3 1 1 2 3 2
Выходные данные
278
Примечание

В первом тесте все хорошие объединения выглядят так:

  • [2] [1] 2 [2 1];
  • [2] [1 2] 2 [1];
  • [2 1] [2] 2 [1];
  • [2 1] 2 [2] [1];
  • 2 [1] [2] [2 1];
  • 2 [1] [2 2] [1];
  • 2 [1 2] [2] [1];

Для второго теста приведём лишь некоторые из хороших объединений:

  • [1 2 3 2] [1 3 3 1 1 2] [3 2];
  • 1 2 [3 2] 1 [3] 3 [1 1 2] 3 2;
  • [1 2 3] 2 1 3 [3 1] 1 2 3 [2];
  • [1] [2 3 2] [1 3] 3 1 1 2 3 2;
  • [1] 2 3 2 1 3 [3 1] 1 [2 3 2];
  • 1 [2 3] [2 1 3] 3 1 [1] 2 3 2;