typedef long long ll;
const ll m = 1000000007;
inline ll mod(ll n) {
return (n % m + m) % m;
}
struct matrix {
ll a, b, c, d;
matrix operator*(const matrix &mat) const {
return { mod(a * mat.a + b * mat.c), mod(a * mat.b + b * mat.d),
mod(c * mat.a + d * mat.c), mod(c * mat.b + d * mat.d)};
}
};
const matrix e = {1, 0, 0, 1};
matrix qpow(matrix a, ll b) {
matrix ret = e;
while(b) {
if(b & 1)
ret = ret * a;
b >>= 1, a = a * a;
}
return ret;
}
class Solution {
public:
/**
* 返回c[n]%1000000007的值
* @param n long长整型 即题目中的n
* @return int整型
*/
int Answerforcn(long long n) {
// write code here
if(n == 1)
return 14;
matrix a = qpow({2, 3, 1, 0}, n - 2), b = qpow({3, 10, 1, 0}, n - 2);
//return a.a;
return mod(mod(a.a * 6 + a.b * 2) * mod(b.a * 35 + b.b * 7));
}
}; 
