#include #include #include using namespace std; const int MOD = 998244353; const int SZ = 1e7 ; int64_t facs[SZ]; int64_t ifacs[SZ]; int64_t modpow(int64_t b, int64_t e, int64_t m) { int64_t r = 1; while(e) { if(e%2) r = (r*b) % MOD; e /= 2; if(e) b = (b*b) % MOD; } return r; } void init() { facs[0] = 1; for(int i = 1; i < SZ; i++) facs[i] = (facs[i-1]*i)%MOD; ifacs[SZ-1] = modpow(facs[SZ-1], MOD-2, MOD); for(int i = SZ-2; i >= 0; i--) ifacs[i] = (ifacs[i+1] * (i+1))%MOD; } int64_t nck(int n, int k) { if(k < 0 || k > n) return 0; return ((facs[n] * ifacs[k]) % MOD * ifacs[n-k]) % MOD; } int main() { init(); int n, k, m; cin >> n >> k >> m; int64_t ret = 0; vector scale(k); while(scale.size() < 30) { int curr = scale.size(); int64_t actual = 0; for(int a = 0; a < curr; a++) { actual += scale[a] * nck(curr, a); actual %= MOD; } scale.push_back((MOD + 1 - actual)%MOD); } for(int mask = 1; mask <= m; mask++) { if(__builtin_popcount(mask) < k) continue; int maxvalid = mask; bool enabled = false; int maxgo = 0; for(int x = 29; x >= 0; x--) { if(mask & (1 << x)) continue; if(enabled) maxgo *= 2; if((maxvalid | (1 << x)) <= m) { maxgo |= 1; enabled = true; maxvalid |= 1 << x; } } maxgo++; ret += scale[__builtin_popcount(mask)] * nck(maxgo, n); ret %= MOD; } cout << (ret*facs[n])%MOD << "\n"; }