셔플
시간 제한2초메모리 제한128 MB
각 곡의 길이가 1에서 9이고 장르 전이 규칙이 주어질 때, 총 재생 시간이 A 이상 B 이하인 재생 순서의 개수를 600921647로 나눈 나머지를 구한다.
문제
음악 플레이어가 곡을 무작위로 재생한다. 여러 장르가 있고, 각 곡은 정확히 하나의 장르에 속한다. 또한 어떤 장르 뒤에 어떤 장르의 곡을 이어서 들을 수 있는지 미리 정해져 있다. 장르 i 뒤에 장르 j를 들을 수 있다면, 장르 i의 곡이 끝난 뒤 장르 j의 곡을 선택할 수 있다.
처음에는 아무 곡이나 하나 재생한다. 그 뒤에는 직전에 재생한 곡의 장르와 이어서 들을 수 있는 장르 중 하나에 속한 곡을 선택해 재생한다. 같은 곡이 여러 번 나올 수 있고, 같은 곡이 연속해서 나올 수도 있다.
이 규칙으로 재생할 수 있는 곡의 순서 중 전체 재생 시간이 A 이상 B 이하인 순서의 개수를 구하시오.
입력
첫째 줄에 곡의 개수 N이 주어진다. N은 1 이상 1000 이하이다.
다음 N개의 줄에는 각 곡의 장르 번호와 길이가 주어진다. 장르 번호는 0부터 M-1까지이고, 곡의 길이는 1 이상 9 이하이다.
그다음 줄에 장르의 개수 M이 주어진다. M은 1 이상 9 이하이다.
다음 M개의 줄에는 서로 이어서 들을 수 있는 장르 관계가 인접 행렬로 주어진다. 행렬의 i번째 줄 j번째 문자가 Y이면 장르 i 뒤에 장르 j를 들을 수 있고, N이면 들을 수 없다. 이 행렬을 T라고 할 때 모든 i에 대해 T[i][i] = Y이다.
마지막 줄에 A와 B가 주어진다. B는 A 이상이고, A와 B는 1 이상 1,000,000,000 이하이다.
출력
전체 재생 시간이 A 이상 B 이하인 곡 순서의 개수를 600921647로 나눈 나머지를 출력한다.