#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll mod = 1e9 + 7;

struct mat {
  vector<vector<ll>> m;
  ll sz;
  
  mat(ll _sz = 2, ll v = 0) {
    sz = _sz;
    m = vector<vector<ll>> (sz, vector<ll> (sz, v));
  }

  mat(vector<vector<ll>> _m) {
    m = _m;
  }

  vector<ll>& operator[](size_t x) {
    return m[x];
  }

  friend mat operator+(mat& a, mat& b) {
    mat res(a.m);
    for (int i = 0 ; i < a.sz ; i ++) {
      for (int j = 0 ; j < a.sz ; j ++) {
        res[i][j] += b[i][j];
        if (res[i][j] >= mod) res[i][j] -= mod;
      }
    }
    return res;
  }

  friend mat operator*(mat& a, mat& b) {
    mat res(a.sz);
    for (int i = 0 ; i < a.sz ; i ++) {
      for (int j = 0 ; j < a.sz ; j ++) {
        for (int k = 0 ; k < a.sz ; k  ++) {
          (res.m[i][j] += a.m[i][k] * b.m[k][j] % mod) %= mod;
        }
      }
    }
    return res;
  }
  inline void operator*=(mat& b) {
    mat res(sz);
    for (int i = 0 ; i < sz ; i ++) {
      for (int j = 0 ; j < sz ; j ++) {
        for (int k = 0 ; k < sz ; k  ++) {
          (res.m[i][j] += m[i][k] * b.m[k][j] % mod) %= mod;
        }
      }
    }
    m.swap(res.m);
  }

};

inline mat pw(mat& a, ll b) {
  if (b == 0) return mat();
  mat res = a;
  for (b -- ; b ; b >>= 1, a *= a) {
    if (b & 1) res *= a;
  }
  return res;
}

int main() {

}