Codeforces F1 ТехноКубок 3

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <string>
#include <math.h>
#include <climits>

//#include <chrono>
//#include <fstream>
//#include <bits/stdc++.h>

#define mp make_pair
#define pb push_back
#define eb emplace_back
#define x first
#define y second
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define RFOR(i,b,a) for (int i = (b) - 1; i >= (a); i--)

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> veci;
typedef vector<bool> vecb;
typedef vector<vector<int>> vvi;
typedef vector<vector<bool>> vvb;

const int INF_I = 1e9;
const ll INF_LL = 1e18;

const int MOD = 998244353;


int main() {
    /*ifstream cin("in.txt");
    ofstream cout("out.txt");
    auto start_time = chrono::high_resolution_clock::now();*/

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);


    int n, k;
    cin >> n >> k;
    const int ST = n;
    veci vec1(n), vec2(n);
    FOR(i, 0, n) {
        cin >> vec1[i];
        vec2[(i + 1) % n] = vec1[i];
    }
    /*swap(vec2[0], vec2[n]);*/
    vvi dp(n + 1, veci(ST + n + 10));
    /*FOR(i, 0, n + 1)
        dp[0][i] = 1;*/
    dp[0][ST] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < ST + n + 10; j++) {
            if (vec1[i] == vec2[i]) {
                dp[i + 1][j] = (dp[i + 1][j] + ((ll)dp[i][j] * k) % MOD) % MOD;
            }
            else {
                if (j + 1 <= ST + n + 2)
                    dp[i + 1][j+1] = (dp[i + 1][j + 1] + ((ll)dp[i][j]) % MOD) % MOD;
                if (j - 1 >= 0)
                    dp[i + 1][j - 1] = (dp[i + 1][j - 1] + ((ll)dp[i][j]) % MOD) % MOD;
                if (k > 1)
                    dp[i + 1][j] = (dp[i + 1][j] + ((ll)dp[i][j] * (k - 2)) % MOD) % MOD;
            }
        }
    }

    int answ = 0;
    FOR(i, ST + 1, ST + n + 2)
        answ = (answ + (ll)dp[n][i]) % MOD;
    cout << answ << endl;

    /*auto end_time = chrono::high_resolution_clock::now();
    chrono::duration<double> duration = end_time - start_time;
    cout << duration.count() << "\n";
    cin.close();
    cout.close();*/
    return 0;
}