시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHJcblxyXG48cD5cclxuXHRcdWI0NTAgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNzc0IFx1YzExY1x1Yjg1YyBcdWFjMDBcdWFlNGNcdWM3NzQgXHVjNzg4XHVjNzNjXHViODI0XHViYTc0LCBcdWFjMTlcdWM3NDAgXHVkNTg5XHVjNzc0XHViMDk4IFx1YzVmNFx1YzVkMCBcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWI2MTAsIFx1YzkxMVx1YWMwNFx1YzVkMCBcdWJlNDRcdWM1YjRcdWM3ODhcdWIyOTQgXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzc0IFx1Yzc4OFx1YzczY1x1YmE3NCBcdWM1NDhcdWI0MWNcdWIyZTQuIFx1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmNcdWM1ZDBcdWMxMWMgJiMzOTthJiMzOTtcdWIyOTQgXHVhYzAwXHVhZTRjXHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWFjODNcdWM3NzQgXHVjNTQ0XHViMmM4XHVjOWMwXHViOWNjLCAmIzM5O2ImIzM5O1x1YjI5NCBcdWFjMDBcdWFlNGNcdWM3NzQgXHVjNzg4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9wZXJpLnBuZ1wiIHN0eWxlPVwid2lkdGg6IDIxM3B4OyBoZWlnaHQ6IDE2NHB4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5cclxuXHROXHVhY2ZjIEssIFx1YWRmOFx1YjlhY1x1YWNlMCBOXHVjNWY0XHVjNzU4IFx1YjE5Mlx1Yzc3NFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWIzZDlcdWQ2MDFcdWM3NzRcdWFjMDAgXHViZTQ0XHVkNjVjXHVjMTMxIFx1YWUzMFx1Y2NiNFx1Yjk3YyBcdWNjNDRcdWM2YjBcdWIyOTQgXHViYzI5XHViYzk1XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgTlx1YWNmYyBLXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgNTAwLCAxICZsZTsgSyAmbGU7IDUwMCk8XC9wPlxyXG5cclxuPHA+XHJcblx0XHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHVjZTc4XHVjNzU4IFx1YjE5Mlx1Yzc3NFx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0XHVjMTFjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMTkyXHVjNzc0XHViMjk0IFx1Y2Q1Y1x1YjMwMCAxLDAwMCwwMDBcdWM3NzRcdWIyZTQuIFx1YjE5Mlx1Yzc3NFx1YjI5NCBcdWM2N2NcdWNhYmQgXHVjZTc4XHViZDgwXHVkMTMwIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YWU0Y1x1YzljMCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1YjNkOVx1ZDYwMVx1Yzc3NFx1Yzc1OCBcdWM4ZmNcdWFlMzBcdWM3MjhcdWQ0NWNcdWM1ZDAgXHViZTQ0XHVkNjVjXHVjMTMxIFx1YWUzMFx1Y2NiNFx1Yjk3YyBcdWNjNDRcdWM2YjBcdWIyOTQgXHViYzI5XHViYzk1XHVjNzU4IFx1YzIxOFx1Yjk3YyAxLDAwMCwwMDAsMDA3XHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI5NTIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQRVJJT0ROSSIsImRlc2NyaXB0aW9uIjoiPHA+THVrYSBpcyBib3JlZCBpbiBjaGVtaXN0cnkgY2xhc3Mgc28gaGUgaXMgc3RhcmluZyBhdCBhIGxhcmdlIHBlcmlvZGljIHRhYmxlIG9mIGNoZW1pY2FsIGVsZW1lbnRzIGhhbmdpbmcgZnJvbSBhIHdhbGwgYWJvdmUgdGhlIGJsYWNrYm9hcmQuIFRvIGtpbGwgdGltZSwgTHVrYSBkZWNpZGVkIHRvIG1ha2UgaGlzIG93biB0YWJsZSBjb21wbGV0ZWx5IGRpZmZlcmVudCBmcm9tIHRoZSBvbmUgaW4gdGhlIGNsYXNzcm9vbS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+SGlzIHRhYmxlIGNvbnNpc3RzIG9mIE4gY29sdW1ucywgZWFjaCB3aXRoIHNvbWUgaGVpZ2h0LCBhbGlnbmVkIGF0IHRoZSBib3R0b20gKHNlZSBleGFtcGxlIGJlbG93KS4gQWZ0ZXIgaGUgZHJhd3MgdGhlIHRhYmxlIGhlIG5lZWRzIHRvIGZpbGwgaXQgd2l0aCBlbGVtZW50cy4gSGUgZmlyc3QgZGVjaWRlZCB0byBlbnRlciB0aGUgbm9ibGUgZ2FzZXMgb2Ygd2hpY2ggdGhlcmUgYXJlIEsuIEx1a2EgbXVzdCBwdXQgdGhlbSBpbiB0aGUgdGFibGUgc28gdGhhdCBubyB0d28gbm9ibGUgZ2FzZXMgYXJlIGNsb3NlIHRvIGVhY2ggb3RoZXIuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlR3byBzcXVhcmVzIGluIHRoZSB0YWJsZSBhcmUgY2xvc2UgdG8gZWFjaCBvdGhlciBpZiB0aGV5IGFyZSBpbiB0aGUgc2FtZSBjb2x1bW4gb3Igcm93LCBhbmQgYWxsIHNxdWFyZXMgYmV0d2VlbiB0aGVtIGV4aXN0LiBJbiB0aGUgZXhhbXBsZSBiZWxvdywgdGhlICYjMzk7YSYjMzk7IHNxdWFyZXMgYXJlIG5vdCBjbG9zZSwgYnV0IHRoZSAmIzM5O2ImIzM5OyBzcXVhcmVzIGFyZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9wZXJpLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE2NHB4OyB3aWR0aDoyMTNweFwiIFwvPjxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCwgZ2l2ZW4gTiwgSyBhbmQgdGhlIGhlaWdodHMgb2YgdGhlIE4gY29sdW1ucywgY2FsY3VsYXRlcyB0aGUgdG90YWwgbnVtYmVyIG9mIHdheXMgZm9yIEx1a2EgdG8gcGxhY2UgdGhlIG5vYmxlIGdhc2VzIGludG8gdGhlIHRhYmxlLiBUaGlzIG51bWJlciBjYW4gYmUgbGFyZ2UsIHNvIG91dHB1dCBpdCBtb2R1bG8gMTAwMDAwMDAwNy4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHRoZSBpbnRlZ2VycyBOIGFuZCBLIHNlcGFyYXRlZCBieSBhIHNwYWNlICgxICZsZTsgTiAmbGU7IDUwMCwgMSAmbGU7IEsgJmxlOyA1MDApLCB0aGUgbnVtYmVyIG9mIGNvbHVtbnMgaW4gTHVrYSYjMzk7cyB0YWJsZSBhbmQgdGhlIG51bWJlciBvZiBub2JsZSBnYXNlcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIG5leHQgbGluZSBjb250YWlucyBOIHBvc2l0aXZlIGludGVnZXJzLCBzZXBhcmF0ZWQgYnkgc3BhY2VzLiBUaGVzZSBhcmUgaGVpZ2h0cyBvZiB0aGUgY29sdW1ucyBmcm9tIGxlZnQgdG8gcmlnaHQuIFRoZSBoZWlnaHRzIHdpbGwgYmUgYXQgbW9zdCAxMDAwMDAwLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0aGUgbnVtYmVyIG9mIHdheXMgZm9yIEx1a2EgdG8gZmlsbCBoaXMgdGFibGUgd2l0aCBub2JsZSBnYXNlcywgbW9kdWxvIDEwMDAwMDAwMDcuJm5ic3A7PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==