주기율표

동혁이는 꿈속에서 N개의 열로 된 빈 주기율표를 보았다. i번째 열의 높이는 h_i이고, 모든 열은 아래쪽을 맞추어 놓여 있다. 각 칸에는 아직 아무 원소도 쓰여 있지 않다.

동혁이는 서로 가까이 있지 않도록 비활성 기체 K개를 서로 다른 칸에 넣으려고 한다.

두 칸이 가까이 있다는 것은 두 칸이 같은 행 또는 같은 열에 있고, 그 사이에 존재하지 않는 칸이 하나도 없다는 뜻이다. 같은 열에서는 두 칸 사이의 모든 칸이 존재하므로 한 열에서 두 칸을 함께 고를 수 없다. 같은 행에서는 두 칸 사이의 모든 열이 그 행까지 높이를 가지고 있으면 두 칸을 함께 고를 수 없다. 아래 그림에서 a로 표시된 두 칸은 가까이 있지 않고, b로 표시된 두 칸은 가까이 있다.

N, K와 N개 열의 높이가 주어졌을 때, 비활성 기체 K개를 배치하는 방법의 수를 구하시오.

첫째 줄에 N과 K가 주어진다. (1 <= N <= 500, 1 <= K <= 500)

둘째 줄에 N개 열의 높이 h_1, h_2, ..., h_N이 왼쪽부터 오른쪽 순서대로 공백으로 구분되어 주어진다. 각 높이는 1 이상 1,000,000 이하이다.

비활성 기체 K개를 배치하는 방법의 수를 1,000,000,007로 나눈 나머지를 출력한다.