G. Игровые автоматы
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ввиду стремительного развития человечества в космической сфере, сказки, которые родители рассказывают детям, весьма исказились. Они перестали быть интересными или смешными и превратились в задачи по информатике. Так, например, марсианским детям на ночь рассказывают следующую задачу.

Жили-были три друга — Саша, Кирилл и Юра. В какой-то момент у них закончились деньги. Поэтому они решили построить казино и стали придумывать правила:

  • Саша: — В автомате будет лежать $$$a$$$ камней, и за ход можно забрать произвольное количество камней от $$$1$$$ до $$$k$$$;
  • Кирилл: — Если кто-то взял столько же камней из автомата, сколько из него брали в предыдущий раз, то он проиграл.
  • Юра: — Автоматов будет $$$n$$$ штук, и в $$$i$$$-м из них будет лежать $$$a_i$$$ камней.

Постоянно играть в одну и ту же игру скучно, к тому же нет никакого элемента случайности. Поэтому друзья решили уточнить правила:

  • Саша: — При входе для игрока генерируется пара случайных чисел $$$(l,r)$$$ ($$$1 \le l \le r \le n$$$). За один ход можно забрать камни из любого автомата с номером $$$i$$$, таким что $$$l \le i \le r$$$.
  • Кирилл: — С игроком играет специально обученный персонал, они делают ходы по очереди, при чем первый ход делает игрок.
  • Юра: — Игрок проиграл, если не может сделать ни одного хода по правилам игры, в таком случае он отдает свою квартиру владельцам казино.

Друзья также решили оценить прибыльность своей схемы, но с этим они уже не справились. Поэтому они просят вас помочь им вычислить количество пар $$$(l, r)$$$, при выборе которых в игре побеждает казино.

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

В первой строке указаны числа $$$n$$$ и $$$k$$$ — количество автоматов и максимальное количество камней, которые можно брать за ход.

Во второй строке указаны числа $$$a_1, \ldots, a_n$$$ — исходное количество камней в каждом из автоматов.

$$$$$$1 \le n \le 1\,000\,000$$$$$$ $$$$$$2 \le k \le 100$$$$$$ $$$$$$1 \le a_i \le 10^{18}$$$$$$

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

Выведите единственное число — ответ на задачу.

Примеры
Входные данные
3 2
1 2 3
Выходные данные
3
Входные данные
2 10
308 693
Выходные данные
3
Примечание

Рассмотрим первый пример:

  • $$$(l,r)=(1,1)$$$. Побеждает игрок, так как он может за первый ход взять все камни.
  • $$$(l,r)=(2,2)$$$. Побеждает игрок, так как он может за первый ход взять все камни.
  • $$$(l,r)=(3,3)$$$. Побеждает казино. Пусть игрок на первом ходу взял $$$x$$$ камней, тогда казино возьмет $$$3-x$$$.
  • $$$(l,r)=(1,2)$$$. Побеждает казино. Заметим, что из кучки размера $$$2$$$ забрать камни можно только один раз (если забрали только $$$1$$$ камень, то еще один нельзя будет забрать никогда, так как это повтор хода). Поэтому игрока всегда будет заканчиваться за два хода.
  • $$$(l,r)=(2,3)$$$. Побеждает игрок, так как первым ходом он может забрать все камни из второй кучки.
  • $$$(l,r)=(1,3)$$$. Побеждает казино, так как у него есть стратегия ответных ходов:
    • Если игрок берет камни из первой кучки, то казино берет камни из второй, и наоборот.
    • Если игрок берет $$$x$$$ камней из третьей кучки, то казино берет $$$3-x$$$ камней из этой же кучки.

Из всевозможных пар $$$(l, r)$$$ нам подходят $$$3$$$ пары $$$(3,3)$$$, $$$(1,2)$$$, $$$(1,3)$$$, поэтому ответ равен $$$3$$$.