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

문제

테트리스는 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

예제 입력 2

5 1
0 0 0 0 0

예제 출력 2

7

예제 입력 3

9 4
4 3 5 4 6 5 7 6 6

예제 출력 3

1
W3sicHJvYmxlbV9pZCI6IjMwMTkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQxNGNcdWQyYjhcdWI5YWNcdWMyYTQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDE0Y1x1ZDJiOFx1YjlhY1x1YzJhNFx1YjI5NCBDXHVjNWY0IFx1ZDU0NFx1YjRkY1x1YzcwNFx1YzVkMFx1YzExYyBcdWQ1MGNcdWI4MDhcdWM3NzRcdWQ1NThcdWIyOTQgXHVjNzIwXHViYTg1XHVkNTVjIFx1YWM4Y1x1Yzc4NFx1Yzc3NFx1YjJlNC4gXHVkNTQ0XHViNGRjXHVjNzU4IFx1ZDU4OVx1Yzc1OCBcdWMyMThcdWIyOTQgXHViYjM0XHVkNTVjXHVkNTU4XHViMmU0LiBcdWQ1NWMgXHViYzg4IFx1YzZjMFx1YzljMVx1Yzc3YyBcdWI1NGMsIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVjNzdjXHVhY2YxXHVhYzAwXHVjOWMwIFx1YmUxNFx1Yjg1ZCBcdWM5MTEgXHVkNTU4XHViMDk4XHViOTdjIFx1ZDU0NFx1YjRkY1x1YzVkMCBcdWI1YThcdWM1YjRcdWI3MjhcdWI5YjQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC8yNWQ2MjRhYi0zYzgxLTQ5MDUtOGYzZi1mYjI2YmYxODE5ZWRcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDQ3M3B4OyBoZWlnaHQ6IDE0MXB4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5cdWJlMTRcdWI4NWRcdWM3NDQgXHViNWE4XHVjNWI0XHViNzI4XHViOWFjXHVhZTMwIFx1YzgwNFx1YzVkMCwgXHVkNTBjXHViODA4XHVjNzc0XHVjNWI0XHViMjk0IFx1YmUxNFx1Yjg1ZFx1Yzc0NCA5MCwgMTgwLCAyNzBcdWIzYzQgXHVkNjhjXHVjODA0XHVjMmRjXHVkMGE0XHVhYzcwXHViMDk4IFx1Yzg4Y1x1YzZiMFx1Yjg1YyBcdWM2YzBcdWM5YzFcdWM3N2MgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWJlMTRcdWI4NWRcdWM3NzQgXHVkNTQ0XHViNGRjXHViOTdjIFx1YmM5N1x1YzViNFx1YjA5OFx1YzljMCBcdWM1NGFcdWM3M2NcdWJhNzQgXHViNDFjXHViMmU0LiBcdWJlMTRcdWI4NWRcdWM3NDQgXHVkNTQ0XHViNGRjXHVjNzU4IFx1YmMxNFx1YjJlNVx1Yzc3NFx1YjA5OCBcdWM3NzRcdWJiZjggXHVjYzQ0XHVjNmNjXHVjODM4XHVjNzg4XHViMjk0IFx1Y2U3OFx1Yzc1OCBcdWM3MDRcdWM1ZDAgXHViMTkzXHVjNWVjXHVjOWMwXHVhYzhjIFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjYzNkXHVjNjAxXHVjNzc0XHVhYzAwIFx1ZDU1OFx1YWNlMFx1Yzc4OFx1YjI5NCBcdWQxNGNcdWQyYjhcdWI5YWNcdWMyYTRcdWIyOTQgXHVjNzdjXHViYzE4XHVjODAxXHVjNzc4IFx1ZDE0Y1x1ZDJiOFx1YjlhY1x1YzJhNFx1YzY0MCBcdWM1N2RcdWFjMDQgXHVhZGRjXHVjZTU5XHVjNzc0IFx1YjJlNFx1Yjk3NFx1YjJlNC4gXHViZTE0XHViODVkXHVjNzc0IFx1YjVhOFx1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YmUxNFx1Yjg1ZFx1YWNmYyBcdWJlMTRcdWI4NWQgXHViNjEwXHViMjk0IFx1YmUxNFx1Yjg1ZFx1YWNmYyBcdWJjMTRcdWIyZTUgXHVjMGFjXHVjNzc0XHVjNWQwIFx1Y2M0NFx1YzZjY1x1YzgzOFx1Yzc4OFx1YzljMCBcdWM1NGFcdWM3NDAgXHVjZTc4XHVjNzc0IFx1YzBkZFx1YWUzMFx1YmE3NCBcdWM1NDggXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzc0IFx1YWMwMSBcdWNlNzhcdWM3NTggXHViMTkyXHVjNzc0XHVhYzAwIDIsIDEsIDEsIDEsIDAsIDFcdWM3NzggXHVhY2JkXHVjNmIwXHViOTdjIFx1YzBkZFx1YWMwMVx1ZDU3NFx1YmNmNFx1Yzc5MC4gXHViZTE0XHViODVkIDVcdWJjODhcdWM3NDQgXHViNWE4XHVjNWI0XHViNzI4XHViOWFjXHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWMyMThcdWIyOTQgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1Yzc3NCBcdWIyZTRcdWMxMmZcdWFjMDBcdWM5YzBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvZDFiZTg3OGUtZTdlZS00YTAwLTk0Y2EtYTlkODNlNzA0ZDMyXC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiA0MzZweDsgaGVpZ2h0OiAyMDhweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVkMTRjXHVkMmI4XHViOWFjXHVjMmE0IFx1ZDU0NFx1YjRkY1x1Yzc1OCBcdWFjMDEgXHVjZTc4XHVjNzU4IFx1YjE5Mlx1Yzc3NFx1YzY0MCBcdWI1YThcdWM1YjRcdWI3MjhcdWI4MjRcdWM1N2MgXHVkNTU4XHViMjk0IFx1YmUxNFx1Yjg1ZFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YmUxNFx1Yjg1ZFx1Yzc0NCBcdWIxOTNcdWIyOTQgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWJjMjlcdWJjOTVcdWM3NTggXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBDXHVjNjQwIFx1YjVhOFx1YzViNFx1YjcyOFx1YjlhY1x1YjI5NCBcdWJlMTRcdWI4NWRcdWM3NTggXHViYzg4XHVkNjM4IFBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IEMgJmxlOyAxMDAsIDEgJmxlOyBQICZsZTsgNyk8XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHVjZTc4XHVjNzU4IFx1YjE5Mlx1Yzc3NFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjE5Mlx1Yzc3NFx1YjI5NCAwXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWM3MFx1YjA5OCBcdWFjMTlcdWFjZTAsIDEwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YmUxNFx1Yjg1ZFx1Yzc0NCBcdWI1YThcdWM1YjRcdWI3MjhcdWI5YWNcdWIyOTQgXHViYzI5XHViYzk1XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMzAxOSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRFVFJJUyIsImRlc2NyaXB0aW9uIjoiPHA+VGV0cmlzIGlzIGEgcG9wdWxhciBjb21wdXRlciBnYW1lIHBsYXllZCBpbiBhIGZpZWxkIGNvbnNpc3Rpbmcgb2YgQyBjb2x1bW5zIGFuZCBhbiB1bmxpbWl0ZWQgbnVtYmVyIG9mIHJvd3MuIEluIG9uZSBtb3ZlLCBvbmUgb2YgdGhlIGZvbGxvd2luZyBzZXZlbiBwaWVjZXMgaXMgZHJvcHBlZCBpbnRvIHRoZSBmaWVsZDombmJzcDs8XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC8yNWQ2MjRhYi0zYzgxLTQ5MDUtOGYzZi1mYjI2YmYxODE5ZWRcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDQ3M3B4OyBoZWlnaHQ6IDE0MXB4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5XaGVuIGRyb3BwaW5nIHRoZSBwaWVjZSwgdGhlIHBsYXllciBpcyBmcmVlIHRvIHJvdGF0ZSB0aGUgcGllY2UgOTAsIDE4MCBvciAyNzAgZGVncmVlcyBhbmQgdG8gbW92ZSBpdCBsZWZ0IG9yIHJpZ2h0LCBhcyBsb25nIGFzIHRoZSBwaWVjZSBzdGF5cyBlbnRpcmVseSBpbiB0aGUgZmllbGQuIFRoZSBwaWVjZSB0aGVuIGZhbGxzIHVudGlsIGl0IHNldHRsZXMgb24gdGhlIGJvdHRvbSBvZiB0aGUgZmllbGQgb3Igb24gYWxyZWFkeSBvY2N1cGllZCBzcXVhcmVzLiBJbiBvdXIgdmFyaWFudCBvZiBUZXRyaXMgdGhlIHBpZWNlIG11c3QgZmFsbCBzbyB0aGF0IGFsbCBwYXJ0cyBvZiB0aGUgcGllY2UgYXJlIG9uIHRoZSBib3R0b20gb2YgdGhlIGZpZWxkIG9yIG9uIGFscmVhZHkgb2NjdXBpZWQgc3F1YXJlcy4gSW4gb3RoZXIgd29yZHMsIGFmdGVyIHRoZSBwaWVjZSBmYWxscyB0aGVyZSBtYXkgbm90IGJlIGEgZnJlZSBzcXVhcmUgc3VjaCB0aGF0IHNvbWUgc3F1YXJlIGFib3ZlIGl0IGlzIG9jY3VwaWVkLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgbGV0IHRoZSBmaWVsZCBiZSBzaXggY29sdW1ucyB3aWRlIHdpdGggaW5pdGlhbCBoZWlnaHRzICh0aGUgbnVtYmVyIG9mIGFscmVhZHkgb2NjdXBpZWQgc3F1YXJlcyBpbiBlYWNoIGNvbHVtbikgMiwgMSwgMSwgMSwgMCBhbmQgMS4gUGllY2UgbnVtYmVyIDUgY2FuIHRoZW4gYmUgZHJvcHBlZCBpbnRvIHRoZSBmaWVsZCBpbiBmaXZlZGlmZmVyZW50IHdheXM6Jm5ic3A7PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvZDFiZTg3OGUtZTdlZS00YTAwLTk0Y2EtYTlkODNlNzA0ZDMyXC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiA0MzZweDsgaGVpZ2h0OiAyMDhweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+WW91IGFyZSBnaXZlbiB0aGUgaW5pdGlhbCBoZWlnaHRzIG9mIGFsbCBjb2x1bW5zIGFuZCB0aGUgZmlndXJlIHRvIGJlIGRyb3BwZWQgaW50byB0aGUgZmllbGQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IGNhbGN1bGF0ZXMgdGhlIG51bWJlciBvZiBkaWZmZXJlbnQgd2F5cyB0byBkbyB0aGlzLCBpLmUuIHRoZSBudW1iZXIgb2YgZGlmZmVyZW50IGZpZWxkIGNvbmZpZ3VyYXRpb25zIHRoYXQgY2FuIGJlIGFjaGlldmVkIGJ5IGRyb3BwaW5nIHRoZSBwaWVjZS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHR3byBpbnRlZ2VycyBDIGFuZCBQLCAxICZsZTsgQyAmbGU7IDEwMCwgMSAmbGU7IFAgJmxlOyA3LCB0aGUgbnVtYmVyIG9mIGNvbHVtbnMgYW5kIHRoZSBudW1iZXIgb2YgdGhlIHBpZWNlIHRvIGJlIGRyb3BwZWQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBjb250YWlucyBDIGludGVnZXJzIHNlcGFyYXRlZCBieSBzaW5nbGUgc3BhY2VzLCBlYWNoIGJldHdlZW4gMCBhbmQgMTAwLCBpbmNsdXNpdmUuIFRoZXNlIGFyZSB0aGUgaW5pdGlhbCBoZWlnaHRzIG9mIHRoZSBjb2x1bW5zLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCBvbiBhIHNpbmdsZSBsaW5lIHRoZSBudW1iZXIgb2YgZGlmZmVyZW50IHdheXMgdG8gZHJvcCB0aGUgcGllY2UgaW4gdGhlIGZpZWxkLiZuYnNwOzxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d