시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB126660.000%

문제

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

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

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

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

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

입력

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

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

출력

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

예제 입력 1

3 3
2 1 3

예제 출력 1

2

예제 입력 2

4 1
1 2 3 4

예제 출력 2

10

예제 입력 3

5 2
2 3 1 2 4

예제 출력 3

43

예제 입력 4

3 2
999999 999999 999999

예제 출력 4

990979013
W3sicHJvYmxlbV9pZCI6IjI5NTIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4ZmNcdWFlMzBcdWM3MjhcdWQ0NWMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjNkOVx1ZDYwMVx1Yzc3NFx1YjI5NCBcdWQ2NTRcdWQ1NTkgXHVjMmRjXHVhYzA0XHVjNWQwIFx1YmNiZFx1YzVkMCBcdWFjNzhcdWI4MjRcdWM3ODhcdWIyOTQgXHVjOGZjXHVhZTMwXHVjNzI4XHVkNDVjXHViOTdjIFx1YmNmNFx1YjJlNFx1YWMwMCBcdWM3YTBcdWM3NzQgXHViNGU0XHVjNWM4XHViMmU0LiBcdWIzZDlcdWQ2MDFcdWM3NzRcdWIyOTQgXHVhZmM4XHVjNWQwXHVjMTFjIFx1YzJlMFx1YWUzMFx1ZDU1OFx1YWM4YyBcdWMwZGRcdWFlMzQgXHVjOGZjXHVhZTMwXHVjNzI4XHVkNDVjXHViOTdjIFx1YmNmNFx1YzU1OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZmM4XHVjNWQwXHVjMTFjIFx1YmNmOCBcdWM4ZmNcdWFlMzBcdWM3MjhcdWQ0NWNcdWIyOTQgTlx1YzVmNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVjNWY0XHVjNzQwIFx1YjE5Mlx1Yzc3NFx1YWMwMCBcdWM3ODhcdWFjZTAsIFx1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmNcdWNjOThcdWI3ZmMgXHVjODE1XHViODJjXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC4gXHVjOGZjXHVhZTMwXHVjNzI4XHVkNDVjXHVjNWQwXHViMjk0IFx1YzU0NFx1YzljMSBcdWM1NDRcdWJiMzQgXHVjNmQwXHVjMThjXHViM2M0IFx1YzRmMFx1YzVlY1x1YzgzOCBcdWM3ODhcdWM5YzAgXHVjNTRhXHViMmU0LiBcdWIzZDlcdWQ2MDFcdWM3NzRcdWIyOTQgXHVjNmQwXHVjMThjXHViOTdjIFx1Y2M0NFx1YzZjY1x1YjEyM1x1YzczY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjNkOVx1ZDYwMVx1Yzc3NFx1YjI5NCBcdWJlNDRcdWQ2NWNcdWMxMzEgXHVhZTMwXHVjY2I0IEtcdWFjMWNcdWI5N2MgXHVjYzQ0XHVjNmNjXHViMTIzXHVjNzNjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHViNjEwLCBcdWJlNDRcdWQ2NWNcdWMxMzEgXHVhZTMwXHVjY2I0XHViOTdjIFx1YzExY1x1Yjg1YyBcdWFjMDBcdWFlNGNcdWM3NzQgXHVjNzg4XHVjOWMwIFx1YzU0YVx1YWM4YyBcdWNjNDRcdWM2YjBcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNzc0IFx1YzExY1x1Yjg1YyBcdWFjMDBcdWFlNGNcdWM3NzQgXHVjNzg4XHVjNzNjXHViODI0XHViYTc0LCBcdWFjMTlcdWM3NDAgXHVkNTg5XHVjNzc0XHViMDk4IFx1YzVmNFx1YzVkMCBcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWI2MTAsIFx1YzkxMVx1YWMwNFx1YzVkMCBcdWJlNDRcdWM1YjRcdWM3ODhcdWIyOTQgXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzc0IFx1Yzc4OFx1YzczY1x1YmE3NCBcdWM1NDggXHViNDFjXHViMmU0LiBcdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjXHVjNWQwXHVjMTFjICYjMzk7YSYjMzk7XHViMjk0IFx1YWMwMFx1YWU0Y1x1Yzc3NCBcdWM3ODhcdWIyOTQgXHVhYzgzXHVjNzc0IFx1YzU0NFx1YjJjOFx1YzljMFx1YjljYywgJiMzOTtiJiMzOTtcdWIyOTQgXHVhYzAwXHVhZTRjXHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvZjE4ZTgzYzUtMjdhOC00YmZmLTk2ODktYmI0NmE0ZGE4YmYwXC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiAxOTNweDsgaGVpZ2h0OiAxNTRweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+Tlx1YWNmYyBLLCBcdWFkZjhcdWI5YWNcdWFjZTAgTlx1YzVmNFx1Yzc1OCBcdWIxOTJcdWM3NzRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHViM2Q5XHVkNjAxXHVjNzc0XHVhYzAwIFx1YmU0NFx1ZDY1Y1x1YzEzMSBcdWFlMzBcdWNjYjRcdWI5N2MgXHVjYzQ0XHVjNmIwXHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IE5cdWFjZmMgS1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDUwMCwgMSAmbGU7IEsgJmxlOyA1MDApPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1Y2U3OFx1Yzc1OCBcdWIxOTJcdWM3NzRcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNFx1YzExYyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjE5Mlx1Yzc3NFx1YjI5NCBcdWNkNWNcdWIzMDAgMSwwMDAsMDAwXHVjNzc0XHViMmU0LiBcdWIxOTJcdWM3NzRcdWIyOTQgXHVjNjdjXHVjYWJkIFx1Y2U3OFx1YmQ4MFx1ZDEzMCBcdWM2MjRcdWI5NzhcdWNhYmRcdWFlNGNcdWM5YzAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWIzZDlcdWQ2MDFcdWM3NzRcdWM3NTggXHVjOGZjXHVhZTMwXHVjNzI4XHVkNDVjXHVjNWQwIFx1YmU0NFx1ZDY1Y1x1YzEzMSBcdWFlMzBcdWNjYjRcdWI5N2MgXHVjYzQ0XHVjNmIwXHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWMyMThcdWI5N2MgMSwwMDAsMDAwLDAwN1x1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyOTUyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUEVSSU9ETkkiLCJkZXNjcmlwdGlvbiI6IjxwPkx1a2EgaXMgYm9yZWQgaW4gY2hlbWlzdHJ5IGNsYXNzIHNvIGhlIGlzIHN0YXJpbmcgYXQgYSBsYXJnZSBwZXJpb2RpYyB0YWJsZSBvZiBjaGVtaWNhbCBlbGVtZW50cyBoYW5naW5nIGZyb20gYSB3YWxsIGFib3ZlIHRoZSBibGFja2JvYXJkLiBUbyBraWxsIHRpbWUsIEx1a2EgZGVjaWRlZCB0byBtYWtlIGhpcyBvd24gdGFibGUgY29tcGxldGVseSBkaWZmZXJlbnQgZnJvbSB0aGUgb25lIGluIHRoZSBjbGFzc3Jvb20uJm5ic3A7PFwvcD5cclxuXHJcbjxwPkhpcyB0YWJsZSBjb25zaXN0cyBvZiBOIGNvbHVtbnMsIGVhY2ggd2l0aCBzb21lIGhlaWdodCwgYWxpZ25lZCBhdCB0aGUgYm90dG9tIChzZWUgZXhhbXBsZSBiZWxvdykuIEFmdGVyIGhlIGRyYXdzIHRoZSB0YWJsZSBoZSBuZWVkcyB0byBmaWxsIGl0IHdpdGggZWxlbWVudHMuIEhlIGZpcnN0IGRlY2lkZWQgdG8gZW50ZXIgdGhlIG5vYmxlIGdhc2VzIG9mIHdoaWNoIHRoZXJlIGFyZSBLLiBMdWthIG11c3QgcHV0IHRoZW0gaW4gdGhlIHRhYmxlIHNvIHRoYXQgbm8gdHdvIG5vYmxlIGdhc2VzIGFyZSBjbG9zZSB0byBlYWNoIG90aGVyLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Ud28gc3F1YXJlcyBpbiB0aGUgdGFibGUgYXJlIGNsb3NlIHRvIGVhY2ggb3RoZXIgaWYgdGhleSBhcmUgaW4gdGhlIHNhbWUgY29sdW1uIG9yIHJvdywgYW5kIGFsbCBzcXVhcmVzIGJldHdlZW4gdGhlbSBleGlzdC4gSW4gdGhlIGV4YW1wbGUgYmVsb3csIHRoZSAmIzM5O2EmIzM5OyBzcXVhcmVzIGFyZSBub3QgY2xvc2UsIGJ1dCB0aGUgJiMzOTtiJiMzOTsgc3F1YXJlcyBhcmUuJm5ic3A7PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvZjE4ZTgzYzUtMjdhOC00YmZmLTk2ODktYmI0NmE0ZGE4YmYwXC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiAxOTNweDsgaGVpZ2h0OiAxNTRweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQsIGdpdmVuIE4sIEsgYW5kIHRoZSBoZWlnaHRzIG9mIHRoZSBOIGNvbHVtbnMsIGNhbGN1bGF0ZXMgdGhlIHRvdGFsIG51bWJlciBvZiB3YXlzIGZvciBMdWthIHRvIHBsYWNlIHRoZSBub2JsZSBnYXNlcyBpbnRvIHRoZSB0YWJsZS4gVGhpcyBudW1iZXIgY2FuIGJlIGxhcmdlLCBzbyBvdXRwdXQgaXQgbW9kdWxvIDEwMDAwMDAwMDcuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyB0aGUgaW50ZWdlcnMgTiBhbmQgSyBzZXBhcmF0ZWQgYnkgYSBzcGFjZSAoMSAmbGU7IE4gJmxlOyA1MDAsIDEgJmxlOyBLICZsZTsgNTAwKSwgdGhlIG51bWJlciBvZiBjb2x1bW5zIGluIEx1a2EmIzM5O3MgdGFibGUgYW5kIHRoZSBudW1iZXIgb2Ygbm9ibGUgZ2FzZXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBuZXh0IGxpbmUgY29udGFpbnMgTiBwb3NpdGl2ZSBpbnRlZ2Vycywgc2VwYXJhdGVkIGJ5IHNwYWNlcy4gVGhlc2UgYXJlIGhlaWdodHMgb2YgdGhlIGNvbHVtbnMgZnJvbSBsZWZ0IHRvIHJpZ2h0LiBUaGUgaGVpZ2h0cyB3aWxsIGJlIGF0IG1vc3QgMTAwMDAwMC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIG51bWJlciBvZiB3YXlzIGZvciBMdWthIHRvIGZpbGwgaGlzIHRhYmxlIHdpdGggbm9ibGUgZ2FzZXMsIG1vZHVsbyAxMDAwMDAwMDA3LiZuYnNwOzxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Contest > Croatian Open Competition in Informatics > COCI 2008/2009 > Contest #4 6번