Розв’язавши всі задачі на змаганнях, Ви вирішили розкласти пасьянс на комп’ютері. У Вас є N гральних карт, що пронумеровані від 1 до N, а на ігровому полі — М комірок, що пронумеровані від 1 до М зліва направо. Вам необхідно розмістити кожну карту у деяку комірку, враховуючи наступні вимоги:

• карта 1 повинна бути розміщена рівно D1 комірок лівіше, або рівно D1 комірок правіше від карти 2;

• карта 2 повинна бути розміщена рівно D2 комірок лівіше, або рівно 'D[2]' комірок правіше від карти 3;

• ...

• карта N повинна бути розміщена рівно DN комірок лівіше, або рівно DN комірок правіше від карти 1;

Вам необхідно знайти кількість різних способів, якими Ви можете розкласти пасьянс. Зауважте, що у одній комірці можна розмістити довільну кількість карт.

Вхідні дані

У першому рядку два цілі числа N та М через пробіл. У наступному рядку N цілих чисел D1, D2,...,DN через пробіл.

Вихідні дані

Кількість способів розкладу пасьянсу.

Обмеження

2 < N < 36,

1 < М < 1000000 (106),

1 < Dj < 10000 (104).

Примітки

У першому прикладі можливі наступні розклади:

{1} - {5} - {4} - {2} - {3}

{5} - {1, 4} — {} — {3} — {2}

{1, 4} — {5} — {3} — {2} — {}

{} — {1, 4} — {5} — {3} — {2}

{3} — {2} — {4} — {5} — {1}

{2} — {3} — {} — {1, 4} — {5}

{} — {2} — {3} — {5} — {1, 4}

{2} — {3} — {5} — {1, 4} — {}