| Codeforces Round 166 (Div. 2) |
|---|
| Закончено |
В стране коней живут три коня: один серый, другой белый, третий серо-белый. Кони очень забавные животные, поэтому им очень нравятся особенные карточки. На каждой такой карточке должно быть написано два целых числа, первое — вверху карточки, второе — внизу карточки. Обозначим карточку, на которой сверху написано число a, а снизу написано число b как (a, b).
Каждый из трех коней умеет рисовать особенные карточки. Если серому коню показать карточку (a, b), он может нарисовать новую карточку (a + 1, b + 1). Если белому коню показать карточку (a, b) , такую что a и b четные числа, он может нарисовать новую карточку 
. Если серо-белому коню показать две карточки (a, b) и (b, c), то он может нарисовать новую карточку (a, c).
Поликарп очень хочет получить n особенных карточек (1, a1), (1, a2), ..., (1, an). Для этого Поликарп собирается в страну коней. Он может взять с собой в страну коней ровно одну карточку (x, y), такую что 1 ≤ x < y ≤ m. Сколькими способами он может выбрать эту карточку, чтобы в результате некоторых действий в стране коней он смог получить требуемые карточки?
Поликарп может получать карточки только от коней в результате действий описанных выше. Кроме требуемых карточек, Поликарпу разрешается получить некоторые дополнительные карточки.
В первой строке записаны два целых числа n, m (1 ≤ n ≤ 105, 2 ≤ m ≤ 109). Во второй строке записана последовательность целых чисел a1, a2, ..., an (2 ≤ ai ≤ 109). Обратите внимание, числа в последовательности могут повторяться.
Числа в строках разделяются одиночными пробелами.
Выведите единственное целое число — ответ на задачу.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на C++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
1 6
2
11
1 6
7
14
2 10
13 7
36
