고대 문자 해독

고고학자 포드 트렁킹스(Mr. Ford Trunkings)는 아프리카 깊은 곳에서 고대 벨룰루(Velulu) 부족의 유적을 발견했다. 벨룰루 부족은 당대 기준으로 매우 발전된 문명을 이루었고 심지어 자신들만의 문자까지 가지고 있었지만, 약 2만 년 전의 빙하기로 문명이 무너지면서 그들의 기록은 거의 사라지고 말았다.

당신의 임무는 살아남은 벨룰루 문헌을 해독하는 것이다. 문제는 벨루루 문자에는 띄어쓰기가 전혀 없다는 점이다. 모든 문헌은 단어들이 전부 이어 붙은, 끊김 없는 하나의 긴 글자열로 적혀 있다.

연구진은 이미 이 언어의 사전 초안을 만들어 두었다. 하지만 문헌을 사전에 있는 단어들로 나누는 방법만 세어도, 웬만한 길이의 문헌이라면 그 경우의 수가 엄청나게 많아진다. 그래서 연구진은 한 문장 안에서 품사가 나타날 수 있는 순서를 규정하는 문장 구성 규칙들도 함께 복원했다.

사전과 이 규칙들을 함께 사용하여, 주어진 문헌을 해석할 수 있는 방법의 수를 구하여라.

첫 번째 줄에 세 정수 $n$, $m$, $k$가 주어진다 ($1 \le n \le 5000$, $1 \le m \le 10$, $1 \le k \le 10$). 각각 사전에 있는 단어의 수, 문장 구성 규칙의 수, 서로 다른 품사의 수이다.

다음 $n$개의 줄에는 각각 하나의 단어가 설명된다. 각 줄은 단어(20글자 미만의 비어 있지 않은 영어 소문자 문자열)로 시작하고, 이어서 정수 $k_i$ ($1 \le k_i \le 10$)와 그 단어가 나타낼 수 있는 품사 번호 $k_i$개 $a_{i1} < a_{i2} < \dots < a_{i k_i}$ ($1 \le a_{ij} \le k$)가 엄격히 증가하는 순서로 주어진다. 각 단어는 정확히 한 번씩만 나타나며, 단어들은 임의의 순서로 나열된다.

그다음 $m$개의 줄에는 각각 하나의 구성 규칙이 주어진다. 각 줄은 그 유형의 문장에 들어가는 단어의 수 $l_i$ ($1 \le l_i \le 10$)로 시작하고, 이어서 각 위치에 요구되는 품사 번호 $l_i$개 $b_{i1}, b_{i2}, \dots, b_{i l_i}$ ($1 \le b_{ij} \le k$)가 순서대로 주어진다. 같은 규칙이 두 번 나오지는 않는다.

마지막 줄에는 해독할 문헌이 주어진다. 1000글자 미만의 비어 있지 않은 영어 소문자 문자열이다.

문헌을 해석하는 서로 다른 방법의 수를 한 줄에 출력한다. 그 수가 $10^{18}$보다 크면 대신 TOO MANY를 출력한다. 문헌을 전혀 해석할 수 없으면 0을 출력한다.

해석(parsing)은 다음으로 이루어진다.

1. 문헌을, 모두 사전에 들어 있는 단어들의 나열로 분할한다.
2. 그 단어들을 순서를 유지한 채 하나 이상의 연속된 문장으로 묶는다.
3. 각 문장마다, 그 문장과 단어 수가 정확히 같고 매 위치에서 그 자리의 단어가 규칙이 요구하는 품사를 나타낼 수 있는 구성 규칙을 하나 선택한다.

두 해석은 단어 분할, 문장으로 묶는 방법, 또는 어느 한 문장에 선택한 규칙이 서로 다르면 다른 해석으로 간주한다. (특히 똑같은 단어 나열이라도 그것이 만족하는 구성 규칙마다 각각 한 번씩 센다.)