$\begin{aligned}\sum\limits_{i=0}^n\sum\limits_{j=0}^i S(i,j)\times(j!)\times 2^j&=\sum\limits_{i=0}^n\sum\limits_{j=0}^n2^j\sum\limits_{k=0}^n (-1)^{j-k}\tbinom{j}{k}k^i\\&=\sum\limits_{i=0}^n\sum\limits_{j=0}^n(-2)^j\sum\limits_{k=0}^j (-1)^k\tbinom{j}{k}k^i\\&=\sum\limits_{k=0}^nf(k)(-1)^k\sum\limits_{j=0}^{n}\tbinom{j}{k}(-2)^j \end{aligned}$

其中，$f(k)=\sum_{i=0}^n k^i$

就是这一坨$\sum\limits_{j=0}^{n}\tbinom{j}{k}(-2)^j$，不好求。

运用有限微积分公式$\sum u\Delta v=uv-\sum Ev\Delta u$，

设$\Delta v=(-2)^j,u=\tbinom{j}{k}$，可以很轻松地得到:

$\Delta u=\tbinom{j+1}{k}-\tbinom{j}{k}=\tbinom{j}{k-1},v=\frac{(-2)^j}{-3}$

于是乎，

$\begin{aligned}\sum\limits_{j=0}^{n}\tbinom{j}{k}(-2)^j&=\sum\limits_{j=0}^{n+1}\tbinom{j}{k}(-2)^j\delta j\\&=[\frac{(-2)^j}{-3}\tbinom{j}{k}]|^{n+1}_{0}-\sum\limits_{j=0}^{n+1}\tbinom{j}{k-1}\frac{(-2)^{j+1}}{-3}\delta j\\&=[\frac{(-2)^j}{-3}\tbinom{j}{k}]|^{n+1}_{0}-\frac{-2}{-3}\sum\limits_{j=0}^{n+1}\tbinom{j}{k-1}(-2)^{j}\delta j\end{aligned}$

当$k=0$时，为

$[\frac{(-2)^j}{-3}\tbinom{j}{0}]|^{n+1}_{0}=\frac{(-2)^{n+1}}{-3}-\frac{1}{-3}$

当$k=1$时，

为$[\frac{(-2)^j}{-3}\tbinom{j}{1}]|^{n+1}_{0}-\frac{2}{3}[\frac{(-2)^j}{-3}\tbinom{j}{0}]|^{n+1}_{0}=[(n+1)\frac{(-2)^{n+1}}{-3}]-\frac{2}{3}[\frac{(-2)^{n+1}}{-3}-\frac{1}{-3}]$

当$k=2$时，

为$[\frac{(n+1)n}{2}\frac{(-2)^{n+1}}{-3}]-\frac{2}{3}\{[(n+1)\frac{(-2)^{n+1}}{-3}]-\frac{2}{3}[\frac{(-2)^{n+1}}{-3}-\frac{1}{-3}]\}$

发现可以递推。

$f(k)$可以转化为$\frac{k^{n+1}-1}{k-1}$线性求得。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define gc getchar()
#define ll long long
using namespace std;
const int mod=998244353,N=1e5+5;
template<class o>
inline void qr(o &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>
void qw(o x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
inline int ksm(int a,int b){int ans=1;for(;b;b>>=1,a=1ll*a*a%mod)if(b&1)ans=1ll*ans*a%mod;return ans;}
int pn[N],prime[N],inv[N],n,m;bool v[N];
void gp()
{
    inv[0]=1;inv[1]=1;m=0;pn[1]=1;
    for(int i=2;i<=n;i++)inv[i]=1ll*inv[mod%i]*(mod-mod/i)%mod;
    for(int i=2;i<=n;i++)
    {
        if(!v[i])prime[++m]=i,pn[i]=ksm(i,n+1);
        for(int j=1;j<=m&&1ll*i*prime[j]<=n;j++)
        {
            v[i*prime[j]]=1;pn[i*prime[j]]=1ll*pn[i]*pn[prime[j]]%mod;
            if(i%prime[j]==0)break;
        }
    }
}
int main()
{
    qr(n);if(n==1){puts("1");return 0;}
    gp();
    int t1=-1ll*ksm(-2,n+1)*inv[3]%mod,t2=-2*inv[3]%mod;
    int f0=-inv[3],fn=t1,ans=(fn-f0)%mod,bin=n+1;
    f0=1ll*t2*f0%mod,fn=(1ll*t1*(n+1)+1ll*t2*fn)%mod;
    ans=(ans-1ll*(n+1)*(fn-f0))%mod;
    for(int i=2;i<=n;i++)
    {
        bin=1ll*bin*(n+2-i)%mod*inv[i]%mod,f0=1ll*t2*f0%mod,fn=(1ll*t1*bin+1ll*t2*fn)%mod;
        ans=(ans+((i&1)?-1:1)*(1ll*inv[i-1]*(pn[i]-1)%mod*(fn-f0)))%mod;
    }
    qw((ans+mod)%mod);puts("");
    return 0;
}