#include using namespace std; #define int long long const int mod = 998244353; vector fact, fact_inv, inv; /* init_nCk :二項係数のための前処理 計算量:O(n) */ void init_nCk(int SIZE) { fact.resize(SIZE + 5); fact_inv.resize(SIZE + 5); inv.resize(SIZE + 5); fact[0] = fact[1] = 1; fact_inv[0] = fact_inv[1] = 1; inv[1] = 1; for (int i = 2; i < SIZE + 5; i++) { fact[i] = fact[i - 1] * i % mod; inv[i] = mod - inv[mod % i] * (mod / i) % mod; fact_inv[i] = fact_inv[i - 1] * inv[i] % mod; } } /* nCk :MODでの二項係数を求める(前処理 int_nCk が必要) 計算量:O(1) */ long long nCk(int n, int k) { if(n < k || n < 0 || k < 0) return 0; return fact[n] * (fact_inv[k] * fact_inv[n - k] % mod) %mod; } int int_mod(int a, int x){ if(x == 0) return 1; else if(x%2 == 0){ int t = int_mod(a,x/2); return (t*t)%mod; } else{ return (int_mod(a,x-1)*a)%mod; } } signed main(){ init_nCk(50000); int N,M,K; cin>>N>>M>>K; string S; cin>>S; vector> dp(M+1,vector(N+1,0)); dp[0][N] = 1; for(int i=0;i=K;k--){ dp[i+1][k] += dp[i][j]*int_mod(2,N-j)%mod*nCk(j,k)%mod; dp[i+1][k] %= mod; } } } /*for(vector s:dp){ for(int x:s){ cout<