시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 158 34 25 37.879%

문제

영 다이어그램이란 박스를 다음과 같은 조건에 따라서 배열한 것이다.

  • 박스는 각각의 행과 열에 대해서 연속적이어야 한다.
  • 모든 행은 모두 가장 왼쪽을 기준으로 정렬되어 있어야 한다.
  • 각각의 행은 바로 위에 있는 행보다 길 수 없다.

다음은 영 다이어그램의 예시이다.

영 태블로는 영 다이어그램에 아래와 같은 조건을 지키면서 수를 채운 것이다.

  • 각각의 박스에는 1과 N을 포함하는 그 사이의 정수가 채워져 있다.
  • 각 박스에 적혀있는 정수는 왼쪽에 있는 정수보다 크거나 같아야 한다.
  • 각 박스에 적혀있는 정수는 위에 있는 정수보다 커야 한다.

N = 3인 경우 아래 그림은 가능한 영 태블로의 예시이다.

N과 영 다이어그램의 형태가 주어졌을 때, 영 태블로를 만드는 방법의 수를 구하는 프로그램을 작성하시오.

입력

각각의 테스트 케이스는 두 줄로 이루어져 있다. 각 테스트 케이스의 첫째 줄은 영 다이어그램을 나타낸다. 첫 번째로 주어지는 수 k는 1 ≤ k ≤ 7을 나타내며, 행의 개수를 나타낸다. 다음 k개의 정수는 각 행에 있는 박스의 개수 l1, l2, ... , lk이며, 7 ≥ l1 ≥ l2 ≥ ··· ≥ lk ≥ 1을 만족한다. 둘째 줄에는 N이 주어지고, k ≤ N ≤ 7을 만족한다.

출력

각각의 테스트 케이스마다 만들 수 있는 영 태블로의 개수를 출력한다.

예제 입력 1

1 1
1
1 1
2
2 2 1
4
4 3 2 1 1
4

예제 출력 1

1
2
20
20
W3sicHJvYmxlbV9pZCI6Ijk2NDYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIyZTRcdWM3NzRcdWM1YjRcdWFkZjhcdWI3YThcdWFjZmMgXHVkMGRjXHViZTE0XHViODVjIiwiZGVzY3JpcHRpb24iOiI8cD48c3BhbiBzdHlsZT1cImxpbmUtaGVpZ2h0OjEuNmVtXCI+XHVjNjAxIFx1YjJlNFx1Yzc3NFx1YzViNFx1YWRmOFx1YjdhOFx1Yzc3NFx1Yjc4MCBcdWJjMTVcdWMyYTRcdWI5N2MgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWM4NzBcdWFjNzRcdWM1ZDAgXHViNTMwXHViNzdjXHVjMTFjIFx1YmMzMFx1YzVmNFx1ZDU1YyBcdWFjODNcdWM3NzRcdWIyZTQuPFwvc3Bhbj48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWJjMTVcdWMyYTRcdWIyOTQgXHVhYzAxXHVhYzAxXHVjNzU4IFx1ZDU4OVx1YWNmYyBcdWM1ZjRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjIFx1YzVmMFx1YzE4ZFx1YzgwMVx1Yzc3NFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YmFhOFx1YjRlMCBcdWQ1ODlcdWM3NDAgXHViYWE4XHViNDUwIFx1YWMwMFx1YzdhNSBcdWM2N2NcdWNhYmRcdWM3NDQgXHVhZTMwXHVjOTAwXHVjNzNjXHViODVjIFx1YzgxNVx1YjgyY1x1YjQxOFx1YzViNCBcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWFjMDFcdWFjMDFcdWM3NTggXHVkNTg5XHVjNzQwIFx1YmMxNFx1Yjg1YyBcdWM3MDRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1ZDU4OVx1YmNmNFx1YjJlNCBcdWFlMzggXHVjMjE4IFx1YzVjNlx1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWIyZTRcdWM3NGNcdWM3NDAgXHVjNjAxIFx1YjJlNFx1Yzc3NFx1YzViNFx1YWRmOFx1YjdhOFx1Yzc1OCBcdWM2MDhcdWMyZGNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXMyXC9kbnQxLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0Ojc3cHg7IGxpbmUtaGVpZ2h0OjIwLjhweDsgb3BhY2l0eTowLjk7IHRleHQtYWxpZ246Y2VudGVyOyB3aWR0aDozNTZweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWM2MDEgXHVkMGRjXHViZTE0XHViODVjXHViMjk0IFx1YzYwMSBcdWIyZTRcdWM3NzRcdWM1YjRcdWFkZjhcdWI3YThcdWM1ZDAgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWM4NzBcdWFjNzRcdWM3NDQgXHVjOWMwXHVkMGE0XHViYTc0XHVjMTFjIFx1YzIxOFx1Yjk3YyBcdWNjNDRcdWM2YjQgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1YWMwMVx1YWMwMVx1Yzc1OCBcdWJjMTVcdWMyYTRcdWM1ZDBcdWIyOTQgMVx1YWNmYyBOXHVjNzQ0IFx1ZDNlY1x1ZDU2OFx1ZDU1OFx1YjI5NCBcdWFkZjggXHVjMGFjXHVjNzc0XHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWNjNDRcdWM2Y2NcdWM4MzggXHVjNzg4XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWFjMDEgXHViYzE1XHVjMmE0XHVjNWQwIFx1YzgwMVx1ZDYwMFx1Yzc4OFx1YjI5NCBcdWM4MTVcdWMyMThcdWIyOTQgXHVjNjdjXHVjYWJkXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWM4MTVcdWMyMThcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YzU0NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YWMwMSBcdWJjMTVcdWMyYTRcdWM1ZDAgXHVjODAxXHVkNjAwXHVjNzg4XHViMjk0IFx1YzgxNVx1YzIxOFx1YjI5NCBcdWM3MDRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzgxNVx1YzIxOFx1YmNmNFx1YjJlNCBcdWNlZTRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPk4gPSAzXHVjNzc4IFx1YWNiZFx1YzZiMCBcdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjXHVjNzQwIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWM2MDEgXHVkMGRjXHViZTE0XHViODVjXHVjNzU4IFx1YzYwOFx1YzJkY1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlczJcL2RudDIucG5nXCIgc3R5bGU9XCJoZWlnaHQ6NjJweDsgbGluZS1oZWlnaHQ6MjAuOHB4OyBvcGFjaXR5OjAuOTsgdGV4dC1hbGlnbjpjZW50ZXI7IHdpZHRoOjQ1MXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPk5cdWFjZmMgXHVjNjAxIFx1YjJlNFx1Yzc3NFx1YzViNFx1YWRmOFx1YjdhOFx1Yzc1OCBcdWQ2MTVcdWQwZGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNjAxIFx1ZDBkY1x1YmUxNFx1Yjg1Y1x1Yjk3YyBcdWI5Y2NcdWI0ZGNcdWIyOTQgXHViYzI5XHViYzk1XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YjQ1MCBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1Yzc0MCBcdWM2MDEgXHViMmU0XHVjNzc0XHVjNWI0XHVhZGY4XHViN2E4XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC4gXHVjY2FiIFx1YmM4OFx1YzlmOFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgXHVjMjE4IGtcdWIyOTQgMSAmbGU7IGsgJmxlOyA3XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiNFx1YmE3MCwgXHVkNTg5XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuIFx1YjJlNFx1Yzc0YyBrXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1YjI5NCBcdWFjMDEgXHVkNTg5XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWJjMTVcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4Jm5ic3A7bDxzdWI+MTxcL3N1Yj4sIGw8c3ViPjI8XC9zdWI+LCAuLi4gLCBsPHN1Yj5rPFwvc3ViPlx1Yzc3NFx1YmE3MCwgNyAmZ2U7IGw8c3ViPjE8XC9zdWI+Jm5ic3A7JmdlOyBsPHN1Yj4yPFwvc3ViPiZuYnNwOyZnZTsgJm1pZGRvdDsmbWlkZG90OyZtaWRkb3Q7ICZnZTsgbDxzdWI+azxcL3N1Yj4mbmJzcDsmZ2U7IDFcdWM3NDQgXHViOWNjXHVjODcxXHVkNTVjXHViMmU0LiBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWMwXHVhY2UwLCBrICZsZTsgTiAmbGU7IDdcdWM3NDQgXHViOWNjXHVjODcxXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzYwMSBcdWQwZGNcdWJlMTRcdWI4NWNcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI5NjQ2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRGlhZ3JhbXMgJiBUYWJsZWF1eCIsImRlc2NyaXB0aW9uIjoiPHA+QSBZb3VuZyBkaWFncmFtIGlzIGFuIGFycmFuZ2VtZW50IG9mIGJveGVzIGluIHJvd3MgYW5kIGNvbHVtbnMgY29uZm9ybWluZyB0byB0aGUgZm9sbG93aW5nIHJ1bGVzOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPnRoZSBib3hlcyBpbiBlYWNoIHJvdyBhbmQgZWFjaCBjb2x1bW4gYXJlIGNvbnRpZ3VvdXMsPFwvbGk+XHJcblx0PGxpPnRoZSBsZWZ0IGJvcmRlcnMgb2YgYWxsIHJvd3MgYXJlIGFsaWduZWQsIGFuZDxcL2xpPlxyXG5cdDxsaT5lYWNoIHJvdyBpcyBub3QgbG9uZ2VyIHRoYW4gdGhlIG9uZSBhYm92ZS48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5IZXJlIGFyZSBzb21lIGV4YW1wbGVzIG9mIFlvdW5nIGRpYWdyYW1zOjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXMyXC9kbnQxLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0Ojc3cHg7IHdpZHRoOjM1NnB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkEgc2VtaS1zdGFuZGFyZCBZb3VuZyB0YWJsZWF1IGZvciBhIGdpdmVuIG51bWJlciBOIGlzIGEgWW91bmcgZGlhZ3JhbSB0aGF0IGhhcyBpdHMgYm94ZXMgZmlsbGVkIGFjY29yZGluZyB0byB0aGUgZm9sbG93aW5nIHJ1bGVzOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPkVhY2ggYm94IGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXIgYmV0d2VlbiAxIGFuZCBOLCBpbmNsdXNpdmUsPFwvbGk+XHJcblx0PGxpPmVhY2ggaW50ZWdlciBpcyBncmVhdGVyIHRoYW4gb3IgZXF1YWwgdG8gdGhlIGludGVnZXIgaW4gdGhlIGJveCB0byBpdHMgbGVmdCwgYW5kPFwvbGk+XHJcblx0PGxpPmVhY2ggaW50ZWdlciBpcyBzdHJpY3RseSBncmVhdGVyIHRoYW4gdGhlIGludGVnZXIgaW4gdGhlIGJveCBhYm92ZS48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5IZXJlIGlzIGEgbGlzdCBvZiBhbGwgc2VtaS1zdGFuZGFyZCBZb3VuZyB0YWJsZWF1eCBmb3IgTiA9IDMsIGJhc2VkIG9uIGEgcGFydGljdWxhciBZb3VuZyBkaWFncmFtOjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXMyXC9kbnQyLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjYycHg7IHdpZHRoOjQ1MXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPllvdXIgdGFzayBpcyB0byBjb3VudCBob3cgbWFueSBzZW1pLXN0YW5kYXJkIFlvdW5nIHRhYmxlYXV4IGFyZSBwb3NzaWJsZSwgYmFzZWQgb24gYSBnaXZlbiBZb3VuZyBkaWFncmFtLCB3aXRoIGEgZ2l2ZW4gTi48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkVhY2ggdGVzdCBjYXNlIGNvbnNpc3RzIG9mIHR3byBsaW5lcy4gVGhlIGZpcnN0IGxpbmUgb2YgZWFjaCB0ZXN0IGNhc2Ugc3BlY2lmaWVzIHRoZSBZb3VuZyBkaWFncmFtLiBUaGlzIGxpbmUgc3RhcnRzIHdpdGggdGhlIG51bWJlciBrIHNhdGlzZnlpbmcgMSAmbGU7IGsgJmxlOyA3LCB0aGUgbnVtYmVyIG9mIHJvd3MsIGZvbGxvd2VkIGJ5IGsgcG9zaXRpdmUgaW50ZWdlcnMgbDxzdWI+MTxcL3N1Yj4sIGw8c3ViPjI8XC9zdWI+LCAuLi4gLCBsPHN1Yj5rPFwvc3ViPi4gVGhlc2UgaW50ZWdlcnMgc3BlY2lmeSB0aGUgbnVtYmVyIG9mIGJveGVzIG9uIGVhY2ggcm93IG9mIHRoZSBZb3VuZyBkaWFncmFtLCBhbmQgdGhleSBzYXRpc2Z5IDcgJmdlOyBsPHN1Yj4xPFwvc3ViPiAmZ2U7IGw8c3ViPjI8XC9zdWI+ICZnZTsgJm1pZGRvdDsmbWlkZG90OyZtaWRkb3Q7ICZnZTsgbDxzdWI+azxcL3N1Yj4gJmdlOyAxLiBUaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgdGhlIGludGVnZXIgTiwgc2F0aXNmeWluZyBrICZsZTsgTiAmbGU7IDcuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBwcmludCBvbmUgbGluZSBjb250YWluaW5nIHRoZSBudW1iZXIgb2Ygc2VtaS1zdGFuZGFyZCBZb3VuZyB0YWJsZWF1eCBiYXNlZCBvbiB0aGUgZ2l2ZW4gWW91bmcgZGlhZ3JhbSwgd2l0aCB0aGUgZ2l2ZW4gTi48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=