시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 378 166 137 44.194%

문제

테트리스는 C열 필드위에서 플레이하는 유명한 게임이다. 필드의 행의 수는 무한하다. 한 번 움직일 때, 아래와 같은 일곱가지 블록 중 하나를 필드에 떨어뜨릴 수 있다.

블록을 떨어뜨리기 전에, 플레이어는 블록을 90, 180, 270도 회전시키거나 좌우로 움직일 수 있다. 이때, 블록이 필드를 벗어나지 않으면 된다. 블록을 필드의 바닥이나 이미 채워져있는 칸의 위에 놓여지게 된다.

창영이가 하고있는 테트리스는 일반적인 테트리스와 약간 규칙이 다르다. 블록이 떨어졌을 때, 블록과 블록 또는 블록과 바닥 사이에 채워져있지 않은 칸이 생기면 안된다.

예를 들어, 아래와 같이 각 칸의 높이가 2, 1, 1, 1, 0, 1인 경우를 생각해보자. 블록 5번을 떨어뜨리는 방법의 수는 아래와 같이 다섯가지이다.

테트리스 필드의 각 칸의 높이와 떨어뜨려야 하는 블록의 번호가 주어진다. 이때, 블록을 놓는 서로 다른 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 C와 떨어뜨리는 블록의 번호 P가 주어진다. (1 ≤ C ≤ 100, 1 ≤ P ≤ 7)

둘째 줄에는 각 칸의 높이가 주어진다. 높이는 0보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 블록을 떨어뜨리는 방법의 수를 출력한다.

예제 입력 1

6 5
2 1 1 1 0 1

예제 출력 1

5
W3sicHJvYmxlbV9pZCI6IjMwMTkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQxNGNcdWQyYjhcdWI5YWNcdWMyYTQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDE0Y1x1ZDJiOFx1YjlhY1x1YzJhNFx1YjI5NCBDXHVjNWY0IFx1ZDU0NFx1YjRkY1x1YzcwNFx1YzVkMFx1YzExYyBcdWQ1MGNcdWI4MDhcdWM3NzRcdWQ1NThcdWIyOTQgXHVjNzIwXHViYTg1XHVkNTVjIFx1YWM4Y1x1Yzc4NFx1Yzc3NFx1YjJlNC4gXHVkNTQ0XHViNGRjXHVjNzU4IFx1ZDU4OVx1Yzc1OCBcdWMyMThcdWIyOTQgXHViYjM0XHVkNTVjXHVkNTU4XHViMmU0LiBcdWQ1NWMgXHViYzg4IFx1YzZjMFx1YzljMVx1Yzc3YyBcdWI1NGMsIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVjNzdjXHVhY2YxXHVhYzAwXHVjOWMwIFx1YmUxNFx1Yjg1ZCBcdWM5MTEgXHVkNTU4XHViMDk4XHViOTdjIFx1ZDU0NFx1YjRkY1x1YzVkMCBcdWI1YThcdWM1YjRcdWI3MjhcdWI5YjQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC90ZXQxKDEpLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE2MXB4OyB3aWR0aDo1MjRweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWJlMTRcdWI4NWRcdWM3NDQgXHViNWE4XHVjNWI0XHViNzI4XHViOWFjXHVhZTMwIFx1YzgwNFx1YzVkMCwgXHVkNTBjXHViODA4XHVjNzc0XHVjNWI0XHViMjk0IFx1YmUxNFx1Yjg1ZFx1Yzc0NCA5MCwgMTgwLCAyNzBcdWIzYzQgXHVkNjhjXHVjODA0XHVjMmRjXHVkMGE0XHVhYzcwXHViMDk4IFx1Yzg4Y1x1YzZiMFx1Yjg1YyBcdWM2YzBcdWM5YzFcdWM3N2MgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWJlMTRcdWI4NWRcdWM3NzQgXHVkNTQ0XHViNGRjXHViOTdjIFx1YmM5N1x1YzViNFx1YjA5OFx1YzljMCBcdWM1NGFcdWM3M2NcdWJhNzQgXHViNDFjXHViMmU0LiBcdWJlMTRcdWI4NWRcdWM3NDQgXHVkNTQ0XHViNGRjXHVjNzU4IFx1YmMxNFx1YjJlNVx1Yzc3NFx1YjA5OCBcdWM3NzRcdWJiZjggXHVjYzQ0XHVjNmNjXHVjODM4XHVjNzg4XHViMjk0IFx1Y2U3OFx1Yzc1OCBcdWM3MDRcdWM1ZDAgXHViMTkzXHVjNWVjXHVjOWMwXHVhYzhjIFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjYzNkXHVjNjAxXHVjNzc0XHVhYzAwIFx1ZDU1OFx1YWNlMFx1Yzc4OFx1YjI5NCBcdWQxNGNcdWQyYjhcdWI5YWNcdWMyYTRcdWIyOTQgXHVjNzdjXHViYzE4XHVjODAxXHVjNzc4IFx1ZDE0Y1x1ZDJiOFx1YjlhY1x1YzJhNFx1YzY0MCBcdWM1N2RcdWFjMDQgXHVhZGRjXHVjZTU5XHVjNzc0IFx1YjJlNFx1Yjk3NFx1YjJlNC4gXHViZTE0XHViODVkXHVjNzc0IFx1YjVhOFx1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YmUxNFx1Yjg1ZFx1YWNmYyBcdWJlMTRcdWI4NWQgXHViNjEwXHViMjk0IFx1YmUxNFx1Yjg1ZFx1YWNmYyBcdWJjMTRcdWIyZTUgXHVjMGFjXHVjNzc0XHVjNWQwIFx1Y2M0NFx1YzZjY1x1YzgzOFx1Yzc4OFx1YzljMCBcdWM1NGFcdWM3NDAgXHVjZTc4XHVjNzc0IFx1YzBkZFx1YWUzMFx1YmE3NCBcdWM1NDhcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NzQgXHVhYzAxIFx1Y2U3OFx1Yzc1OCBcdWIxOTJcdWM3NzRcdWFjMDAgMiwgMSwgMSwgMSwgMCwgMVx1Yzc3OCBcdWFjYmRcdWM2YjBcdWI5N2MgXHVjMGRkXHVhYzAxXHVkNTc0XHViY2Y0XHVjNzkwLiBcdWJlMTRcdWI4NWQgNVx1YmM4OFx1Yzc0NCBcdWI1YThcdWM1YjRcdWI3MjhcdWI5YWNcdWIyOTQgXHViYzI5XHViYzk1XHVjNzU4IFx1YzIxOFx1YjI5NCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzc0IFx1YjJlNFx1YzEyZlx1YWMwMFx1YzljMFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC90ZXQyLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjIzNnB4OyB3aWR0aDo0ODFweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWQxNGNcdWQyYjhcdWI5YWNcdWMyYTQgXHVkNTQ0XHViNGRjXHVjNzU4IFx1YWMwMSBcdWNlNzhcdWM3NTggXHViMTkyXHVjNzc0XHVjNjQwIFx1YjVhOFx1YzViNFx1YjcyOFx1YjgyNFx1YzU3YyBcdWQ1NThcdWIyOTQgXHViZTE0XHViODVkXHVjNzU4IFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHViZTE0XHViODVkXHVjNzQ0IFx1YjE5M1x1YjI5NCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIENcdWM2NDAgXHViNWE4XHVjNWI0XHViNzI4XHViOWFjXHViMjk0IFx1YmUxNFx1Yjg1ZFx1Yzc1OCBcdWJjODhcdWQ2MzggUFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgQyAmbGU7IDEwMCwgMSAmbGU7IFAgJmxlOyA3KTxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWNlNzhcdWM3NTggXHViMTkyXHVjNzc0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMTkyXHVjNzc0XHViMjk0IDBcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YWNlMCwgMTAwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjNzkwXHVjNWYwXHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViZTE0XHViODVkXHVjNzQ0IFx1YjVhOFx1YzViNFx1YjcyOFx1YjlhY1x1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NTggXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzMDE5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVEVUUklTIiwiZGVzY3JpcHRpb24iOiI8cD5UZXRyaXMgaXMgYSBwb3B1bGFyIGNvbXB1dGVyIGdhbWUgcGxheWVkIGluIGEgZmllbGQgY29uc2lzdGluZyBvZiBDIGNvbHVtbnMgYW5kIGFuIHVubGltaXRlZCBudW1iZXIgb2Ygcm93cy4gSW4gb25lIG1vdmUsIG9uZSBvZiB0aGUgZm9sbG93aW5nIHNldmVuIHBpZWNlcyBpcyBkcm9wcGVkIGludG8gdGhlIGZpZWxkOiZuYnNwOzxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3RldDEoMSkucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTYxcHg7IHdpZHRoOjUyNHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPldoZW4gZHJvcHBpbmcgdGhlIHBpZWNlLCB0aGUgcGxheWVyIGlzIGZyZWUgdG8gcm90YXRlIHRoZSBwaWVjZSA5MCwgMTgwIG9yIDI3MCBkZWdyZWVzIGFuZCB0byBtb3ZlIGl0IGxlZnQgb3IgcmlnaHQsIGFzIGxvbmcgYXMgdGhlIHBpZWNlIHN0YXlzIGVudGlyZWx5IGluIHRoZSBmaWVsZC4gVGhlIHBpZWNlIHRoZW4gZmFsbHMgdW50aWwgaXQgc2V0dGxlcyBvbiB0aGUgYm90dG9tIG9mIHRoZSBmaWVsZCBvciBvbiBhbHJlYWR5IG9jY3VwaWVkIHNxdWFyZXMuIEluIG91ciB2YXJpYW50IG9mIFRldHJpcyB0aGUgcGllY2UgbXVzdCBmYWxsIHNvIHRoYXQgYWxsIHBhcnRzIG9mIHRoZSBwaWVjZSBhcmUgb24gdGhlIGJvdHRvbSBvZiB0aGUgZmllbGQgb3Igb24gYWxyZWFkeSBvY2N1cGllZCBzcXVhcmVzLiBJbiBvdGhlciB3b3JkcywgYWZ0ZXIgdGhlIHBpZWNlIGZhbGxzIHRoZXJlIG1heSBub3QgYmUgYSBmcmVlIHNxdWFyZSBzdWNoIHRoYXQgc29tZSBzcXVhcmUgYWJvdmUgaXQgaXMgb2NjdXBpZWQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCBsZXQgdGhlIGZpZWxkIGJlIHNpeCBjb2x1bW5zIHdpZGUgd2l0aCBpbml0aWFsIGhlaWdodHMgKHRoZSBudW1iZXIgb2YgYWxyZWFkeSBvY2N1cGllZCBzcXVhcmVzIGluIGVhY2ggY29sdW1uKSAyLCAxLCAxLCAxLCAwIGFuZCAxLiBQaWVjZSBudW1iZXIgNSBjYW4gdGhlbiBiZSBkcm9wcGVkIGludG8gdGhlIGZpZWxkIGluIGZpdmVkaWZmZXJlbnQgd2F5czombmJzcDs8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC90ZXQyLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjIzNnB4OyB3aWR0aDo0ODFweFwiIFwvPjxcL3A+XHJcblxyXG48cD5Zb3UgYXJlIGdpdmVuIHRoZSBpbml0aWFsIGhlaWdodHMgb2YgYWxsIGNvbHVtbnMgYW5kIHRoZSBmaWd1cmUgdG8gYmUgZHJvcHBlZCBpbnRvIHRoZSBmaWVsZC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgY2FsY3VsYXRlcyB0aGUgbnVtYmVyIG9mIGRpZmZlcmVudCB3YXlzIHRvIGRvIHRoaXMsIGkuZS4gdGhlIG51bWJlciBvZiBkaWZmZXJlbnQgZmllbGQgY29uZmlndXJhdGlvbnMgdGhhdCBjYW4gYmUgYWNoaWV2ZWQgYnkgZHJvcHBpbmcgdGhlIHBpZWNlLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdHdvIGludGVnZXJzIEMgYW5kIFAsIDEgJmxlOyBDICZsZTsgMTAwLCAxICZsZTsgUCAmbGU7IDcsIHRoZSBudW1iZXIgb2YgY29sdW1ucyBhbmQgdGhlIG51bWJlciBvZiB0aGUgcGllY2UgdG8gYmUgZHJvcHBlZC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zIEMgaW50ZWdlcnMgc2VwYXJhdGVkIGJ5IHNpbmdsZSBzcGFjZXMsIGVhY2ggYmV0d2VlbiAwIGFuZCAxMDAsIGluY2x1c2l2ZS4gVGhlc2UgYXJlIHRoZSBpbml0aWFsIGhlaWdodHMgb2YgdGhlIGNvbHVtbnMuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IG9uIGEgc2luZ2xlIGxpbmUgdGhlIG51bWJlciBvZiBkaWZmZXJlbnQgd2F5cyB0byBkcm9wIHRoZSBwaWVjZSBpbiB0aGUgZmllbGQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==