D. Boxes
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Xiaopeng is a warehouse keeper. One day, he was idle and decided to arrange the boxes he manages.

There are now $$$n$$$ closely adjacent shelves, where the height of the $$$i$$$-th shelf from left to right is $$$a_i$$$. Specifically, $$$a_0 = a_{n+1} = +\infty$$$. There are $$$m$$$ boxes of size 1 to be placed on these shelves. Xiaopeng considers a placement scheme "good" if it satisfies the following conditions:

We model the warehouse as a two-dimensional Cartesian coordinate system. If a box is placed at coordinate $$$(x,y)$$$, then:

  • $$$a_x \lt y$$$.
  • $$$(x,y-1)$$$ either satisfies $$$a_x \ge y-1$$$ or has a box placed at $$$(x,y-1)$$$.
  • $$$(x-1,y)$$$ either satisfies $$$a_{x-1} \ge y$$$ or has a box placed at $$$(x-1,y)$$$.
  • $$$(x+1,y)$$$ either satisfies $$$a_{x+1} \ge y$$$ or has a box placed at $$$(x+1,y)$$$.

Xiaopeng wants to determine the total number of good placement schemes. The answer should be taken modulo $$$10^9+7$$$.

Input

The first line contains two positive integers $$$n,m$$$ ($$$1 \le n \le 10^3$$$, $$$1 \le m \le 10^4$$$), representing the number of shelves and boxes.

The second line contains $$$n$$$ non-negative integers, where the $$$i$$$-th number denotes the height $$$a_i$$$ ($$$0 \le a_i \le 10^5$$$) of each shelf.

Output

Output a single integer, representing the number of good schemes.

Example
Input
4 6
5 1 6 1
Output
5