시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 246 96 82 39.234%

문제

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

힌트

W3sicHJvYmxlbV9pZCI6IjMwMTkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQxNGNcdWQyYjhcdWI5YWNcdWMyYTQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDE0Y1x1ZDJiOFx1YjlhY1x1YzJhNFx1YjI5NCBDXHVjNWY0IFx1ZDU0NFx1YjRkY1x1YzcwNFx1YzVkMFx1YzExYyBcdWQ1MGNcdWI4MDhcdWM3NzRcdWQ1NThcdWIyOTQgXHVjNzIwXHViYTg1XHVkNTVjIFx1YWM4Y1x1Yzc4NFx1Yzc3NFx1YjJlNC4gXHVkNTQ0XHViNGRjXHVjNzU4IFx1ZDU4OVx1Yzc1OCBcdWMyMThcdWIyOTQgXHViYjM0XHVkNTVjXHVkNTU4XHViMmU0LiBcdWQ1NWMgXHViYzg4IFx1YzZjMFx1YzljMVx1Yzc3YyBcdWI1NGMsIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVjNzdjXHVhY2YxXHVhYzAwXHVjOWMwIFx1YmUxNFx1YjdlZCBcdWM5MTEgXHVkNTU4XHViMDk4XHViOTdjIFx1ZDU0NFx1YjRkY1x1YzVkMCBcdWI1YThcdWM1YjRcdWI3MjhcdWI5YjQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC90ZXQxKDEpLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE2MXB4OyB3aWR0aDo1MjRweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWJlMTRcdWI3ZWRcdWM3NDQgXHViNWE4XHVjNWI0XHViNzI4XHViOWFjXHVhZTMwIFx1YzgwNFx1YzVkMCwgXHVkNTBjXHViODA4XHVjNzc0XHVjNWI0XHViMjk0IFx1YmUxNFx1YjdlZFx1Yzc0NCA5MCwgMTgwLCAyNzBcdWIzYzQgXHVkNjhjXHVjODA0XHVjMmRjXHVkMGE0XHVhYzcwXHViMDk4IFx1Yzg4Y1x1YzZiMFx1Yjg1YyBcdWM2YzBcdWM5YzFcdWM3N2MgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1YjU0YywgXHViZTE0XHViN2VkXHVjNzc0IFx1ZDU0NFx1YjRkY1x1Yjk3YyBcdWJjOTdcdWM1YjRcdWIwOThcdWM5YzAgXHVjNTRhXHVjNzNjXHViYTc0IFx1YjQxY1x1YjJlNC4gXHViZTE0XHViN2VkXHVjNzQ0IFx1ZDU0NFx1YjRkY1x1Yzc1OCBcdWJjMTRcdWIyZTVcdWM3NzRcdWIwOTggXHVjNzc0XHViYmY4IFx1Y2M0NFx1YzZjY1x1YzgzOFx1Yzc4OFx1YjI5NCBcdWNlNzhcdWM3NTggXHVjNzA0XHVjNWQwIFx1YjE5M1x1YzVlY1x1YzljMFx1YWM4YyBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2MzZFx1YzYwMVx1Yzc3NFx1YWMwMCBcdWQ1NThcdWFjZTBcdWM3ODhcdWIyOTQgXHVkMTRjXHVkMmI4XHViOWFjXHVjMmE0XHViMjk0IFx1Yzc3Y1x1YmMxOFx1YzgwMVx1Yzc3OCBcdWQxNGNcdWQyYjhcdWI5YWNcdWMyYTRcdWM2NDAgXHVjNTdkXHVhYzA0IFx1YWRkY1x1Y2U1OVx1Yzc3NCBcdWIyZTRcdWI5NzRcdWIyZTQuIFx1YmUxNFx1YjdlZFx1Yzc3NCBcdWI1YThcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWJlMTRcdWI3ZWRcdWFjZmMgXHViZTE0XHViN2VkIFx1YjYxMFx1YjI5NCBcdWJlMTRcdWI3ZWRcdWFjZmMgXHViYzE0XHViMmU1IFx1YzBhY1x1Yzc3NFx1YzVkMCBcdWNjNDRcdWM2Y2NcdWM4MzhcdWM3ODhcdWM5YzAgXHVjNTRhXHVjNzQwIFx1Y2U3OFx1Yzc3NCBcdWMwZGRcdWFlMzBcdWJhNzQgXHVjNTQ4XHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzc0IFx1YWMwMSBcdWNlNzhcdWM3NTggXHViMTkyXHVjNzc0XHVhYzAwIDIsIDEsIDEsIDEsIDAsIDFcdWM3NzggXHVhY2JkXHVjNmIwXHViOTdjIFx1YzBkZFx1YWMwMVx1ZDU3NFx1YmNmNFx1Yzc5MC4gXHViZTE0XHViN2VkIDVcdWJjODhcdWM3NDQgXHViNWE4XHVjNWI0XHViNzI4XHViOWFjXHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWMyMThcdWIyOTQgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1Yzc3NCBcdWIyZTRcdWMxMmZcdWFjMDBcdWM5YzBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvdGV0Mi5wbmdcIiBzdHlsZT1cImhlaWdodDoyMzZweDsgd2lkdGg6NDgxcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVkMTRjXHVkMmI4XHViOWFjXHVjMmE0IFx1ZDU0NFx1YjRkY1x1Yzc1OCBcdWFjMDEgXHVjZTc4XHVjNzU4IFx1YjE5Mlx1Yzc3NFx1YzY0MCBcdWI1YThcdWM1YjRcdWI3MjhcdWI4MjRcdWM1N2MgXHVkNTU4XHViMjk0IFx1YmUxNFx1YjdlZFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzQgXHViNTRjLCBcdWJlMTRcdWI3ZWRcdWM3NDQgXHViMTkzXHViMjk0IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHViYzI5XHViYzk1XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgQ1x1YzY0MCBcdWI1YThcdWM1YjRcdWI3MjhcdWI5YWNcdWIyOTQgXHViZTE0XHViN2VkXHVjNzU4IFx1YmM4OFx1ZDYzOCBQXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBDICZsZTsgMTAwLCAxICZsZTsgUCAmbGU7IDcpPFwvcD5cclxuXHJcbjxwPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1Y2U3OFx1Yzc1OCBcdWIxOTJcdWM3NzRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIxOTJcdWM3NzRcdWIyOTQgMFx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVhY2UwLCAxMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWM3OTBcdWM1ZjBcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJlMTRcdWI3ZWRcdWM3NDQgXHViNWE4XHVjNWI0XHViNzI4XHViOWFjXHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMwMTkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJURVRSSVMiLCJkZXNjcmlwdGlvbiI6IjxwPlRldHJpcyBpcyBhIHBvcHVsYXIgY29tcHV0ZXIgZ2FtZSBwbGF5ZWQgaW4gYSBmaWVsZCBjb25zaXN0aW5nIG9mIEMgY29sdW1ucyBhbmQgYW4gdW5saW1pdGVkIG51bWJlciBvZiByb3dzLiBJbiBvbmUgbW92ZSwgb25lIG9mIHRoZSBmb2xsb3dpbmcgc2V2ZW4gcGllY2VzIGlzIGRyb3BwZWQgaW50byB0aGUgZmllbGQ6Jm5ic3A7PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvdGV0MSgxKS5wbmdcIiBzdHlsZT1cImhlaWdodDoxNjFweDsgd2lkdGg6NTI0cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+V2hlbiBkcm9wcGluZyB0aGUgcGllY2UsIHRoZSBwbGF5ZXIgaXMgZnJlZSB0byByb3RhdGUgdGhlIHBpZWNlIDkwLCAxODAgb3IgMjcwIGRlZ3JlZXMgYW5kIHRvIG1vdmUgaXQgbGVmdCBvciByaWdodCwgYXMgbG9uZyBhcyB0aGUgcGllY2Ugc3RheXMgZW50aXJlbHkgaW4gdGhlIGZpZWxkLiBUaGUgcGllY2UgdGhlbiBmYWxscyB1bnRpbCBpdCBzZXR0bGVzIG9uIHRoZSBib3R0b20gb2YgdGhlIGZpZWxkIG9yIG9uIGFscmVhZHkgb2NjdXBpZWQgc3F1YXJlcy4gSW4gb3VyIHZhcmlhbnQgb2YgVGV0cmlzIHRoZSBwaWVjZSBtdXN0IGZhbGwgc28gdGhhdCBhbGwgcGFydHMgb2YgdGhlIHBpZWNlIGFyZSBvbiB0aGUgYm90dG9tIG9mIHRoZSBmaWVsZCBvciBvbiBhbHJlYWR5IG9jY3VwaWVkIHNxdWFyZXMuIEluIG90aGVyIHdvcmRzLCBhZnRlciB0aGUgcGllY2UgZmFsbHMgdGhlcmUgbWF5IG5vdCBiZSBhIGZyZWUgc3F1YXJlIHN1Y2ggdGhhdCBzb21lIHNxdWFyZSBhYm92ZSBpdCBpcyBvY2N1cGllZC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIGxldCB0aGUgZmllbGQgYmUgc2l4IGNvbHVtbnMgd2lkZSB3aXRoIGluaXRpYWwgaGVpZ2h0cyAodGhlIG51bWJlciBvZiBhbHJlYWR5IG9jY3VwaWVkIHNxdWFyZXMgaW4gZWFjaCBjb2x1bW4pIDIsIDEsIDEsIDEsIDAgYW5kIDEuIFBpZWNlIG51bWJlciA1IGNhbiB0aGVuIGJlIGRyb3BwZWQgaW50byB0aGUgZmllbGQgaW4gZml2ZWRpZmZlcmVudCB3YXlzOiZuYnNwOzxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3RldDIucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjM2cHg7IHdpZHRoOjQ4MXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPllvdSBhcmUgZ2l2ZW4gdGhlIGluaXRpYWwgaGVpZ2h0cyBvZiBhbGwgY29sdW1ucyBhbmQgdGhlIGZpZ3VyZSB0byBiZSBkcm9wcGVkIGludG8gdGhlIGZpZWxkLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCBjYWxjdWxhdGVzIHRoZSBudW1iZXIgb2YgZGlmZmVyZW50IHdheXMgdG8gZG8gdGhpcywgaS5lLiB0aGUgbnVtYmVyIG9mIGRpZmZlcmVudCBmaWVsZCBjb25maWd1cmF0aW9ucyB0aGF0IGNhbiBiZSBhY2hpZXZlZCBieSBkcm9wcGluZyB0aGUgcGllY2UuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyB0d28gaW50ZWdlcnMgQyBhbmQgUCwgMSAmbGU7IEMgJmxlOyAxMDAsIDEgJmxlOyBQICZsZTsgNywgdGhlIG51bWJlciBvZiBjb2x1bW5zIGFuZCB0aGUgbnVtYmVyIG9mIHRoZSBwaWVjZSB0byBiZSBkcm9wcGVkLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgQyBpbnRlZ2VycyBzZXBhcmF0ZWQgYnkgc2luZ2xlIHNwYWNlcywgZWFjaCBiZXR3ZWVuIDAgYW5kIDEwMCwgaW5jbHVzaXZlLiBUaGVzZSBhcmUgdGhlIGluaXRpYWwgaGVpZ2h0cyBvZiB0aGUgY29sdW1ucy4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgb24gYSBzaW5nbGUgbGluZSB0aGUgbnVtYmVyIG9mIGRpZmZlcmVudCB3YXlzIHRvIGRyb3AgdGhlIHBpZWNlIGluIHRoZSBmaWVsZC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d