Cow Poetry

농부 존은 모르지만, 베시는 예술을 무척 좋아한다. 최근에는 위대한 시인 여럿을 공부하기 시작했고, 이제 직접 시를 써 보고 싶어 한다.

베시는 $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로 나눈 나머지를 출력한다.

이 예에서 베시는 세 단어를 알고 있다. 처음 두 단어는 서로 운을 맞추고 길이가 각각 세 음절과 네 음절이며, 마지막 단어는 세 음절이고 다른 단어와 운을 맞추지 않는다. 베시는 각 행이 열 음절이고 첫 행과 마지막 행이 운을 맞추는 세 행짜리 시를 쓰려고 한다. 이런 시는 960개 있다. 유효한 시의 한 예는 다음과 같다(1, 2, 3은 각각 첫 번째, 두 번째, 세 번째 단어를 나타낸다): 121 123 321