#include #include #include #include using namespace std; // ?? const int MOD = 998244353; // ?? const int G = 3; // ??? (Modular Exponentiation) long long power(long long base, long long exp) { long long res = 1; base %= MOD; while (exp > 0) { if (exp % 2 == 1) res = (res * base) % MOD; base = (base * base) % MOD; exp /= 2; } return res; } // ??? (Modular Inverse) long long modInverse(long long n) { return power(n, MOD - 2); } // ????????? vector fact; vector invFact; // ????????? void precompute_factorials(int n) { fact.resize(n + 1); invFact.resize(n + 1); fact[0] = 1; for (int i = 1; i <= n; i++) { fact[i] = (fact[i - 1] * i) % MOD; } invFact[n] = modInverse(fact[n]); for (int i = n - 1; i >= 0; i--) { invFact[i] = (invFact[i + 1] * (i + 1)) % MOD; } } // ??? C(n, r) long long nCr(int n, int r) { if (r < 0 || r > n) return 0; return (((fact[n] * invFact[r]) % MOD) * invFact[n - r]) % MOD; } // --- NTT (Number Theoretic Transform) Implementation --- // ????? (Bit-reversal permutation) void bit_reverse(vector& a, int n) { int j = 0; for (int i = 1; i < n; i++) { int bit = n >> 1; while (j & bit) { j ^= bit; bit >>= 1; } j ^= bit; if (i < j) { swap(a[i], a[j]); } } } // NTT ??? // invert: true for Inverse NTT void ntt(vector& a, bool invert) { int n = a.size(); // 1. ????? bit_reverse(a, n); // 2. ???? (Butterfly operations) for (int len = 2; len <= n; len <<= 1) { // len ?????????? long long wlen = power(G, (MOD - 1) / len); if (invert) wlen = modInverse(wlen); for (int i = 0; i < n; i += len) { long long w = 1; for (int j = 0; j < len / 2; j++) { long long u = a[i + j]; long long v = (a[i + j + len / 2] * w) % MOD; a[i + j] = (u + v) % MOD; a[i + j + len / 2] = (u - v + MOD) % MOD; w = (w * wlen) % MOD; } } } // 3. ? NTT ???? if (invert) { long long n_inv = modInverse(n); for (long long& x : a) { x = (x * n_inv) % MOD; } } } // ????? (Polynomial Multiplication) vector poly_mul(vector a, vector b) { int deg = a.size() + b.size() - 1; int n = 1; while (n < deg) n <<= 1; a.resize(n, 0); b.resize(n, 0); ntt(a, false); ntt(b, false); vector res(n); for (int i = 0; i < n; i++) { res[i] = (a[i] * b[i]) % MOD; } ntt(res, true); res.resize(deg); return res; } // ????? (Polynomial Inverse) // ?? A^{-1} mod x^n vector poly_inv(const vector& a, int n) { if (n == 1) return {modInverse(a[0])}; // ??? A_0^{-1} mod x^(n/2) vector a0_inv = poly_inv(a, (n + 1) / 2); int m = 1; while (m < 2 * n) m <<= 1; // A mod x^n vector A(a.begin(), a.begin() + min((int)a.size(), n)); A.resize(m, 0); // A_0^{-1} mod x^n a0_inv.resize(m, 0); ntt(A, false); ntt(a0_inv, false); vector B(m); for (int i = 0; i < m; i++) { // B = (2 * A_0^{-1} - A * (A_0^{-1})^2) mod x^n // B = A_0^{-1} * (2 - A * A_0^{-1}) mod x^n long long term = (A[i] * a0_inv[i]) % MOD; long long factor = (2 - term + MOD) % MOD; B[i] = (a0_inv[i] * factor) % MOD; } ntt(B, true); B.resize(n); return B; } // ????? (Polynomial Derivative) vector poly_der(const vector& a) { if (a.empty() || a.size() == 1) return {}; vector res(a.size() - 1); for (int i = 1; i < a.size(); i++) { res[i - 1] = (a[i] * i) % MOD; } return res; } // ????? (Polynomial Integral) vector poly_int(const vector& a) { if (a.empty()) return {0}; vector res(a.size() + 1, 0); for (int i = 0; i < a.size(); i++) { res[i + 1] = (a[i] * modInverse(i + 1)) % MOD; } return res; } // ????? (Polynomial Logarithm) // ?? ln(A) mod x^n. ?? A[0] = 1 vector poly_ln(const vector& a, int n) { if (a[0] != 1) return {}; // ?? A[0] = 1 // ln(A) = integral(A' * A^{-1}) vector a_inv = poly_inv(a, n); // A^{-1} mod x^n vector a_der = poly_der(a); // A' // ?? size ?????? int size = 1; while (size < n + a_der.size()) size <<= 1; vector a_inv_ntt = a_inv; a_inv_ntt.resize(size, 0); vector a_der_ntt = a_der; a_der_ntt.resize(size, 0); ntt(a_inv_ntt, false); ntt(a_der_ntt, false); vector mul_res(size); for (int i = 0; i < size; i++) { mul_res[i] = (a_der_ntt[i] * a_inv_ntt[i]) % MOD; } ntt(mul_res, true); mul_res.resize(n - 1); // ?? degree N-2 return poly_int(mul_res); // ??? degree N-1 } // ????? (Polynomial Exponentiation) // ?? exp(A) mod x^n. ?? A[0] = 0 vector poly_exp(const vector& a, int n) { if (n == 1) return {1}; // ??? H_0 = exp(A) mod x^(n/2) vector h0 = poly_exp(a, (n + 1) / 2); // L = ln(H_0) mod x^n vector L = poly_ln(h0, n); // R = A - L mod x^n vector R(n); for (int i = 0; i < n; i++) { long long a_i = i < a.size() ? a[i] : 0; long long l_i = i < L.size() ? L[i] : 0; R[i] = (a_i - l_i + MOD) % MOD; } R[0] = (R[0] + 1) % MOD; // H = H_0 * (1 + A - ln(H_0)) mod x^n // ????? H = H_0 * R mod x^n int size = 1; while (size < 2 * n) size <<= 1; vector h0_ntt = h0; h0_ntt.resize(size, 0); vector R_ntt = R; R_ntt.resize(size, 0); ntt(h0_ntt, false); ntt(R_ntt, false); vector res(size); for (int i = 0; i < size; i++) { res[i] = (h0_ntt[i] * R_ntt[i]) % MOD; } ntt(res, true); res.resize(n); return res; } // ?????? (Polynomial Exponentiation G^Q) // G(x)^Q mod x^n vector poly_q_pow(const vector& G, long long Q, int n) { // ?? G[0] = 1 // G^Q = exp(Q * ln(G)) // 1. ?? ln(G) mod x^n vector ln_G = poly_ln(G, n); // 2. ?? Q * ln(G) mod x^n vector A(n, 0); for (int i = 0; i < ln_G.size() && i < n; i++) { // ln_G[0] = 0, ?? A[0] = 0 A[i] = (ln_G[i] * Q) % MOD; } // 3. ?? exp(A) mod x^n return poly_exp(A, n); } void solve() { int N; long long P; cin >> N >> P; // ?? N ? 5e5?????? precompute_factorials(N); // --- 1. ?????? --- // N ???? N ? 1 (mod 4) if (N % 4 != 1) { cout << 0 << endl; return; } // ?? N_U (????) ? N_T (?????) long long N_U = (N - 1) / 4; long long N_T = (3LL * N + 1) / 4; // Q ??????? long long Q = N_T - P; // K ? c_i = d_i - 1 ??? // K = sum(d_i) - Q = (N-1 - 8P) - Q // K = N - 1 - 8P - (N_T - P) = N - 1 - 7P - N_T long long K_val = N - 1 - 7 * P - N_T; // P ??????P <= (N-5)/28 // K >= 0 ????? if (K_val < 0) { cout << 0 << endl; return; } // Q ????Q >= 0 if (Q < 0) { cout << 0 << endl; return; } // c_i <= 6 ????K <= 6Q if (K_val > 6 * Q) { cout << 0 << endl; return; } int K = (int)K_val; // --- 2. ????? --- long long ans = 1; // ????: C(N, N_T) * C(N_T, P) ans = (ans * nCr(N, N_T)) % MOD; ans = (ans * nCr((int)N_T, (int)P)) % MOD; // ???: (N-2)! / ((7!)^P * (3!)^N_U) // (N-2)! if (N >= 2) { ans = (ans * fact[N - 2]) % MOD; } else { // N=1, N=2 ????? N ? 1 (mod 4) // N >= 5 } // 7! ? 3! ??? long long inv7Fact = invFact[7]; long long inv3Fact = invFact[3]; // (7!)^{-P} ans = (ans * power(inv7Fact, P)) % MOD; // (3!)^{-N_U} ans = (ans * power(inv3Fact, N_U)) % MOD; // --- 3. ????? T_Q ??? --- // G(x) = sum_{c=0}^6 x^c / c! vector G(7); for (int c = 0; c <= 6; c++) { G[c] = invFact[c]; } // Q = N_T - P // T_Q = [x^K] G(x)^Q // ???????? H(x) = G(x)^Q mod x^{K+1} // ???????? n = K + 1 int n = K + 1; vector H = poly_q_pow(G, Q, n); // ???? T_Q = H[K] long long T_Q = H[K]; // --- 4. ???? --- ans = (ans * T_Q) % MOD; cout << ans << endl; } // ??? int main() { // ??????? I/O ?? ios_base::sync_with_stdio(false); cin.tie(NULL); solve(); return 0; }//eg