Solitaire#7805

Solitaire

1 second

64 megabytes

Easy

After solving all the problems at the competition, you decide to play a game of solitaire on your computer. You have $N$ playing cards, each uniquely numbered from $1$ to $N$ . The game board consists of $M$ cells, numbered from $1$ to $M$ from left to right.

Your task is to place each card into one of these cells, following these rules:

Card $1$ must be positioned exactly $D_{1}$ D_1 cells to the left or right of card $2$ .
Card $2$ must be positioned exactly $D_{2}$ D_2 cells to the left or right of card $3$ .
...
Card $N$ must be positioned exactly $D_{N}$ D_N cells to the left or right of card $1$ .

You need to determine the number of distinct ways to arrange the cards on the board. Note that any number of cards can occupy a single cell.

Input

The first line contains two integers $N$ and $M$ , separated by a space ( $2 < N < 36$ 2 < N < 36, $1 < M < 1000000$ 1 < M < 1\ 000\ 000).The second line contains $N$ integers $D_{1}, D_{2}, \dots, D_{N}$ D_1, D_2, \ldots, D_N, also separated by spaces ( $1 < D_{j} < 10000$ 1 < D_j < 10\ 000 for each $j$ ).

Output

Output the number of distinct ways to arrange the cards according to the rules.

Examples

Example 1

Loading

Example 2

Loading

Note

In the first example, the following arrangements are possible:

${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}$ — ${}$

D_{1}

D_{2}

D_{N}

2 < N < 36

1 < M < 1000000

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

1 < D_{j} < 10000