### 原根

#### 概念

1. $\omega_n^k$ 互不相同；
2. $\omega_{2n}^{2k}=\omega_n^k$；
3. $\omega_n^{k+\frac{n}{2}}=-\omega_n^k$
4. 当 $k \neq 0$ 时，$1+\omega_n^k+(\omega_n^k)^2+\cdots+(\omega_n^k)^{n-1}=0$。

##### 性质一

$1,g^q,g^{2q},\cdots,g^{(n-1)q}$ 互不相同。

##### 性质二

$\omega_{2n}=g^{\frac{q}{2}}(p=\frac{q}{2}\times2n+1)$，有 $\omega_{2n}^{2k}=g^{2k\frac{q}{2}}=g^{kq}=\omega_n^k$。

##### 性质三

$$\omega_n^n=g^{nq}=g^{p-1}\equiv1\pmod p$$

##### 性质四

\begin{aligned} S(\omega_n^k)&=1+\omega_n^k+(\omega_n^k)^2+\cdots+(\omega_n^k)^{n-1}\\ \omega_n^k S(\omega_n^k)&=\omega_n^k+(\omega_n^k)^2+(\omega_n^k)^3+\cdots+(\omega_n^k)^{n}\\ S(\omega_n^k)&=\frac{(\omega_n^k)^n-1}{\omega_n^k-1}\end{aligned}

### 例题

#### 思路

\begin{aligned}&\sum_{i=0}^ni^kC(n,i) \\ =& \sum_{i=0}^nC(n,i)\sum_{j=0}^kS(k,j)C(i,j)j! \\ =& \sum_{j=0}^kS(k,j)j!\sum_{i=0}^n C(n,j)C(n-j,i-j) \\ =& \sum_{j=0}^k S(k,j)j!C(n,j)2^{n-j}\end{aligned}

#### 代码

#include <bits/stdc++.h>
#define maxm 1048576
#define maxn 600005
#define ll long long
#define md 998244353
using namespace std;
int x=0,flag=1;char ch=getchar();
while(!isdigit(ch)&&ch!='-') ch=getchar();
if (ch=='-') flag=-1,ch=getchar();
while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch-'0'),ch=getchar();
return x*flag;
}
int n,m,rev[maxm+1],bit,s;
ll fac[maxn],inv[maxn],inv2;
ll wi[maxm+1],a[maxm+1],b[maxm+1];
ll ksm(ll a,ll b){
ll res=1;
while(b){
if (b&1) res=res*a%md;
a=a*a%md;b>>=1;
}
return res;
}
void init(){
fac[0]=wi[0]=1;
for (int i=1;i<=m+1;++i)
fac[i]=fac[i-1]*i%md;
inv[m+1]=ksm(fac[m+1],md-2);
for (int i=m+1;i>=1;--i)
inv[i-1]=inv[i]*i%md;
for (bit=1,s=2;(1<<bit)<2*m+2;++bit)
s<<=1;
ll c=ksm(3,(md-1)/s);
inv2=ksm(s,md-2);
for (int i=1;i<=s;++i){
if(i!=s) rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
wi[i]=wi[i-1]*c%md;
}
}
void ntt(ll *a,int n,int dft){
for (int i=0;i<n;++i)
if (i<rev[i]) swap(a[i],a[rev[i]]);
for (int step=1;step<n;step<<=1){
ll wn=dft?wi[n-n/(step<<1)]:wi[n/(step<<1)];
for (int j=0;j<n;j+=step<<1){
ll wnk=1;
for (int k=j;k<j+step;++k,(wnk*=wn)%=md){
ll t=wnk*a[k+step]%md;
a[k+step]=(a[k]-t+md)%md;
(a[k]+=t)%=md;
}
}
}
if (dft)
for (int i=0;i<n;++i)
(a[i]*=inv2)%=md;
}
int main(){
if(m==0){
printf("%lld\n",ksm(2,n-1)*n%md*ksm(2,(ll)(n-1)*(ll)(n-2)/2)%md);
return 0;
}
init();
ll ans=0,v=1,c=1;
int l=max(0,n-1-m);
for (int i=0;i<=m;++i)
a[i]=(inv[i]*v+md)%md,
b[i]=ksm(i,m)*inv[i]%md,v=-v;
ntt(a,s,0),ntt(b,s,0);
for (int i=0;i<s;++i)
(a[i]*=b[i])%=md;
ntt(a,s,1);
ll vs=ksm(2,n-1);
for (int i=n-1;i>=l;--i){
ans=(ans+vs*a[n-1-i]%md*c%md)%md;
vs=vs*inv[2]%md;
c=c*(ll)i%md;
}
ans=ans*(ll)n%md*ksm(2,(ll)(n-1)*(ll)(n-2)/2)%md;
printf("%lld\n",(ans+md)%md);
return 0;
}