시 쓰기

가영은 예술계의 큰 후원자입니다! 최근에 그녀는 많은 위대한 시인들을 공부하기 시작하였고, 이제 그녀는 스스로 시를 쓰고자 합니다.

가영은 $N$ ($1 \leq N \leq 5000$) 개의 단어를 알고 있으며, 그녀는 이 단어들을 배열하여 시를 쓰고자 합니다. 가영은 각 단어의 길이를 음절로, 그리고 '운'에 따라 그들을 분류하였습니다. 모든 단어는 같은 '운' 분류에 속한 다른 단어들과만 운이 맞습니다.

가영의 시는 각각 $M$ 행 ($1 \leq M \leq 10^5$)을 포함하며, 각 행은 $K$ ($1 \leq K \leq 5000$) 개의 음절로 구성되어야 합니다. 추가로, 가영의 시는 특정한 운의 패턴에 따라 구성되어야 합니다.

가영은 주어진 제약 조건을 만족하는 다양한 시를 얼마나 많이 쓸 수 있는지 알고 싶어합니다.

첫 번째 입력 행에는 $N$, $M$, $K$가 있습니다.

다음 $N$개의 입력 행 각각에는 두 개의 숫자 $s_i$ ($1 \leq s_i \leq K$)와 $c_i$ ($1 \leq c_i \leq N$)가 있습니다. 이것은 가영이 음절 길이 $s_i$의 단어를 '운' 분류 $c_i$에서 알고 있다는 것을 나타냅니다.

마지막 $M$개의 입력 행은 가영이 원하는 운의 패턴을 설명하고, 각각에는 한 개의 대문자 $e_i$가 있습니다. 모든 $e_i$ 값이 같은 행은 반드시 같은 '운' 분류에 속한 단어로 끝나야 합니다. 서로 다른 $e_i$ 값의 행은 반드시 서로 다른 '운' 분류에 속한 단어로 끝나야 하는 것은 아닙니다.

주어진 제약 조건을 만족하는 가영이 쓸 수 있는 시의 수를 출력하십시오. 이 수는 매우 클 수 있기 때문에, 1,000,000,007로 나눈 나머지를 계산해 주십시오.