시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 9 3 3 50.000%

문제

동혁이는 화학 시간에 벽에 걸려있는 주기율표를 보다가 잠이 들었다. 동혁이는 꿈에서 신기하게 생긴 주기율표를 보았다.

꿈에서 본 주기율표는 N열로 이루어져 있다. 각 열은 높이가 있고, 아래 그림처럼 정렬되어 있다. 주기율표에는 아직 아무 원소도 쓰여져 있지 않다. 동혁이는 원소를 채워넣으려고 한다.

동혁이는 비활성 기체 K개를 채워넣으려고 한다. 또, 비활성 기체를 서로 가까이 있지 않게 채우려고 한다.

두 정사각형이 서로 가까이 있으려면, 같은 행이나 열에 있어야 한다. 또, 중간에 비어있는 사각형이 있으면 안된다. 아래 그림에서 'a'는 가까이 있는 것이 아니지만, 'b'는 가까이 있는 것이다.

N과 K, 그리고 N열의 높이가 주어졌을 때, 동혁이가 비활성 기체를 채우는 방법의 수를 출력하는 프로그램을 작성하시오.

입력

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

다음 줄에는 각 칸의 높이가 공백으로 구분되어서 주어진다. 높이는 최대 1,000,000이다. 높이는 왼쪽 칸부터 오른쪽까지 순서대로 주어진다.

출력

동혁이의 주기율표에 비활성 기체를 채우는 방법의 수를 1,000,000,007로 나눈 나머지를 출력한다.

예제 입력

5 2
2 3 1 2 4

예제 출력

43

힌트