Пасьянс#7805

Умова Обговорення

Пасьянс

1 секунда

64 мегабайти

Легка

Розвʼязавши всі задачі на змаганнях, Ви вирішили розкласти пасьянс на комп'ютері. У Вас є $N$ гральних карт, що пронумеровані від $1$ до $N$ , а на ігровому полі — $M$ комірок, що пронумеровані від $1$ до $M$ зліва направо.

Ваша задача — розмістити кожну карту у деякій комірці, дотримуючись таких правил:

Карта $1$ повинна бути розміщена рівно на D_1 комірок лівіше або рівно на D_1 комірок правіше від карти $2$ .
Карта $2$ повинна бути розміщена рівно на D_2 комірок лівіше або рівно на D_2 комірок правіше від карти $3$ .
...
Карта $N$ повинна бути розміщена рівно на D_N комірок лівіше або рівно на D_N комірок правіше від карти $1$ .

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

Вхідні дані

У першому рядку містяться два цілі числа $N$ та $M$ , розділені пробілом (2 < N < 36, 1 < M < 1\ 000\ 000).У другому рядку — $N$ цілих чисел D_1, D_2, \ldots, D_N, розділених пробілом (1 < D_j < 10\ 000 для кожного $j$ ).

Вихідні дані

Виведіть кількість різних способів розкласти пасьянс згідно з правилами.

Приклади

Приклад 1

Loading

Loading

Приклад 2

Loading

Loading

Примітка

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

${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}$ — ${2}$ — ${1, 4}$ — ${5}$
${}$ — ${2}$ — ${3}$ — ${5}$ — ${1, 4}$
${5}$ — ${3}$ — ${2}$ — ${3}$ — ${}$

D_{1}

D_{1}

D_{2}

D_{2}

D_{N}

D_{N}

2 < N < 36

1 < M < 1000000

D_{1}, D_{2}, \dots, D_{N}

1 < D_{j} < 10000