Martian language 2 - MarisaOJ: Marisa Online Judge

Martian language 2

Time limit: 1000 ms
Memory limit: 256 MB
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
Topic
Dynamic Programming
Matrix
Rating 1500
Source HackerEarth
Solution (0) Solution