1081C - Colorful Bricks - CodeForces Solution

// THEY DON'T KNOW ME SON
#include <bits/stdc++.h>
using namespace std;
#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

typedef long long ll;
typedef long double ld;
ll n,m,q,d,k;
const ll prime=1e9+7;
const ll prime2=998244353;
const ll prime3=7901;

const ll MOD = 998244353;
ll INF=2e18;
ll dp[2005][2005];
ll work(int index,int currk){
	debug() << imie(index) imie(currk);
	if(index>=n){
		if(currk!=k){
			return 0;
		}
		return 1;
	}
	if(dp[index][currk]!=-1) return dp[index][currk];
	ll answer=0;
	if(index==0){
		answer+=work(index+1,currk);
		answer%=MOD;
		return  dp[index][currk]=answer;
	}else{
		answer+=max(0ll,(m-1))*work(index+1,currk+1);
		answer%=MOD;
		answer+=work(index+1,currk);
	return  dp[index][currk]=answer;
	}

}
void solve(){
	cin >>n >> m >> k;
	ll ans=0;
	memset(dp,-1,sizeof dp);
	for(int i=0;i<m;i++){
		ans+=work(0,0);
		ans%=MOD;
	}
	cout << ans << "\n";
}
	
	

 
int main() {
	fastInp;
	//init();
	//debug() << imie(s);
	//freopen("grids.in","r",stdin);
	//freopen("res.out","w",stdout);
	// __gcd <long long> (x, y);
	int tc=1;
	//debug() << imie(sieve);
	//cin >> tc;
	//cout << setprecision(10)<<fixed;

	while(tc--){
		//i++;
		//cout <<"Test " << i << ":" << "\n";
		
		solve();
		
	}

	return 0;
}

/*
   Some insights:
    .Binary search
    .Graph representation
    .Write brute force code
    .Change your approach
 
 
 */