Revise paste 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;
}