#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

template<typename T, typename Mul>
constexpr T fast_pow(T x, T identity, int y, Mul mul) {
    T p = identity;
    while (y) {
        if (y & 1) {
            p = mul(p, x);
        }
        y >>= 1;
        x = mul(x, x);
    }
    return p;
}

int main()
{
    constexpr int mod = 1e9 + 7;
    ifstream fin("bani.in");
    ofstream fout("bani.out");
    int n;
    int type;
    fin >> type;
    fin >> n;
    auto mul_numbers = [mod = mod](int a, int b) -> int {
        return 1ll * a * b % mod;
    };
    auto mul_matrices = [mod = mod](const vector<vector<int>>& a,
        const vector<vector<int>>& b) {
            int n = a.size();
            vector<vector<int>> r(n, vector<int>(n, 0));
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < n; ++j) {
                    for (int k = 0; k < n; ++k) {
                        r[i][j] = (1ll * r[i][j] +
                            1ll * a[i][k] * b[k][j] % mod) % mod;
                    }
                }
            }
            return r;
    };
    if (type == 1) {
        fout << 5ll * fast_pow(2, 1, n - 1, mul_numbers) % mod;
    }
    else {
        int r = 0;
        vector<vector<int>> m = {
            {0, 1, 1, 0, 0},
            {1, 0, 0, 1, 0},
            {1, 0, 1, 0, 0},
            {0, 1, 1, 0, 1},
            {1, 0, 0, 1, 0}
        };
        vector<vector<int>> identity = {
            {1, 0, 0, 0, 0},
            {0, 1, 0, 0, 0},
            {0, 0, 1, 0, 0},
            {0, 0, 0, 1, 0},
            {0, 0, 0, 0, 1}
        };

        m = fast_pow(m, identity, n - 1, mul_matrices);
        for (int i = 0; i < m.size(); ++i) {
            for (int j = 0; j < m.size(); ++j) {
                r = (1ll * r + m[i][j]) % mod;
            }
        }
        fout << r;
    }
    return 0;
}