#include #include #include #include using namespace atcoder; using mint = modint998244353; using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf 1000000000000000 struct FPS:vector{ using vector::vector; FPS(const vector &x):vector(x){ } FPS pow(long long n,int maxDegree = -1){ if(maxDegree==-1)maxDegree = (*this).size() - 1; FPS now = (*this); FPS ret(1,1); while(n!=0){ if(n&1){ ret *= now; } n>>=1; if(n==0)break; now *= now; while(now.size()>maxDegree+1)now.pop_back(); while(ret.size()>maxDegree+1)ret.pop_back(); } while(ret.size()>maxDegree+1)ret.pop_back(); return ret; } FPS inv(int maxDegree = -1){ if(maxDegree==-1)maxDegree = (*this).size() - 1; FPS ret(1,(*this)[0].inv()); int m = 1; while(mm)ret.pop_back(); } while(ret.size()>maxDegree+1)ret.pop_back(); return ret; } FPS &operator+=(mint another){ *this += FPS(1,another); return (*this); } FPS operator+(mint another)const{ return (FPS(*this)+=another); } FPS &operator+=(const FPS &another){ if((*this).size()>N>>K; FPS F(N+1,1); for(int i=1;i<=N;i++){ F[i] = F[i-1] * i; } F.back() = F.back().inv(); for(int i=N-1;i>=1;i--){ F[i] = F[i+1] * (i+1); } FPS ans = F.pow(K,N); F -= 1; F = -F + 1; if(K&1){ ans += F.pow(K,N); } else{ ans -= F.pow(K,N); } mint Ans = ans[N]; Ans /= 2; for(int i=1;i<=N;i++)Ans *= i; cout<