text: class Solution
  {
  private:
    const int MOD = 1e9 + 7;
  
  public:
    int knightDialer(int N)
    {
      if (N == 1)
        return 10;
      // DP Version O(N)
      // vector<int> f(10, 1);
      // vector<int> nf(10, 1);
      // f[5]=0;
      // nf[5]=0;
      // for(int i =2;i<=N;++i){
      //     nf[1]=nf[3]=nf[7]=nf[9]=(f[2]+f[4])%MOD;
      //     nf[2]=nf[8]=(2*f[1])%MOD;
      //     nf[4]=nf[6]=(nf[2]+f[0])%MOD;
      //     nf[0]=(2*f[4])%MOD;
      //     for(int i =0;i<10;++i)f[i]=nf[i];
      // }
      // int ret = 0;
      // for(int i =0;i<10;++i)ret=(ret+f[i])%MOD;
      return fastPow(N);
    }
    // DP 加上矩阵快速幂 O(lgN)
    int fastPow(int N)
    {
      vector<vector<long long>> matrix = {{0, 1, 1, 0}, {2, 0, 0, 0}, {2, 0, 0, 1}, {0, 0, 2, 0}};
      vector<vector<long long>> final = {{1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}};
      vector<vector<long long>> tmp(4, vector<long long>(4, 0));
      N--;
      while (N != 0)
      {
        if (N & 1 != 0)
        {
          final = mutiply(final, matrix);
        }
        matrix = mutiply(matrix, matrix);
        N >>= 1;
      }
      // printMatrix(final);
      vector<int> nums = {1, 1, 1, 1};
      vector<long long> res(4, 0);
      for (int i = 0; i < 4; ++i)
      {
        for (int k = 0; k < 4; ++k)
        {
          res[i] = (res[i] + final[i][k] * nums[k]) % MOD;
        }
      }
      return (4 * res[0] + 2 * res[1] + 2 * res[2] + res[3]) % MOD;
    }
    vector<vector<long long>> mutiply(vector<vector<long long>> &x, vector<vector<long long>> &y)
    {
      vector<vector<long long>> ret(x.size(), vector<long long>(x.size()));
      int N = x.size();
      for (int i = 0; i < N; ++i)
      {
        for (int j = 0; j < N; ++j)
        {
          int v = 0;
          for (int k = 0; k < N; ++k)
          {
            v = (v + x[i][k] * y[k][j]) % MOD;
          }
          ret[i][j] = v;
        }
      }
      return ret;
    }
    void printMatrix(vector<vector<long long>> &m)
    {
      for (int i = 0; i < m.size(); ++i)
      {
        for (int j = 0; j < m.size(); ++j)
        {
          cout << m[i][j] << " ";
        }
        cout << endl;
      }
    }
  };