Пасьянс
Решив все задачи на соревнованиях, вы решили разложить пасьянс на компьютере. У вас есть 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} — {}