Пасьянс
Розв’язавши всі задачі на змаганнях, Ви вирішили розкласти пасьянс на комп’ютері. У Вас є N гральних карт, що пронумеровані від 1 до N, а на ігровому полі — М комірок, що пронумеровані від 1 до М зліва направо. Вам необхідно розмістити кожну карту у деяку комірку, враховуючи наступні вимоги:
• карта 1 повинна бути розміщена рівно D[1] комірок лівіше, або рівно D[1] комірок правіше від карти 2;
• карта 2 повинна бути розміщена рівно D[2] комірок лівіше, або рівно 'D[2]' комірок правіше від карти 3;
• ...
• карта N повинна бути розміщена рівно D[N] комірок лівіше, або рівно D[N] комірок правіше від карти 1;
Вам необхідно знайти кількість різних способів, якими Ви можете розкласти пасьянс. Зауважте, що у одній комірці можна розмістити довільну кількість карт.
Вхідні дані
У першому рядку два цілі числа N та М через пробіл. У наступному рядку N цілих чисел D[1], D[2],...,D[N] через пробіл.
Вихідні дані
Кількість способів розкладу пасьянсу.
Обмеження
2 < N < 36,
1 < М < 1000000 (10^6),
1 < D[j] < 10000 (10^4).
Примітки
У першому прикладі можливі наступні розклади:
{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} — {}