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));
    }
};