• I have not solved it. But, if were in your situation I would try following ideas to get rid of TLE:-
• Implement matrix mult(matrix &x,matrix &y) function in matrix bigmod(matrix b,LL p) function
• r.mat[i][j]=sum%mod; can be replaced with while(r.mat[i][j]>=mod)r.mat[i][j]-=mod;
• i would try to avoid long long data type and use some explicit cast when needed.
• if that's also not enough i would try fastIO(use getchar() to take input).
• Also read the comments after the problem statement. It might be helpful for you.

In constant optimisation problems, especially in those which have enormous input data, it is good to write your own function for scanning integers. Below is the procedure i have used in many problems:

#define gc getchar_unlocked
inline int geti() {
  register int c = gc(), x = 0, sign = 1;
  for( ; c != '-' && (c < '0' || c > '9'); c = gc());
  if(c == '-') c = gc(), sign = -1;
  for( ; c >= '0' && c <= '9'; c = gc()) x = (x<<1) + (x<<3) + c-'0';
  return sign*x;
}

The most significant thing you need to optimize is storing the result of base^2,base^4,base^8.... So when calculating base^n you can just multiply the corresponding power of twos like base^7 = base * base^2 * base^4

Nobody has really helped you, but your post got -8 rating. Codeforces community is so awful...

In fact, if you have an N × N matrix (let's call it M), it's possible to calculate M^E × V (V is a vector) in , not in . To do so, you need to precalculate M¹, M², M⁴, M⁸.... Then, if you need to calculate, for example, M¹³ × V, you can just use the following formula: M¹³ × V = M⁸ × (M⁴ × (M¹ × V)).

Sorry for my pidgin English, but in Russian (my native language) I'd explain this exactly the same way.

UPD. With this idea I instantly got AC in Java in 2.7s without any additional optimizations.

I got AC with a 3x3 matrix and optimizations, but I heard that there is a way of doing with just a 2x2 matrix. Can someone tell me how to find this 2x2 matrix?