Cho hai số nguyên ~n~ và ~m~ và một dãy gồm ~n~ số nguyên dương ~a_i~. Đếm số cách xếp ~n~ phần tử vào ~m~ ô trống sao cho: Gọi ~p_i~ là vị trí mà ~i~ được điền, khi đó ~min(|p_i - p_j|) \geq a_i \space (a_i \leq n, j \neq i)~.

In đáp án chia lấy dư cho ~10 ^ 9 + 7~.

Input

Dòng đầu gồm 2 số nguyên dương ~n~ và ~m~.

Dòng thứ hai gồm ~n~ số nguyên dương ~a_i~ (~i \leq n~).

Giới hạn: ~n \leq 50, m \leq 10^6, a_i \leq n~.

Output

Một số duy nhất là kết quả của bài toán chia lấy dư cho ~10 ^ 9 + 7~.

Sample Input 1

2 3
2 2

Sample Output 1

2

Notes

Giải thích test ví dụ: các cách xếp thỏa mãn là "~1 \space o \space 2~", "~2 \space o \space 1~" với ~o~ tượng trưng cho ô trống.