17480번 - 개구쟁이 준석이

초등학생 준석이는 영어를 배우고 있는 중이다.

개구쟁이인 준석이는 단어에서 본인이 마음에 드는 부분을 뽑아 섞어 읽고, 뽑은 부분의 알파벳 종류와 개수만 이야기한다.

준석이와 소통하고 싶어하는 진우 선생님은 준석이가 일정한 규칙을 가지고 읽는다는 것을 깨달았다.

진우 선생님이 발견한 규칙은 다음과 같다.

먼저, 준석이는 주어진 단어에서 본인이 읽고 싶은 연속된 문자열을 뽑아 다음의 규칙에 따라 새 문자열을 만든다.

1. 문자열을 반으로 나눈다. 
2. 1번 과정에서 나눠진 두 개의 문자열 중 한 쪽 문자열만 역순으로 바꾼다. 
3. 2번 과정에서 역순으로 바꾸지 않은 다른 한 쪽의 문자열을 다시 반으로 나눈다.
4. 3번 과정에서 반으로 나눈 두 개의 문자열 중 한 쪽 문자열만 역순으로 바꾼다.
5. 1 ~ 4번 과정을 반복한다.  단, 반복하는 과정에서 역순으로 바꿀 문자열은 무작위로 선택하고 선택한 문자열의 길이가 1이라면 역순으로 바꾸지 않고 끝낸다.

위의 규칙에 따라 여러 문자열들을 만들 수 있는데 만약 만들어진 문자열이 중복되면, 오직 1개만 가능한 문자열로 생각한다.

또한 반으로 나눌 문자열 S의 길이가 N이라 하면, N이 홀수일 경우 반으로 나누는 방법은 두 가지가 생긴다.

이 경우, 두 가지를 모두 가능한 방법으로 생각하며 두 가지 방법에서 발생하는 모든 경우의 수도 포함해야 한다.

이런 규칙에 따라 새 문자열을 만들고 나면 준석이는 그 문자열에 포함된 알파벳과 알파벳의 개수를 말한다. (단, 준석이가 잘못 말할 가능성은 없다.)

예를 들어, inconvenience라는 단어가 주어졌다고 하자.

준석이는 e가 2개, n이 2개, i가 1개, c가 1개라고 말한다.

준석이가 말한 조건에 따르면, 준석이가 단어 속에서 뽑은 연속된 문자열은 두 개가 될 수 있다.(enienc, nience)

예시를 위해 enienc를 봤다고 가정하자.

1. enienc를 반으로 나누면 eni와 enc가 된다.
2. eni 또는 enc를 역순으로 바꾼다. 예시에서는 enc의 순서를 역순으로 한다. (cne)
3. eni를 역순으로 바꾸지 않았으므로 eni를 반으로 나눈다. 다만, 정확히 반으로 나눌 수 없기 때문에 e ni와 en i로 두 가지 경우가 생길 수 있다. 예시에서는 e ni일 경우를 설명하겠다.
4. 만약 e를 선택한다면 eni가 되고, ni를 선택한다면 ein이 된다. 따라서, enicne 혹은 eincne가 된다.

이처럼 inconvenience라는 단어가 주어지고, 준석이가 단어 속에서 뽑은 연속된 문자열 enienc과 nience에 대하여 

준석이의 규칙에 의해 만들어진 문자열들은 eincne, einnce, einnec, enicne, ineecn, ineenc, inenec, neicne, neiecn, nieecn으로 총 10개다.

진우 선생님은 준석이와 소통을 하기 위해 준석이의 규칙에 의해 만들어질 문자열들을 모두 알아내고자 한다.

진우 선생님을 도와 주어진 단어, 준석이가 말한 알파벳과 알파벳들의 개수를 토대로 규칙에 따라 만들 수 있는 문자열들의 개수를 출력하는 프로그램을 만들자.

첫째 줄에 준석이가 말한 알파벳 종류의 개수가 주어진다. 단, 알파벳 종류의 개수는 N개(0 < N < 15)다.

둘째 줄에는 준석이가 말한 알파벳들과 각각의 개수가 주어진다. 단, 각각의 개수는 M개(0 < M < 15)다.

세번째 줄에는 알파벳 소문자로 이루어진 영어 단어가 주어진다. 단, 영어 단어의 길이는 알파벳 각각의 갯수들의 합 이상이며 15자 미만이다. 

규칙에 따라 만들 수 있는 문자열의 개수를 출력한다. 단, 중복되는 문자열일 경우 그 문자열은 1개로 취급해야 한다.