Динамика на префиксе.

1. Состояние $dp[i][j]$ — количество последовательностей на префиксе $i$ где ровно $j$ раз $a_{i-1}\ne a_i$.
2. Начальные значения $dp[1][0]=m$ т.к. можно покрасить в любой цвет.
3. Считаем опять двумя циклами:

• $dp[i][j]=dp[i-1][j]$ всегда. Если брать $a_{i-1}=a_i$.

• $dp[i][j]+=dp[i-1][j-1]\times (m-1)$ если $a_{i-1}\ne a_i$, т.к красим в любой из $m$ цветов без одного.

4. Ответ — $dp[n-1][k]$ все $k$ цветов и последний префикс.

$O(n\times m)$

int dp[2001][2001];

void solve() {
  int n, m, k;
  cin >> n >> m >> k;

  dp[0][0] = m;
  for (int i = 1; i < n; i++) {
    dp[i][0] = dp[i - 1][0];
    for (int j = 1; j <= k; j++) {
      dp[i][j] = add(dp[i - 1][j], mult(dp[i - 1][j - 1], (m - 1)));
    }
  }
  cout << dp[n - 1][k];
}