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
#include <cstdio>
#include <vector>
#include <cmath>

using namespace std;

unsigned long long power(int a, int x)
{
    if (x == 0)
    {
        return 1;
    }
    else if (x == 1)
    {
        return a;
    }
    else if (x == 2)
    {
        return a * a;
    }
    else if (x % 2 == 0)
    {
        unsigned long long tmp = power(a, x / 2);
        return (tmp * tmp) % 1000000007ull;
    }
    else
    {
        unsigned long long tmp = power(a, x / 2);
        return (tmp * tmp * a) % 1000000007ull;
    }
}

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);

    std::vector<unsigned long long> sol(n + 1, 0);
    std::vector<unsigned long long> npd(n + 1, 0);  // w sposób NiePoDzielny
    sol[0] = npd[0] = 1;
    sol[1] = npd[1] = 0;
    for (int i = 2; i <= n; ++i)
    {
        unsigned long long cnt0 = (m * power(m, i - 2)) % 1000000007ull;
        unsigned long long cnt = cnt0;
        unsigned long long add = 0;
        for (int j = 2; j <= i - 2; ++j)
        {
            int a = j;
            int b = i - j;
            add += npd[a] * (sol[b] - power(m, b-2));
            add %= 1000000007ull;
        }
        sol[i] = (cnt0 + add) % 1000000007ull;
        npd[i] = (sol[i] - add + 1000000007ull) % 1000000007ull;
        
        //printf("cnt0 = %d, cnt = %d, sol[%d] = %d, npd[%d] = %d\n", (int)cnt0, (int)cnt, i, (int)sol[i], i, (int)npd[i]);
    }
    
    printf("%d\n", (int)(sol[n] % 1000000007ull));

    return 0;
}