**PK and interesting language(number of string of length n with restriction (expo + dp ))

PK and interesting language

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

SAMPLE INPUT

 

0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2
c 3
b 2

SAMPLE OUTPUT

 

1
2

Explanation

For query 1, Words of length 3 are: aba,acb,bab,bac,cba. The only word ending with ‘c’ is bac.

=====================================editorial=================================

Count the number of strings of length L with lowercase english letters, if some pairs of letters can not appear consequently in those strings. L is up to 10⁷, there are up to 100 inputs.

The “banned” pairs are described in the input as matrix: banned[i][j] == 0 means that letter j can not go after letter i in a valid string. Otherwise, banned[i][j] == 1.

Let dp[n][last_letter] be the number of valid strings of length n, which have last letter equal to last_letter. Then we can recalculate dp in order of increasing n:

dp[1][a] = dp[1][b] = … = dp[1][z] = 1
for n = 2..L:
  for last_letter = a..z:
    for next_letter = a..z:
      if banned[last_letter][next_letter] != 0:
        dp[n + 1][next_letter] += dp[n][last_letter]

The logic behind this is such: if we have the number of valid strings for some n and last_letter (it is dp[n][last_letter]), then we can add some letter to the end of those strings. Let’s iterate over this new letter next_letter and see if it is OK to place it after last_letter. If it is, then adding next_letter will result in the string of length n + 1 with last letter equal to next_letter. Thus, we add dp[n][last_letter] to dp[n + 1][next_letter].

The above approach works in Θ(L * 26²) time and won’t pass with L ~ 10⁷.

To speed things up, notice that inside the
for n = 2..L
loop nothing depends on n itself! Well, you could argue that writing “dp[n + 1][next_letter] += dp[n][last_letter]” and then saying “it does not depend on n” is nonsense. What I want to stress out is that transition from n to n + 1 happens in exactly the same way like, for example, from n + 100 to n + 101. The “banned” rules do not change over time!

The second observation would be: transition formulas from n to n + 1 are linear. To compute dp[n + 1][next_letter], we sum up dp[n][letter] for some letter. We do not have something like
dp[n + 1][next_letter] += dp[n][letter] * dp[n][next_letter],
which would mean that transition is not linear.

These two observations combined provide a useful property: there exists some matrix M, such that for any n ≥ 1

By now you should be able to tell that M is a square matrix with size 26 (which is number of letters in English alphabet). It contains 26 * 26 = 676 values - tough thing if you want to write them down manually!
Here is the easy way to understand, which values x_ij must be in M, based on the above equation:

1. Call the left part initial and the right part result;
2. By matrix multiplication definition we have:
   
3. In other words, when you want to compute i-th value of the result, you take all x’s from i-th column and multiply them by corresponding initial’s;
4. This means that x_ki is the number, which tells “how many times we need to add initial_1k to result_1i”. Personally, I call it “impact of k-th value on i-th value of dp”.

In this problem, M is conveniently given to you in input. Indeed, we could rewrite the transition loop to this:

for last_letter = a..z:
  for next_letter = a..z:
    dp[n + 1][next_letter] += dp[n][last_letter] * banned[last_letter][next_letter]

That’s because “banned” is given in binary form: 1 if letters can appear together, 0 in other case.
The states of dynamic programming here are letters, and matrix “banned” shows how one letter affect the other. The final solution is:

It works in O(26³ * log(L)), which is significantly faster and passes time limit.

This way of speeding up dynamic programming is crucial to understand. Most of the problems tagged “Matrix exponentiation” on HackerEarth can be solved with this trick.

=======================================code=================================

/*             deepak gautam
  codechef - algorithmist2 ,codeforce - gautam27
  topcoder- gautam_27      ,spoj - nexus_d
  hackerearth-deepak.gautam.127648 , hackerrank- deepakgautam2701
   */
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
#define ff first
#define ss second
#define mp make_pair
#define ph push_back
#define debug 0
int banned[26][26];
class expo
{
 public :
 lli sz=26;
 void mul(lli mat1[26][26],lli mat2[26][26],lli  ret[26][26],lli m)
 {

  for(lli i=0;i<sz;i++)
   {
    for(lli j=0;j<sz;j++)
       {
        ret[i][j]=0;
        for(lli k=0;k<sz;k++)
            {
            ret[i][j]=(ret[i][j]+(mat1[i][k]*mat2[k][j]+m))%m;
            while(ret[i][j]<0)
                {
                ret[i][j]+=m;
}

         
}
   
}
 
 }
 }
void rais(lli base[26][26], lli n,lli ans[26][26],lli mod)
 {

   lli temp[26][26];
      while(n>0)
    {
    if(n%2)
         {
          mul(ans,base,temp,mod);
          for(lli i=0;i<sz;i++)
                {
                for(lli j=0;j<sz;j++)
                         {
                          ans[i][j]=temp[i][j];
               
 }
         
  }
     
 }
 mul(base,base,temp,mod);
       for(lli i=0;i<sz;i++)
                {
                        for(lli j=0;j<sz;j++)
                         {
                          base[i][j]=temp[i][j];
               
 }
         
  }
   
    n/=2;
  }
 }
lli fibo(lli n,char c,lli mod)
 {
  lli base[26][26],ans[26][26];
  // generating identity matrix ans[][] ans filling base array with banned
for(int i=0;i<sz;i++)
{
for(int j=0;j<26;j++)

{
base[i][j]=banned[i][j];
if(i==j) ans[i][j]=1;
else ans[i][j]=0;
}
}
 
     rais(base,n-1,ans,mod);
     int col=c-'a';
     lli ret=0;
     // now  counting all matrixs have last character c 
     //since banned is given as banned[i][j]=1 means characted j can be adjecent to i 
     // counting of all string ending with c will be 
     //sum of coulumn c  means c at nth  index = sum of c at  nth 
//preceding character(a t= z at index n-1) index and 
     for(int i=0;i<sz;i++)
      {
      ret=(ret+ans[i][col]);
      if(ret>mod )
        {
      ret%=mod;
  }
     
 }
    return ret;
 }
};


int main()
 {
  for(int i=0;i<26;i++)
   {
    for(int j=0;j<26;j++)
        {
        scanf("%d",&banned[i][j]);
        // banned [i][j]=1 means 
        // j can be adjecent of i ( means not banned)
}
 }
 
 
 int t;
  cin>>t;
  while(t--){
  int n;
  char c;
   cin>>c;
   scanf("%d",&n);
  expo ob;
  printf("%lld\n",ob.fibo(n,c,1000000007));
 
  }

 }