我的 poly 模板

#include <bits/stdc++.h>
#include <assert.h>
using namespace std;
typedef long long ll;
typedef double db;
#define ep emplace_back
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define fout freopen("out.out","w",stdout);
#define fin freopen("in.in","r",stdin);
#define DE {cerr << "QAQ" << endl;}
#define dd(x) {cerr << (x) << endl}
inline int read() {
	int x=0, v=1,ch=getchar();
	while('0'>ch||ch>'9') {
		if(ch=='-') v=0;
		ch=getchar();
	}while('0'<=ch&&ch<='9') {
		x=(x*10)+(ch^'0');
		ch=getchar();
	}return v?x:-x;
}
const int MAX = 1e6 + 5, P = 998244353, G = 3, iG = 332748118;
int qpow(int x,int p){
	int r=1;
	for(;p;p>>=1,x=1ll*x*x%P)if(p&1)r=1ll*r*x%P;
	return r;
}
namespace poly {
	// N ?a 4 ±??￥é??? 
	#define N (524300)
	#define clr(f, n) memset(f, 0, sizeof(int) * n)
	#define cpy(f, g, n) memcpy(f, g, sizeof(int) * n)
	int tr[N], now = 0;
	void tpre(int n) {
		if(n == now) return ; now = n;
		for(int i = 0; i < n; ++ i) tr[i] = (tr[i >> 1] >> 1) | ((i & 1) ? (n >> 1) : 0);
	}
	int inc(int a, int b) { a += b; return (a >= P) ? a - P : a; }
	void NTT(int *f, int n, int op) {
		tpre(n);
		for(int i = 0; i < n; ++ i) if(i < tr[i]) swap(f[i], f[tr[i]]);
		static int w[N] = {1}; 
		for(int l = 1; l < n; l <<= 1) {
			int wG = qpow(op ? G : iG, (P - 1) / (l << 1));
			for(int i = 1; i < l; ++ i) w[i] = 1ll * w[i - 1] * wG % P;
			for(int i = 0; i < n; i += (l << 1)) {
				for(int j = 0; j < l; ++ j) {
					int a = f[i | j], b = 1ll * f[i | j | l] * w[j] % P;
					f[i | j] = inc(a, b);
					f[i | j | l] = inc(a, P - b);
				}
			}
		}
		if(op == 0) {
			int invn = qpow(n, P - 2);
			for(int i = 0; i < n; ++ i) f[i] = 1ll * f[i] * invn % P;
		}
	}
	void px(int *f, int *g, int n) {
		for(int i = 0; i < n; ++ i) f[i] = 1ll * f[i] * g[i] % P; 
	}
	void times(int *f, int *g, int len, int lim) {
		static int tmp[N];
		int n = 1; while(n < len + len) n <<= 1;
		clr(tmp, n), cpy(tmp, g, n);
		NTT(f, n, 1), NTT(tmp, n, 1);
		px(f, tmp, n), NTT(f, n, 0);
		clr(f + lim, n - lim), clr(tmp, n); 
	}
	void BF(int *f, int *g, int n) {
		static int h[N];
		memset(h, 0, sizeof(h));
		for(int i = 0; i < n; ++ i) 
			for(int j = 0; i + j < n; ++ j) 
				h[i + j] = inc(h[i + j], 1ll * f[i] * g[j] % P);
		for(int i = 0; i < n; ++ i) f[i] = h[i]; 
	}
	void myinv(int *f, int m) {
		int n = 1; for(n = 1; n < m; n <<= 1);
		static int w[N], r[N], sav[N];
		w[0] = qpow(f[0], P - 2);
		for(int len = 2; len <= n; len <<= 1) {
			for(int i = 0; i < (len >> 1); ++ i) r[i] = w[i];
			cpy(sav, f, len), NTT(sav, len, 1);
			NTT(r, len, 1), px(r, sav, len);
			NTT(r, len, 0), clr(r, (len >> 1));
			cpy(sav, w, len), NTT(sav, len, 1);
			NTT(r, len, 1), px(r, sav, len);
			NTT(r, len, 0);
			for(int i = len >> 1; i < len; ++ i) w[i] = inc(2ll * w[i] % P, P - r[i]) % P;
		} 
		cpy(f, w, m), clr(sav, n), clr(w, n), clr(r, n);
	}
	void mysqrt(int *f, int m) {
		int n = 1; while(n < m) n <<= 1;
		static int b1[N], b2[N]; b1[0] = 1;
		for(int len = 2; len <= n; len <<= 1) {
			for(int i = 0; i < (len >> 1); ++ i) b2[i] = inc(b1[i], b1[i]);
			myinv(b2, len);
			NTT(b1, len, 1), px(b1, b1, len), NTT(b1, len, 0);
			for(int i = 0; i < len; ++ i) b1[i] = inc(f[i], b1[i]);
			times(b1, b2, len, len); 
		} cpy(f, b1, m), clr(b1, n + n), clr(b2, n + n); 
	}
	
	int inv[N];
	void init(int lim) {
		inv[1] = 1;
		for(int i = 2; i <= lim; ++ i) {
			inv[i] = 1ll * inv[P % i] * (P - P / i) % P; 
		}
	}
	void dao(int *f ,int m) {
		for(int i=1;i<m;++i) {
			f[i-1] = 1ll * f[i] * i % P; 
		} f[m - 1] = 0;
	}
	void jf(int *f,int m) {
		for(int i=m;i;--i) 
			f[i] = 1ll * f[i-1] * inv[i] % P;
		f[0] = 0;
	}
	void myln(int *f, int m) {
		static int g[N];
		cpy(g, f, m);
		myinv(g, m), dao(f, m);
		times(f, g, m, m), jf(f, m - 1);
		clr(g, m);
	}
	void myexp(int *f,int m) {
		static int s[N], s2[N];
		int n = 1; while(n < m) n <<= 1;
		s2[0] = 1;
		for(int len = 2; len <= n; len <<= 1) {
			cpy(s, s2, len >> 1), myln(s, len);
			for(int i = 0; i < len; ++ i) s[i] = inc(f[i], P - s[i]);
			s[0] = inc(s[0], 1);
			times(s2, s, len, len);
		}  cpy(f, s2, m), clr(s, n), clr(s2, n);
	}
	void myqpow(int *f, int m, int k) {
		myln(f, m);
		for(int i = 0; i < m; ++ i) f[i] = 1ll * f[i] * k % P;
		myexp(f, m);
	}
} 
using namespace poly;
int n;
signed main() {
	n = read();
	
	return 0;
}