Shuffle

A music player plays songs in a shuffled order. There are several genres, and each song belongs to exactly one genre. For every pair of genres, it is known whether a song of the second genre may be played immediately after a song of the first genre. If genre j is allowed after genre i, then after listening to a song of genre i, the next song may have genre j.

The first song may be any song. After that, the next song must belong to a genre that is allowed after the genre of the previous song. The same song may be played multiple times, and it may also be played twice in a row.

Count the number of playable song sequences whose total playing time is at least A and at most B.

The first line contains the number of songs N. N is between 1 and 1000, inclusive.

Each of the next N lines contains the genre number and length of one song. Genre numbers range from 0 to M-1, and every song length is between 1 and 9, inclusive.

The next line contains the number of genres M. M is between 1 and 9, inclusive.

The next M lines describe the genre compatibility relation as an adjacency matrix. If the jth character of the ith row is Y, a song of genre j may be played after a song of genre i; if it is N, it may not. Let this matrix be T; for every i, T[i][i] = Y.

The last line contains A and B. B is at least A, and both A and B are between 1 and 1,000,000,000, inclusive.

Print the number of song sequences whose total playing time is at least A and at most B, modulo 600921647.