시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 23 5 5 50.000%

문제

다음은 류원룡의 말이다.

나는 음악을 사랑하기 때문에, 항상 음악을 듣는다. 나는 많은 곡을 소장하고 있고, 음악을 매번 곡을 선택하는 것보다, 셔플로 (무작위로) 듣는다. 그러나 나는 다른 장르의 음악도 듣지만, 어떤 것들은 서로 맞지 않는다. (예를 들어, 조용한 클래식을 듣다가, 갑자기 쏘리쏘리와 같이 시끄러운 가요가 나오는 것은 좀 불편하다) 따라서, 나는 다음과 같은 룰을 적용해서 셔플을 하게 하는 프로그램을 작성하려고 한다. 룰은 다음과 같다.

나는 여러 개의 장르를 정의해 놓았고, 모든 곡은 하나의 장르에 속한다. 그리고 나는 어떤 장르가 서로 맞는지도 정해놓았다. (서로 맞다는 말은 i라는 장르가 j와 맞다면, i란 장르의 노래를 듣고, j를 듣는것은 괜찮다는 것, 서로 맞지 않으면, i란 장르의 노래를 듣고, j란 장르의 노래를 듣는것은 안된다는 것)

나의 프로그램은 다음과 같이 작동한다.

처음에 하나의 곡을 랜덤하게 재생한다. 그 곡이 끝나면, 그 곡의 장르와 맞는 곳을 랜덤하게 선택해서, 그 곡을 재생한다. 같은 곡은 여러번 재생될 수도 있고, 연속해서 재생하는 것도 가능한다.

나의 프로그램을 이용해서 재생할 수 있는 곡의 순서 중 그 길이가 A보다 크거나 같고, B보다 작거나 같은 것의 경우의 수를 출력하는 프로그램을 작성하시오.
 

입력

첫째 줄에 곡의 개수 N이 주어진다. 곡의 개수는 1000보다 작거나 같은 자연수이다. 둘째 줄 부터 N개의 줄에는 각 곡의 장르번호와 곡의 길이가 주어진다. 다음 줄에는 장르의 개수 M이 주어진다. M은 9보다 작거나 같은 자연수이고, 장르 번호는 0부터 M-1까지 이다. 곡의 길이는 9보다 작거나 같은 자연수이다. 다음 줄에는 서로 맞는 장르가 인접행렬 형식으로 주어진다. Y는 서로 맞는 장르, N은 아니다. 이 때, 이 인접행렬을 T라고 했을 때, T[i][i] = ‘Y’이다. 마지막 줄에는 A와 B가 주어진다. B는 A보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다.

출력

곡의 순서 중 그 길이가 A보다 크거나 같고, B보다 작거나 같은 것의 경우의 수를 600921647로 나눈 나머지를 출력한다.

예제 입력

3
0 3
1 2
0 2
2
YY
YY
2 4

예제 출력

7

힌트

출처