PK is an astronaut who went to a planet and was very fascinated by the language of its creatures. The language contains only lowercase English letters and is based on a simple logic that only certain characters can follow a particular character.

Now he is interested in calculating the number of words of length L and ending at a particular character C. Help PK to calculate this value.

Input :

The input begins with 26 lines, each containing 26 space-separated integers. The integers can be either 0 or 1. The jth integer at i^th line depicts whether j^th English alphabet can follow i^th English alphabet or not.
Next line contains an integer T. T is the number of queries.
Next T lines contains a character C and an integer L.

Output :

For each query output the count of words of length L ending with the character C. Answer to each query must be followed by newline character.
The answer may be very large so print it modulo 1000000007.

Constraints :

1 <= T <= 100
C is lowercase English alphabet.
2 <= L <= 10000000