Recently, scientists have discovered that the Martian alphabet has very specific constraints, where certain letters can only come after certain other letters.
They have q questions for you. Please count the number of different words of length n, ending with the character c, that could exist in the Martian language.
### Input
- The first 26 lines, each containing 26 characters. The j-th character of the i-th line can be 0 or 1, representing whether the j-th letter can come after the i-th letter or not.
- The next line contains an integer q, the number of questions from the scientists.
- The next q lines, each line consisting of an integer k and a character c, which represent a question.
### Output
- For each question, print an integer modulo 109+7, which represents the number of strings that satisfy the question.
### Constraints
- 1≤q≤100.
- 1≤n≤109.
- a≤c≤z.
### Example
Input:
011000000000000000000000001000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000023c2b
Output:
12
