Solitaire

After completing 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 sequentially from 1 to M from left to right. Your task is to place each card into one of these cells, adhering to the following rules:

• Card 1 must be positioned exactly D[1] cells to the left or right of card 2.

• Card 2 must be positioned exactly D[2] cells to the left or right of card 3.

• ...

• Card N must be positioned exactly D[N] cells to the left or right of card 1.

Your goal is to determine the number of distinct ways to arrange the cards on the board. Note that multiple cards can occupy the same cell.

Input

The first line contains two integers, N and M, separated by a space. The second line contains N integers D[1], D[2], ..., D[N], also separated by spaces.

Output

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

Constraints

• 2 < N < 36

• 1 < M < 1,000,000

• 1 < D[j] < 10,000 for each j

Notes

For example, the possible arrangements in one scenario are:

• {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} - {}

Examples