title: Is there any way to reduce time complexity to find this matrix to the power n?
body: <p>I am working on a problem where I am supposed to find <code>nth</code> power of a <code>4x4</code> matrix where <code>n</code> can be as large as <code>10^15</code> and since values in answer can be very large I can use <code>modulo 10^9+7</code> .
  Given Matrix is-</p>
  
  <pre><code>   2  1 -2 -1
  A= 1  0  0  0
     0  1  0  0
     0  0  1  0 
  </code></pre>
  
  <p>I have written a code for this purpose but its running time is more than desired time. So 
  anyone please help me in reducing time complexity. </p>
  
  <pre><code>#define FOR(k,a,b) for(typeof(a) k=(a); k &lt; (b); ++k)
  typedef long long ll;
  #define dim 4
  struct matrix {
      long long a[dim][dim];
  };
  #define MOD 1000000007
  matrix mul(matrix x, matrix y)
  {
      matrix res;
      FOR(a, 0, dim) FOR(b, 0, dim) res.a[a][b] = 0;
      FOR(a, 0, dim) FOR(b, 0, dim) FOR(c, 0, dim) {
      ll temp = x.a[a][b] * y.a[b][c];
      if (temp &lt;= -MOD || temp &gt;= MOD)
          temp %= MOD;
      res.a[a][c] += temp;
      if (res.a[a][c] &lt;= -MOD || res.a[a][c] &gt;= MOD)
          res.a[a][c] %= MOD;
      }
      return res;
  }
  
  matrix power(matrix m, ll n)
  {
      if (n == 1)
          return m;
      matrix u = mul(m, m);
      u = power(u, n / 2);
      if (n &amp; 1)
          u = mul(u, m);
      return u;
  }
  
  matrix M, RP;
  int main()
  {
      FOR(a, 0, dim) FOR(b, 0, dim) M.a[a][b] = 0;
      M.a[0][0] = 2;
      M.a[0][1] = 1;
      M.a[0][2] = -2;
      M.a[0][3] = -1;
      M.a[1][0] = 1;
      M.a[2][1] = 1;
      M.a[3][2] = 1;
      int nt;
      scanf("%d", &amp;nt);
      while (nt--) {
      ll n;
      scanf("%lld", &amp;n);
      RP = power(M, n);
      FOR(a, 0, dim)
          FOR(b, 0, dim)
          printf("%lld\n", RP.a[a][b]);
      }
      return 0;
  }
  </code></pre>