#include using namespace std; using ll = long long; using ld = long double; using ull = unsigned long long; using uint = unsigned; using pcc = pair; using pii = pair; using pll = pair; using pdd = pair; using tuplis = array; template using pq = priority_queue, greater>; const ll LINF=0x1fffffffffffffff; const ll MINF=0x7fffffffffff; const int INF=0x3fffffff; const int MOD=1000000007; const int MODD=998244353; const ld DINF=numeric_limits::infinity(); const ld EPS=1e-9; const ld PI=3.1415926535897932; const ll dx[] = {0, 1, 0, -1, 1, -1, 1, -1}; const ll dy[] = {1, 0, -1, 0, 1, 1, -1, -1}; #define overload4(_1,_2,_3,_4,name,...) name #define overload3(_1,_2,_3,name,...) name #define rep1(n) for(ll i=0;i(a);) #define rrep4(i,a,b,c) for(ll i=(a)+((b)-(a)-1)/(c)*(c);i>=(a);i-=c) #define rrep(...) overload4(__VA_ARGS__,rrep4,rrep3,rrep2,rrep1)(__VA_ARGS__) #define each1(i,a) for(auto&&i:a) #define each2(x,y,a) for(auto&&[x,y]:a) #define each3(x,y,z,a) for(auto&&[x,y,z]:a) #define each(...) overload4(__VA_ARGS__,each3,each2,each1)(__VA_ARGS__) #define all1(i) begin(i),end(i) #define all2(i,a) begin(i),begin(i)+a #define all3(i,a,b) begin(i)+a,begin(i)+b #define all(...) overload3(__VA_ARGS__,all3,all2,all1)(__VA_ARGS__) #define rall1(i) (i).rbegin(),(i).rend() #define rall2(i,k) (i).rbegin(),(i).rbegin()+k #define rall3(i,a,b) (i).rbegin()+a,(i).rbegin()+b #define rall(...) overload3(__VA_ARGS__,rall3,rall2,rall1)(__VA_ARGS__) #define sum(...) accumulate(all(__VA_ARGS__),0LL) #define dsum(...) accumulate(all(__VA_ARGS__),0.0L) #define Msum(...) accumulate(all(__VA_ARGS__),0_M) #define elif else if #define unless(a) if(!(a)) #define INT(...) int __VA_ARGS__;in(__VA_ARGS__) #define LL(...) ll __VA_ARGS__;in(__VA_ARGS__) #define ULL(...) ull __VA_ARGS__;in(__VA_ARGS__) #define STR(...) string __VA_ARGS__;in(__VA_ARGS__) #define CHR(...) char __VA_ARGS__;in(__VA_ARGS__) #define DBL(...) double __VA_ARGS__;in(__VA_ARGS__) #define LD(...) ld __VA_ARGS__;in(__VA_ARGS__) #define Sort(a) sort(all(a)) #define Rev(a) reverse(all(a)) #define Uniq(a) sort(all(a));a.erase(unique(all(a)),end(a)) #define vec(type,name,...) vectorname(__VA_ARGS__) #define VEC(type,name,size) vectorname(size);in(name) #define vv(type,name,h,...) vector>name(h,vector(__VA_ARGS__)) #define VV(type,name,h,w) vector>name(h,vector(w));in(name) #define vvv(type,name,h,w,...) vector>>name(h,vector>(w,vector(__VA_ARGS__))) template auto min(const T& a){ return *min_element(all(a)); } template auto max(const T& a){ return *max_element(all(a)); } inline ll popcnt(ull a){ return __builtin_popcountll(a); } ll intpow(ll a, ll b){ ll ans = 1; while(b){ if(b & 1) ans *= a; a *= a; b /= 2; } return ans; } ll modpow(ll a, ll b, ll p){ ll ans = 1; while(b){ if(b & 1) (ans *= a) %= p; (a *= a) %= p; b /= 2; } return ans; } template bool chmin(T& a, const T& b){ if(a > b){ a = b; return 1; } return 0; } template bool chmax(T& a, const T& b){ if(a < b){ a = b; return 1; } return 0; } template bool chmin(T& a, const U& b){ if(a > T(b)){ a = b; return 1; } return 0; } template bool chmax(T& a, const U& b){ if(a < T(b)){ a = b; return 1; } return 0; } vector iota(ll n, ll begin = 0){ vector a(n); iota(a.begin(), a.end(), begin); return a; } vector factor(ull x){ vector ans; for(ull i = 2; i * i <= x; i++) if(x % i == 0){ ans.push_back({i, 1}); while((x /= i) % i == 0) ans.back().second++; } if(x != 1) ans.push_back({x, 1}); return ans; } map factor_map(ull x){ map ans; for(ull i = 2; i * i <= x; i++) if(x % i == 0){ ans[i] = 1; while((x /= i) % i == 0) ans[i]++; } if(x != 1) ans[x] = 1; return ans; } vector divisor(ull x){ vector ans; for(ull i = 1; i * i <= x; i++) if(x % i == 0) ans.push_back(i); rrep(ans.size() - (ans.back() * ans.back() == x)) ans.push_back(x / ans[i]); return ans; } template unordered_map press(vector a){ Uniq(a); unordered_map ans; rep(a.size()) ans[a[i]] = i; return ans; } template map press_map(vector a){ Uniq(a); map ans; rep(a.size()) ans[a[i]] = i; return ans; } int scan(){ return getchar(); } void scan(int& a){ scanf("%d", &a); } void scan(unsigned& a){ scanf("%u", &a); } void scan(long& a){ scanf("%ld", &a); } void scan(long long& a){ scanf("%lld", &a); } void scan(unsigned long long& a){ scanf("%llu", &a); } void scan(char& a){ do{ a = getchar(); }while(a == ' ' || a == '\n'); } void scan(float& a){ scanf("%f", &a); } void scan(double& a){ scanf("%lf", &a); } void scan(long double& a){ scanf("%Lf", &a); } void scan(vector& a){ for(unsigned i = 0; i < a.size(); i++){ int b; scan(b); a[i] = b; } } void scan(char a[]){ scanf("%s", a); } void scan(string& a){ cin >> a; } template void scan(vector&); template void scan(array&); template void scan(pair&); template void scan(T(&)[size]); template void scan(vector& a){ for(auto&& i : a) scan(i); } template void scan(deque& a){ for(auto&& i : a) scan(i); } template void scan(array& a){ for(auto&& i : a) scan(i); } template void scan(pair& p){ scan(p.first); scan(p.second); } template void scan(T (&a)[size]){ for(auto&& i : a) scan(i); } template void scan(T& a){ cin >> a; } void in(){} template void in(T&... a){ (void)initializer_list{ (scan(a), 0)... }; } void print(){ putchar(' '); } void print(bool a){ printf("%d", a); } void print(int a){ printf("%d", a); } void print(unsigned a){ printf("%u", a); } void print(long a){ printf("%ld", a); } void print(long long a){ printf("%lld", a); } void print(unsigned long long a){ printf("%llu", a); } void print(char a){ printf("%c", a); } void print(char a[]){ printf("%s", a); } void print(const char a[]){ printf("%s", a); } void print(float a){ printf("%.15f", a); } void print(double a){ printf("%.15f", a); } void print(long double a){ printf("%.15Lf", a); } void print(const string& a){ for(auto&& i : a) print(i); } template void print(const complex& a){ if(a.real() >= 0) print('+'); print(a.real()); if(a.imag() >= 0) print('+'); print(a.imag()); print('i'); } template void print(const vector&); template void print(const array&); template void print(const pair& p); template void print(const T (&)[size]); template void print(const vector& a){ if(a.empty()) return; print(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); print(*i); } } template void print(const deque& a){ if(a.empty()) return; print(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); print(*i); } } template void print(const array& a){ print(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); print(*i); } } template void print(const pair& p){ print(p.first); putchar(' '); print(p.second); } template void print(const T (&a)[size]){ print(a[0]); for(auto i = a; ++i != end(a); ){ putchar(' '); print(*i); } } template void print(const T& a){ cout << a; } int out(){ putchar('\n'); return 0; } template int out(const T& t){ print(t); putchar('\n'); return 0; } template int out(const Head& head, const Tail&... tail){ print(head); putchar(' '); out(tail...); return 0; } #ifdef DEBUG inline ll __lg(ull x){ return 63 - __builtin_clzll(x); } #define debug(...) { print(#__VA_ARGS__); print(":"); out(__VA_ARGS__); } #else #define debug(...) void(0) #endif int first(bool i = true){ return out(i?"first":"second"); } int First(bool i = true){ return out(i?"First":"Second"); } int yes(bool i = true){ return out(i?"yes":"no"); } int Yes(bool i = true){ return out(i?"Yes":"No"); } int No(){ return out("No"); } int YES(bool i = true){ return out(i?"YES":"NO"); } int NO(){ return out("NO"); } int Yay(bool i = true){ return out(i?"Yay!":":("); } int possible(bool i = true){ return out(i?"possible":"impossible"); } int Possible(bool i = true){ return out(i?"Possible":"Impossible"); } int POSSIBLE(bool i = true){ return out(i?"POSSIBLE":"IMPOSSIBLE"); } void Case(ll i){ printf("Case #%lld: ", i); } #include using Modint = atcoder::modint998244353; struct Poly{ vector a; Poly(){} explicit Poly(ll n): a(n){} Poly(const vector& a): a(a){} Poly(vector&& a): a(a){} Modint& operator[](ll x){ return a[x]; } Modint operator[](ll x) const { return a[x]; } auto begin(){ return a.begin(); } auto end(){ return a.end(); } auto begin() const { return a.cbegin(); } auto end() const { return a.cend(); } ll size() const { return a.size(); } Poly& resize(ll n){ a.resize(n); return *this; } Poly& resize(const Poly& f){ if(size() < f.size()) resize(f.size()); return *this; } Poly& operator+=(const Poly& f){ resize(f); for(ll i = 0; i < f.size(); i++) a[i] += f[i]; return *this; } Poly operator+(const Poly& f) const { if(size() < f.size()) return Poly(f) += *this; return Poly(*this) += f; } Poly& operator-=(const Poly& f){ resize(f); for(ll i = 0; i < f.size(); i++) a[i] -= f[i]; return *this; } Poly operator-(const Poly& f) const { return Poly(*this) -= f; } Poly operator-(int) const { Poly ans(size()); for(ll i = 0; i < size(); i++) ans[i] = -a[i]; return ans; } Poly& operator*=(Modint x){ for(Modint& i : a) i *= x; return *this; } Poly operator*(Modint x){ return Poly(*this) *= x; } Poly operator*(const Poly& f) const { return atcoder::convolution(a, f.a); } Poly& operator*=(const Poly& f){ a = atcoder::convolution(move(a), vector(f.a)); return *this; } Poly inv(ll n = -1) const { if(n == -1) n = size(); if(n == 0) return {}; assert(size() && a[0] != 0); vector ans = {a[0].inv()}; for(ll m = 1; m < n; m *= 2) { const Modint M = Modint(m * m * 4).inv(); vector x(a.begin(), a.begin() + min(size(), m * 2)), y = ans; x.resize(m * 2); atcoder::internal::butterfly(x); y.resize(m * 2); atcoder::internal::butterfly(y); for(ll i = 0; i < m * 2; ++i) x[i] *= y[i]; atcoder::internal::butterfly_inv(x); for(ll i = 0; i < m; i++) x[i] = 0; for(ll i = m; i < m * 2; i++) x[i] *= M; atcoder::internal::butterfly(x); for(ll i = 0; i < m * 2; ++i) x[i] *= -y[i]; atcoder::internal::butterfly_inv(x); ans.insert(ans.end(), x.begin() + m, x.end()); } ans.resize(n); return ans; } Poly operator/=(const Poly& f){ const ll n = size(); *this *= f.inv(n); return resize(n); } Poly operator/(const Poly& f) const { return Poly(*this) /= f; } Poly div(const Poly& f) const { assert(f.size() && f.a.back() != 0); if(size() < f.size()) return {}; Poly x = *this, y = f; while(x.size() && !x.a.back().val()) x.a.pop_back(); while(y.size() && !y.a.back().val()) y.a.pop_back(); const ll n = x.size() - y.size() + 1; reverse(x.begin(), x.end()); x.resize(n); reverse(y.begin(), y.end()); y.resize(n); x /= y; reverse(x.begin(), x.end()); return x; } Poly operator%(const Poly& f) const { assert(f.size() && f.a.back() != 0); return (*this - f * div(f)).resize(f.size() - 1); } Poly D(ll n = -1) const { if(n == -1) n = size(); if(n == 0) return {}; Poly ans(size() - 1); for(ll i = 1; i < size(); i++) ans[i - 1] = a[i] * Modint::raw(i); return ans; } Poly integral() const { const ll n = size(); Poly ans(n + 1); ans[0] = 1; for(ll i = 0; i < n; i++) ans[i + 1] = ans[i] * Modint::raw(i + 1); ans[n] = ans[n].inv(); for(ll i = n; i--; ){ swap(ans[i], ans[i + 1]); ans[i + 1] *= ans[i] * a[i]; ans[i] *= Modint::raw(i + 1); } ans[0] = 0; return ans; } Poly log(ll n = -1) const { if(n == -1) n = size(); if(n == 0) return {}; assert(size() && a[0] == 1); return (D(n) * inv(n)).resize(n - 1).integral(); } Poly exp(ll n = -1) const { if(n == -1) n = size(); if(n == 0) return {}; assert(a[0] == 0); if(size() == 1) return vector{1}; vector b = {1, a[1]}, c = {1}, z1, z2 = {1, 1}; for(ll m = 2; m < n; m *= 2) { const Modint M = Modint(m).inv(), M2 = Modint(m * 2).inv(); auto y = b; y.resize(m * 2); atcoder::internal::butterfly(y); z1 = move(z2); vector z(m); for(ll i = 0; i < m; i++) z[i] = y[i] * z1[i]; atcoder::internal::butterfly_inv(z); for(ll i = 0; i < m / 2; i++) z[i] = 0; for(ll i = m / 2; i < m; i++) z[i] *= M * M; atcoder::internal::butterfly(z); for(ll i = 0; i < m; i++) z[i] *= -z1[i]; atcoder::internal::butterfly_inv(z); c.insert(c.end(), z.begin() + m / 2, z.end()); z2 = c; z2.resize(m * 2); atcoder::internal::butterfly(z2); Poly x = vector(begin(), begin() + min(size(), m)); x = x.D(); x.a.push_back(0); atcoder::internal::butterfly(x.a); for(ll i = 0; i < m; i++) x[i] *= y[i] * M; atcoder::internal::butterfly_inv(x.a); x -= Poly(b).D(); x.resize(m * 2); for(ll i = 0; i < m - 1; i++){ x[m + i] = x[i]; x[i] = 0; } atcoder::internal::butterfly(x.a); for (ll i = 0; i < m * 2; i++) x[i] *= z2[i] * M2; atcoder::internal::butterfly_inv(x.a); x = x.integral(); x.a.pop_back(); for(ll i = m; i < min(size(), m * 2); i++) x[i] += a[i]; for(ll i = 0; i < m; i++) x[i] = 0; for(ll i = m; i < m * 2; i++) x[i] *= M2; atcoder::internal::butterfly(x.a); for(ll i = 0; i < m * 2; ++i) x[i] *= y[i]; atcoder::internal::butterfly_inv(x.a); b.insert(b.end(), x.begin() + m, x.end()); } return Poly(move(b)).resize(n); } Poly pow(ll k, ll n = -1){ if(n == -1) n = size(); if(n == 0) return {}; assert(k >= 0); if(k == 0){ Poly ans(n); ans[0] = 1; return ans; } Poly ans = *this; ll cnt = 0; while(cnt < size() && ans[cnt] == 0) cnt++; if(cnt == size() || cnt * k >= n) return Poly(n); ans.a.erase(ans.a.begin(), ans.a.begin() + cnt); const Modint c = ans[0], C = c.pow(k), D = c.inv(), K = k; for(Modint& i : ans) i *= D; ans = ans.log(n - cnt * k); for(Modint& i : ans) i *= K; ans = ans.exp(); for(Modint& i : ans) i *= C; ans.a.insert(ans.a.begin(), cnt * k, 0); return ans; } }; Modint bostan_mori(Poly P, Poly Q, ll n){ assert(Q.size() && Q[0] != 0); ll lg = atcoder::internal::ceil_pow2(max(P.size(), Q.size())), z = 1 << lg; const Modint M = Modint(z * 2).inv(), W = Modint(atcoder::internal::primitive_root).pow(Modint::mod() - 1 >> lg + 1).inv(); auto bitrev = [lg](ll bit){ for(ll i = 0; i < lg / 2; i++){ const ll j = lg - 1 - i; if((bit >> i ^ bit >> j) & 1) bit ^= 1 << i | 1 << j; } return bit; }; vector w(z); w[0] = 1; for(ll i = 1; i < z; i++) w[i] = w[i - 1] * W; { vector w2(z); for(ll i = 0; i < z; i++) w2[bitrev(i)] = w[i]; w = move(w2); } while(n){ P.resize(z * 2); atcoder::internal::butterfly(P.a); Q.resize(z * 2); atcoder::internal::butterfly(Q.a); if(n & 1){ for(ll i = 0; i < z; i++) P[i] = (P[i << 1] * Q[i << 1 ^ 1] - P[i << 1 ^ 1] * Q[i << 1]) * w[i]; for(ll i = 0; i < z; i++) Q[i] = Q[i << 1] * Q[i << 1 ^ 1] * 2; } else{ for(ll i = 0; i < z; i++) P[i] = P[i << 1] * Q[i << 1 ^ 1] + P[i << 1 ^ 1] * Q[i << 1]; for(ll i = 0; i < z; i++) Q[i] = Q[i << 1] * Q[i << 1 ^ 1] * 2; } P.resize(z); atcoder::internal::butterfly_inv(P.a); Q.resize(z); atcoder::internal::butterfly_inv(Q.a); for(Modint& i : P) i *= M; for(Modint& i : Q) i *= M; n >>= 1; } return P[0] / Q[0]; } int main(){ ll N, M, K; cin >> N >> M >> K; if(M == K) M--; if(M == 0) return puts("0") & 0; Poly F(M * 2 + 1); ll s = 0; for(ll i = -M; i <= M; i++) if(i != K && i != -K){ F[i + M] = 1; s += 1; } Poly S(M + 1); S[M] = s; Poly Q = Poly(vector{1, -1}) * (F - S) * (F - S); cout << (F.pow(N + 2, N * M) / Q)[N * M - 1].val() << endl; }