首先发现j是可以枚举到n的，因为j>i时s(i,j)为0。

把第二类斯特林数按照容斥的定义转换一下。

由于第二类斯特林数是一个卷积的形式，可以枚举i后ntt求解，复杂度O(n^2logn)

变换一下枚举的顺序，把i移到最内层。

发现可以预处理一下sigema i^0+i^1+i^2+i^3.....i^n然后就o(nlogn)了。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #define N 1100000#define L 1100000#define eps 1e-7#define inf 1e9+7#define db double#define ll long long#define ldb long doubleusing namespace std;inline ll read(){ char ch=0; ll x=0,flag=1; while(!isdigit(ch)){ch=getchar();if(ch=='-')flag=-1;} while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return x*flag;}const ll d=3,mo=998244353;ll ksm(ll x,ll k){ ll ans=1; while(k) { if(k&1)ans=1ll*ans*x%mo; k>>=1; x=1ll*x*x%mo; } return ans;}ll inv(ll x){return ksm(x,mo-2);}ll rev[N];void ntt(ll *f,ll n,ll flag){ for(ll i=0;i
             
              >1]>>1)+(i&1)*(n>>1); for(ll i=0;i