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
#include <iostream>
#include <cmath>

using namespace std;

bool IsCorect(int* trees, int n)
{
    if (trees[0] == trees[n - 1] && n != 1)
        return true;

    for (int i = n - 3; i > 0; i--)
    {
        if (trees[i] == trees[0])
        {
            return IsCorect(&trees[i + 1], n - i - 1);
        }
    }
    return false;
}

void Add(int* numbers, int m)
{
    numbers[0]++;
    if (numbers[0] > m)
    {
        numbers[0] = 1;
        Add(&numbers[1], m);
    }
}

int main()
{
    int n, m;
    cin >> n >> m;

    int trees[n];
    int answer = 0;

    for (int i = 0; i < n; i++)
    {
        trees[i] = 1;
    }

    for (int i = 1; i <= pow(m, n); i++)
    {
        if(IsCorect(trees, n))
        {
            answer++;
        }

        Add(trees, m);
    }

    cout << answer % (1000000000 + 7);

    return 0;
}