1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
#include <iostream>
#include <vector>
#include <cmath>
#include <random>

typedef long long ll;

using namespace std;



inline vector<ll> ciag_i_gen(ll& n, ll& m) {
    random_device rd;
    mt19937_64 gen(rd());
    uniform_int_distribution<ll> disc(1, m);
    vector<ll> ciag_drzew(n);
    for (ll i = 0; i < n; i++) {
        ciag_drzew[i] = disc(gen);
    }
    return ciag_drzew;
}

inline bool spr1(vector<vector<ll>> &ciag, vector<ll> &ciag_i) {
    for (ll i = 0; i < ciag.size(); i++) {
        if (ciag[i] == ciag_i) {
            return true;
        }
        else if (i == (ciag.size() - 1)) {
            return false;
        }
    }
}


inline bool spr2(vector<ll>& ciag_i, ll& n) {
    if (ciag_i.front() == ciag_i.back()) {
        return true;
    }
    else {
        ll j = 0;
        do{
            for (ll k = (j + 1); k < n; k++) {
                if (ciag_i.front() == ciag_i[k]) {
                    if (ciag_i[j] == ciag_i.back()) {
                        return true;
                    }
                    for (ll h = (j + 1); h < n; h++) {
                        if (ciag_i[j] == ciag_i[h]) {
                            j = h;
                        }
                        else if (h = (n - 1)) {

                        }
                    }
                }
            }
            
            j++;
        } while (j < n);
    }
    return false;
}

inline ll wynik(vector<vector<ll>>& ciag, ll& n, ll& potega) {
    ll x = 0;
    for (ll i = 0; i < potega; i++) {
        if (spr2(ciag[i], n)) {
            x++;
        }
    }
    return x;
}

inline vector<vector<ll>>ciag_gen(ll &n, ll &m, ll &potega) {
    vector<vector<ll>>ciag(potega);
    for (ll i = 0; i < potega; i++) {
        vector<ll> ciag_i;
        do {
            ciag_i = ciag_i_gen(n, m);
        } while (spr1(ciag, ciag_i));
        ciag[i] = ciag_i;
    }
    return ciag;
}

inline ll Running_Program(ll &n, ll &m) {
    ll potega = (pow(n, m));
    vector<vector<ll>>ciag = ciag_gen(n, m, potega);    
    

    return wynik(ciag, n, potega);
}

int main() {

    const long long dzielnik = (pow(10, 9) + 7);
    ll n, m;
    cin >> n >> m;
   
    cout << (Running_Program(n, m) % dzielnik);

    return 0;}