Untitled

#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ll const MatrixSize = 102;
int siz = MatrixSize;
long long mod = 1e9 + 7;
 
struct Matrix {
    ll mat[MatrixSize][MatrixSize];
    Matrix() {
        memset(mat, 0, sizeof mat);
    }
    Matrix operator*(const Matrix &other) {
        Matrix prod;
        int n = siz;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] != 0) {
                    for (int k = 0; k < n; k++) {
                        prod.mat[i][k] = (prod.mat[i][k] + mat[i][j] * other.mat[j][k] % mod) % mod;
                    }
                }
            }
        }
        return prod;
    }
};
 
Matrix power(Matrix &a, ll k) {
    Matrix prod;
    int n = siz;
    for (int i = 0; i < n; i++) {
        prod.mat[i][i] = 1;
    }
    while (k) {
        if (k & 1) prod = prod * a;
        k >>= 1;
        a = a * a;
    }
    return prod;
}
 
const int M = 104;
ll c[M + 1][M + 1];
void pascal() {
    c[0][0] = 1;
    for (int n = 1; n < M; n++) {
        c[n][0] = 1;
        c[n][n] = 1;
        for (int k = 1; k < n; k++) {
            c[n][k] = (c[n - 1][k - 1] + c[n - 1][k]) % mod;
        }
    }
}
 
int main() {
    fast
    pascal();
    ll m, k; cin >> m >> k;
    Matrix x;
    for (int i = 0; i <= m; ++i) {
        for (int j = 0; j <= i; ++j) x.mat[i][j] = c[i][j] * m % mod;
    }
    x.mat[m + 1][m + 1] = 1;
    x.mat[m + 1][m] = 1;
    x = power(x, k + 1);
    cout << x.mat[m + 1][0] << "\n";
}