CCCPaste

aeace2741bc43

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 7, mod = 998244353;

long long binexp(long long a, long long n) {
long long res = 1;
while(n) {
if(n & 1) {
res = (res * a) % mod;
}
n >>= 1;
a = (a * a) % mod;
}
return res;
}

namespace ntt {
long long w[N], k, nrev;
inline void init(int n, int root) {
w[0] = 1;
k = binexp(root, (mod - 1) / n);
nrev = binexp(n, mod - 2);
for(int i = 1; i <= n; i++) {
w[i] = (w[i - 1] * k) % mod;
}
}
inline void ntt(vector<long long> &a, int n, bool inv = false) {
a.resize(n);
for(int i = 0, j = 0; i < n; i++) {
if(i > j) swap(a[i], a[j]);
for(int l = n / 2; (j ^= l) < l; l >>= 1);
}
for(int i = 2; i <= n; i <<= 1) {
for(int j = 0; j < n; j += i) {
for(int l = 0; l < i / 2; l++) {
int x = j + l, y = j + l + (i / 2), z = (n / i) * l;
long long tmp = (a[y] * w[(inv ? (n - z) : z)]) % mod;
a[y] = (a[x] - tmp + mod) % mod;
a[x] = (a[j + l] + tmp) % mod;
}
}
}
if(inv) {
for(int i = 0; i < n; i++) {
a[i] = (a[i] * nrev) % mod;
}
}
}
void multiply(vector<long long> &a, vector<long long> b, int root = 3) {
int n = (int)a.size() + (int)b.size() - 1;
while(n & (n - 1)) n++;
a.resize(n);
b.resize(n);
init(n, root);
ntt(a, n);
ntt(b, n);
for(int i = 0; i < n; i++) {
a[i] = (a[i] * b[i]) % mod;
}
ntt(b, n, true);
ntt(a, n, true);
while(a.back() == 0) a.pop_back();
}
}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, s;
cin >> n >> m >> s;
// auto start = chrono::high_resolution_clock::now();
vector<long long> v(m + 1, 1), ans(1, 1);
while(n) {
if(n & 1) {
ntt::multiply(ans, v);
if(ans.size() > s + 1) ans.resize(s + 1);
}
ntt::multiply(v, v);
if(v.size() > s + 1) v.resize(s + 1);
n >>= 1;
}
ans.resize(s + 1);
cout << ans[s] << "\n";
// auto stop = chrono::high_resolution_clock::now();
// cerr << chrono::duration_cast<chrono::milliseconds>(stop - start).count() << "\n";
return 0;
}