시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 14 7 7 58.333%

문제

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

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

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

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

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

입력

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

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

출력

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

예제 입력 1

5 2
2 3 1 2 4

예제 출력 1

43
W3sicHJvYmxlbV9pZCI6IjI5NTIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4ZmNcdWFlMzBcdWM3MjhcdWQ0NWMiLCJkZXNjcmlwdGlvbiI6IjxwPlxyXG5cdFx1YjNkOVx1ZDYwMVx1Yzc3NFx1YjI5NCBcdWQ2NTRcdWQ1NTkgXHVjMmRjXHVhYzA0XHVjNWQwIFx1YmNiZFx1YzVkMCBcdWFjNzhcdWI4MjRcdWM3ODhcdWIyOTQgXHVjOGZjXHVhZTMwXHVjNzI4XHVkNDVjXHViOTdjIFx1YmNmNFx1YjJlNFx1YWMwMCBcdWM3YTBcdWM3NzQgXHViNGU0XHVjNWM4XHViMmU0LiBcdWIzZDlcdWQ2MDFcdWM3NzRcdWIyOTQgXHVhZmM4XHVjNWQwXHVjMTFjIFx1YzJlMFx1YWUzMFx1ZDU1OFx1YWM4YyBcdWMwZGRcdWFlMzQgXHVjOGZjXHVhZTMwXHVjNzI4XHVkNDVjXHViOTdjIFx1YmNmNFx1YzU1OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVhZmM4XHVjNWQwXHVjMTFjIFx1YmNmOCBcdWM4ZmNcdWFlMzBcdWM3MjhcdWQ0NWNcdWIyOTQgTlx1YzVmNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVjNWY0XHVjNzQwIFx1YjE5Mlx1Yzc3NFx1YWMwMCBcdWM3ODhcdWFjZTAsIFx1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmNcdWNjOThcdWI3ZmMgXHVjODE1XHViODJjXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC4gXHVjOGZjXHVhZTMwXHVjNzI4XHVkNDVjXHVjNWQwXHViMjk0IFx1YzU0NFx1YzljMSBcdWM1NDRcdWJiMzQgXHVjNmQwXHVjMThjXHViM2M0IFx1YzRmMFx1YzVlY1x1YzgzOCBcdWM3ODhcdWM5YzAgXHVjNTRhXHViMmU0LiBcdWIzZDlcdWQ2MDFcdWM3NzRcdWIyOTQgXHVjNmQwXHVjMThjXHViOTdjIFx1Y2M0NFx1YzZjY1x1YjEyM1x1YzczY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjNkOVx1ZDYwMVx1Yzc3NFx1YjI5NCBcdWJlNDRcdWQ2NWNcdWMxMzEgXHVhZTMwXHVjY2I0IEtcdWFjMWNcdWI5N2MgXHVjYzQ0XHVjNmNjXHViMTIzXHVjNzNjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHViNjEwLCBcdWJlNDRcdWQ2NWNcdWMxMzEgXHVhZTMwXHVjY2I0XHViOTdjIFx1YzExY1x1Yjg1YyBcdWFjMDBcdWFlNGNcdWM3NzQgXHVjNzg4XHVjOWMwIFx1YzU0YVx1YWM4YyBcdWNjNDRcdWM2YjBcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWI0NTAgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNzc0IFx1YzExY1x1Yjg1YyBcdWFjMDBcdWFlNGNcdWM3NzQgXHVjNzg4XHVjNzNjXHViODI0XHViYTc0LCBcdWFjMTlcdWM3NDAgXHVkNTg5XHVjNzc0XHViMDk4IFx1YzVmNFx1YzVkMCBcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWI2MTAsIFx1YzkxMVx1YWMwNFx1YzVkMCBcdWJlNDRcdWM1YjRcdWM3ODhcdWIyOTQgXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzc0IFx1Yzc4OFx1YzczY1x1YmE3NCBcdWM1NDggXHViNDFjXHViMmU0LiBcdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjXHVjNWQwXHVjMTFjICYjMzk7YSYjMzk7XHViMjk0IFx1YWMwMFx1YWU0Y1x1Yzc3NCBcdWM3ODhcdWIyOTQgXHVhYzgzXHVjNzc0IFx1YzU0NFx1YjJjOFx1YzljMFx1YjljYywgJiMzOTtiJiMzOTtcdWIyOTQgXHVhYzAwXHVhZTRjXHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdDxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvcGVyaS5wbmdcIiBzdHlsZT1cIndpZHRoOiAyMTNweDsgaGVpZ2h0OiAxNjRweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+XHJcblx0Tlx1YWNmYyBLLCBcdWFkZjhcdWI5YWNcdWFjZTAgTlx1YzVmNFx1Yzc1OCBcdWIxOTJcdWM3NzRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHViM2Q5XHVkNjAxXHVjNzc0XHVhYzAwIFx1YmU0NFx1ZDY1Y1x1YzEzMSBcdWFlMzBcdWNjYjRcdWI5N2MgXHVjYzQ0XHVjNmIwXHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IE5cdWFjZmMgS1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDUwMCwgMSAmbGU7IEsgJmxlOyA1MDApPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1Y2U3OFx1Yzc1OCBcdWIxOTJcdWM3NzRcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNFx1YzExYyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjE5Mlx1Yzc3NFx1YjI5NCBcdWNkNWNcdWIzMDAgMSwwMDAsMDAwXHVjNzc0XHViMmU0LiBcdWIxOTJcdWM3NzRcdWIyOTQgXHVjNjdjXHVjYWJkIFx1Y2U3OFx1YmQ4MFx1ZDEzMCBcdWM2MjRcdWI5NzhcdWNhYmRcdWFlNGNcdWM5YzAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWIzZDlcdWQ2MDFcdWM3NzRcdWM3NTggXHVjOGZjXHVhZTMwXHVjNzI4XHVkNDVjXHVjNWQwIFx1YmU0NFx1ZDY1Y1x1YzEzMSBcdWFlMzBcdWNjYjRcdWI5N2MgXHVjYzQ0XHVjNmIwXHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWMyMThcdWI5N2MgMSwwMDAsMDAwLDAwN1x1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI5NTIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQRVJJT0ROSSIsImRlc2NyaXB0aW9uIjoiPHA+THVrYSBpcyBib3JlZCBpbiBjaGVtaXN0cnkgY2xhc3Mgc28gaGUgaXMgc3RhcmluZyBhdCBhIGxhcmdlIHBlcmlvZGljIHRhYmxlIG9mIGNoZW1pY2FsIGVsZW1lbnRzIGhhbmdpbmcgZnJvbSBhIHdhbGwgYWJvdmUgdGhlIGJsYWNrYm9hcmQuIFRvIGtpbGwgdGltZSwgTHVrYSBkZWNpZGVkIHRvIG1ha2UgaGlzIG93biB0YWJsZSBjb21wbGV0ZWx5IGRpZmZlcmVudCBmcm9tIHRoZSBvbmUgaW4gdGhlIGNsYXNzcm9vbS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+SGlzIHRhYmxlIGNvbnNpc3RzIG9mIE4gY29sdW1ucywgZWFjaCB3aXRoIHNvbWUgaGVpZ2h0LCBhbGlnbmVkIGF0IHRoZSBib3R0b20gKHNlZSBleGFtcGxlIGJlbG93KS4gQWZ0ZXIgaGUgZHJhd3MgdGhlIHRhYmxlIGhlIG5lZWRzIHRvIGZpbGwgaXQgd2l0aCBlbGVtZW50cy4gSGUgZmlyc3QgZGVjaWRlZCB0byBlbnRlciB0aGUgbm9ibGUgZ2FzZXMgb2Ygd2hpY2ggdGhlcmUgYXJlIEsuIEx1a2EgbXVzdCBwdXQgdGhlbSBpbiB0aGUgdGFibGUgc28gdGhhdCBubyB0d28gbm9ibGUgZ2FzZXMgYXJlIGNsb3NlIHRvIGVhY2ggb3RoZXIuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlR3byBzcXVhcmVzIGluIHRoZSB0YWJsZSBhcmUgY2xvc2UgdG8gZWFjaCBvdGhlciBpZiB0aGV5IGFyZSBpbiB0aGUgc2FtZSBjb2x1bW4gb3Igcm93LCBhbmQgYWxsIHNxdWFyZXMgYmV0d2VlbiB0aGVtIGV4aXN0LiBJbiB0aGUgZXhhbXBsZSBiZWxvdywgdGhlICYjMzk7YSYjMzk7IHNxdWFyZXMgYXJlIG5vdCBjbG9zZSwgYnV0IHRoZSAmIzM5O2ImIzM5OyBzcXVhcmVzIGFyZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9wZXJpLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE2NHB4OyB3aWR0aDoyMTNweFwiIFwvPjxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCwgZ2l2ZW4gTiwgSyBhbmQgdGhlIGhlaWdodHMgb2YgdGhlIE4gY29sdW1ucywgY2FsY3VsYXRlcyB0aGUgdG90YWwgbnVtYmVyIG9mIHdheXMgZm9yIEx1a2EgdG8gcGxhY2UgdGhlIG5vYmxlIGdhc2VzIGludG8gdGhlIHRhYmxlLiBUaGlzIG51bWJlciBjYW4gYmUgbGFyZ2UsIHNvIG91dHB1dCBpdCBtb2R1bG8gMTAwMDAwMDAwNy4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHRoZSBpbnRlZ2VycyBOIGFuZCBLIHNlcGFyYXRlZCBieSBhIHNwYWNlICgxICZsZTsgTiAmbGU7IDUwMCwgMSAmbGU7IEsgJmxlOyA1MDApLCB0aGUgbnVtYmVyIG9mIGNvbHVtbnMgaW4gTHVrYSYjMzk7cyB0YWJsZSBhbmQgdGhlIG51bWJlciBvZiBub2JsZSBnYXNlcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIG5leHQgbGluZSBjb250YWlucyBOIHBvc2l0aXZlIGludGVnZXJzLCBzZXBhcmF0ZWQgYnkgc3BhY2VzLiBUaGVzZSBhcmUgaGVpZ2h0cyBvZiB0aGUgY29sdW1ucyBmcm9tIGxlZnQgdG8gcmlnaHQuIFRoZSBoZWlnaHRzIHdpbGwgYmUgYXQgbW9zdCAxMDAwMDAwLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0aGUgbnVtYmVyIG9mIHdheXMgZm9yIEx1a2EgdG8gZmlsbCBoaXMgdGFibGUgd2l0aCBub2JsZSBnYXNlcywgbW9kdWxvIDEwMDAwMDAwMDcuJm5ic3A7PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d