I. I Spy
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Womais is training to become a world-class spy to protect his magical village. His final assignment is to observe a tall building through very thick fog. This building has $$$n$$$ floors, each floor has $$$m$$$ windows in a row such that all the windows of this building form an $$$n\times m$$$ grid. Each window is either dark or lit by a light from inside the building. Womais needs to determine exactly which of the windows are lit to know the distribution of people inside the building. Enhancing his emerald eyes with an enigmatic magic, Womais is able to see through the fog well enough to make two observations:

  • Floor $$$i$$$ has exactly $$$a_i$$$ lit windows.
  • No two lit windows are horizontally or vertically adjacent.
This information is definitely an improvement from guessing in the dark, but how many possible ways are there for the windows to be lit? Two ways are considered different if a window is lit in one but dark in the other. Since the answer could be very large, please output it modulo the prime $$$10^9 + 7$$$.
Input

The first line of input contains two space-separated integers $$$n$$$ and $$$m$$$ ($$$1\le n\le 30$$$, $$$1\le m\le 23$$$), representing the number of floors and the number of windows on each floor respectively (ie. the dimensions of the building).

The second line of input contains $$$n$$$ space-separated integers. The $$$i$$$-th integer is $$$a_i$$$ ($$$0\le a_i\le m$$$), representing the number of lit windows on the $$$i$$$-th floor.

Output

The output should contain a single integer, the number of ways (modulo $$$10^9 + 7$$$) for the windows to be lit so that both of Womais's observations are satisfied.

Examples
Input
4 3
1 2 0 2
Output
1
Input
2 3
2 2
Output
0