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
// #include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#include <iostream>
#include <vector>
#include <map>
using namespace std;
#define MOD 1000000007
enum state
{
    START,
    PROGRESS,
    FINE
};
vector<int64_t> powers;
// state, n, fs
map<state, map<int64_t, map<int64_t, int64_t>>> memo;
void powerade(int64_t n, int64_t base)
{
    vector<int64_t> pwrs(n + 1);
    pwrs[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        pwrs[i] = (pwrs[i - 1] * base) % MOD;
    }
    powers = pwrs;
}

int64_t getMemo(state s, int64_t n, int64_t finishingStates)
{
    return memo[s][n][finishingStates];
}
void saveMemo(state s, int64_t n, int64_t finishingStates, int64_t v)
{
    memo[s][n][finishingStates] = v;
}
int64_t wtf(int64_t n, int64_t treeTypes, int64_t finishingStates, state s)
{
    if (n == 1)
    {
        return finishingStates;
    }
    if (finishingStates == treeTypes)
    {
        return powers[n];
    }
    int64_t mm = getMemo(s, n, finishingStates);
    if (mm)
    {
        return mm;
    }
    switch (s)
    {
    case FINE:
        mm = (finishingStates * wtf(n - 1, treeTypes, finishingStates, FINE) +
              (treeTypes - finishingStates) * wtf(n - 1, treeTypes, finishingStates + 1, START)) %
             MOD;
        break;
    case PROGRESS:

        mm = (finishingStates * wtf(n - 1, treeTypes, finishingStates, FINE) +
              (treeTypes - finishingStates) * wtf(n - 1, treeTypes, finishingStates, PROGRESS)) %
             MOD;
        break;
    case START:
        mm = (finishingStates * wtf(n - 1, treeTypes, finishingStates, FINE) +
              (treeTypes - finishingStates) * wtf(n - 1, treeTypes, finishingStates, PROGRESS)) %
             MOD;
        break;
    }
    saveMemo(s, n, finishingStates, mm);
    return mm;
}

int main()
{
    FAST int64_t n, m;
    cin >> n >> m;
    switch (n)
    {
    case 1:
        cout << 0 << endl;
        return 0;
    case 2:
        cout << m << endl;
        return 0;
    case 3:
        cout << (m * m) % MOD;
        return 0;
    }
    if (m == 1)
    {
        cout << 1 << endl;
        return 0;
    }

    powerade(n - 1, m);
    cout << (m * wtf(n - 1, m, 1, START)) % MOD << endl;
}