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
#include <iostream>
#include <vector>
#include <cstring>

#define MOD 1'000'000'007

using namespace std;

typedef long long ll;

ll pow(ll n, int base) {
    ll result = 1;
    for (int i = 0; i < base; i++) {
        result = (result * n) % MOD;
    }
    return result;
}

vector<string> pos;

void combinations(int l, int r, string prev, int depth) {
    if (depth == l) {
        pos.push_back(prev);
    } else {
        for (int i = 1; i <= r; i++) {
            combinations(l, r, prev + static_cast<char>(i + 48), depth + 1);
        }
    }
}

bool valid(string row) {
    if (row[0] == row[row.length() - 1])
        return true;
    for (int i = 0; i <= row.length() - 1; i++) {
        for (int j = row.length() - 1; j >= i; j--) {
            if (j == i)
                return false;
            if (row[j] == row[i] || (j == i + 1 && row[i] == row[j])) {
                i = j;
                if (i == row.length() - 1)
                    return true;
                break;
            }
        }
    }
    return false;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    ll m;
    cin >> n >> m;
    ll sum = 0;
    combinations(n, m, "", 0);
    for (int i = 0; i < pos.size(); i++) {
        if (valid(pos[i])) {
            sum++;
            // cout << pos[i] + "\n";
        }
    }
     cout << sum;
    return 0;
}