레이팅 미적용농부 존은 모르지만, 베시는 상당한 예술 애호가이다! 최근 베시는 위대한 시인들을 여럿 공부하기 시작했고, 이제 직접 시를 써 보려 한다.
베시는 \(N\)개의 단어 (\(1 \leq N \leq 5000\))를 알고 있으며, 이들을 배열하여 시를 짓고 싶어한다. 베시는 각 단어의 길이를 음절 수로 파악해 두었고, 단어들을 "운율 클래스"로 분류해 두었다. 각 단어는 같은 운율 클래스에 속한 다른 단어들과만 운이 맞는다.
베시의 시는 각각 \(M\)개의 행 (\(1 \leq M \leq 10^5\))으로 이루어지며, 각 행은 \(K\)개의 음절 (\(1 \leq K \leq 5000\))로 구성되어야 한다. 게다가 베시의 시는 특정한 운율 구조를 따라야 한다.
베시는 주어진 제약을 만족하는 서로 다른 시를 몇 편 쓸 수 있는지 알고 싶어한다.
출제자: Jay Leeds
출제자: Jay Leeds
입력의 첫째 줄에 \(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로 나눈 나머지를 계산하여 출력한다.
poetry.in · 출력을 쓸 파일 poetry.out3 3 10
3 1
4 1
3 2
A
B
A960In this example, Bessie knows three words. The first two words rhyme, and have lengths of three
syllables and four syllables, and the last word is three syllables long and
doesn't rhyme with the others. She wants to write a three-line poem such that each line contains ten
syllables and the first and last lines rhyme. There are 960 such poems. One example of a valid poem is the following (where 1, 2, and 3 represent the
first, second, and third words): 121 123 321