题目分析

将每次添加的字符……看成一个节点（节点有标号）？！！

添加一个字符时删除的字符……都是它的儿子？！！

这样 0 就是叶子节点，1 就是非叶节点。任意一个添加字符的方案，构成了一种唯一的森林，而本题求的东西就变成了……这个森林只有一棵树，节点数为 $n$的方案数？！！

这什么神仙思路啊 (╯°Д°)╯︵ ┻━┻

然后设 $f(i)$表示 $i$个节点构成的树的方案数（该树根节点一定是一个字符 1），$g(i)$表示 $i$个节点构成的森林的方案数（森林里每棵树的根节点都是字符 1），$A(i)=[i \in A],B(i)=[i \in B]$，就有如下 DP 方程：

$$f(n)=\sum_{i=0}^{n-1} A(i)g(n-1-i)C_{n-1}^i + B(n-1)$$

$$g(n)=\sum_{i=1}^n f(i)g(n-i)C_{n-1}^{i-1}$$
其中 $f$的方程是考虑与根节点直接相连的叶子有几个，$g$是考虑 $1$号节点所在的那棵树的大小。

然后写成卷积的形式：

$$\frac{f(n)}{(n-1)!}=\sum_{i=0}^{n-1} \frac{g(n-1-i)}{(n-1-i)!}\frac{A(i)}{i!}+\frac{B(n-1)}{n-1}$$

$$\frac{g(n)}{n!}=\frac{1}{n}(\sum_{i=1}^n \frac{f(i)}{(i-1)!}\frac{g(n-i)}{(n-i)!})$$

发现 $f$的 DP 式中带的那个卷积其实卷出来是 $n-1$，所以将 $A(i)$整体往后平移一格，卷积式改成 $\sum_{i=1}^{n} \frac{A(i)}{(i-1)!} \frac{g(n-i)}{(n-i)!}$。

还有一点就是每次删除的子段不能为空，所以强制让 $B(0)=0$，最后全部算出来后再让 $f(1)+=1$（即只有一个字符 0 即可）

初值：$f(0)=0,g(0)=1$。

然后一个分治 NTT 即可解决，完结，撒花！

……个鬼啦！

这个分治 NTT 怎么做啊！$g$的方程里又有 $f$又有 $g$的！

我花了一下午在这上面啊！

好吧，其实是这样做的。首先，分治 NTT 的时候，是递归左半边区间，用 $[l,mid]$里的值去更新 $[mid+1,r]$中的值，然后递归右半边区间嘛。

对于 $f$，用 $[l,mid]$里的 $g$（已经求出正确的值了）和前 $r-l+1$项 $A$去卷积，加到右半边的 $f$中。

对于 $g$，用 $[l,mid]$里的 $f$（已经求出正确的值了）和前 $r-l+1$项 $g$去卷积，加到右半边的 $g$中。但是有一个问题，若 $l=1$，可能出现前 $r-l+1$项 $g$还没有完全算出的情况。

设 $i+j=k$，$j>mid$，$i \leq mid$，那么此时我们漏算了 $f(i)g(j)$对 $g(k)$的贡献。

不过没关系，当我们递归到一个左半边包含 $j$的 $[l,r]$（此时 $l \not= 1$）时，我们再用 $[l,mid]$里的 $g$和前 $r-l+1$项 $f$去卷积，加到右半边的 $g$中即可。

所以当 $l \not=1$时，要额外多卷积一次。

另外，注意不要不小心使用在本次卷积算贡献时，用被更新了的 $f$和 $g$去卷。

代码

#include<bits/stdc++.h>
using namespace std;
#define RI register int
int read() {
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
    return q;
}
const int mod=998244353,N=262150;
int n,ma,mb,ans;
int fac[N],inv[N],ifac[N],A[N],B[N],f[N],g[N],rev[N];
int k1[N],k2[N],k3[N],k4[N];

int qm(int x) {return x>=mod?x-mod:x;}
int ksm(int x,int y) {
    int re=1;
    for(;y;y>>=1,x=1LL*x*x%mod) if(y&1) re=1LL*re*x%mod;
    return re;
}
void NTT(int *a,int n,int x) {
    for(RI i=0;i<n;++i) if(rev[i]>i) swap(a[i],a[rev[i]]);
    for(RI i=1;i<n;i<<=1) {
        int gn=ksm(3,(mod-1)/(i<<1));
        for(RI j=0;j<n;j+=(i<<1)) {
            int t1,t2,g=1;
            for(RI k=0;k<i;++k,g=1LL*g*gn%mod) {
                t1=a[j+k],t2=1LL*g*a[j+i+k]%mod;
                a[j+k]=qm(t1+t2),a[j+i+k]=qm(t1-t2+mod);
            }
        }
    }
    if(x==1) return;
    reverse(a+1,a+n);int invn=ksm(n,mod-2);
    for(RI i=0;i<n;++i) a[i]=1LL*a[i]*invn%mod;
}

void prework() {
    fac[0]=1;for(RI i=1;i<=n;++i) fac[i]=1LL*fac[i-1]*i%mod;
    inv[0]=inv[1]=1,ifac[0]=1;
    for(RI i=2;i<=n;++i) inv[i]=1LL*(mod-mod/i)*inv[mod%i]%mod;
    for(RI i=1;i<=n;++i) ifac[i]=1LL*ifac[i-1]*inv[i]%mod;
}
void work(int l,int r) {
    int mid=(l+r)>>1,n=r-l+1,kn=1,len=0;
    while(kn<(n<<1)) kn<<=1,++len;
    for(RI i=0;i<kn;++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<(len-1));
    {   for(RI i=0;i<kn;++i) k1[i]=k2[i]=0;
        for(RI i=l;i<=mid;++i) k1[i-l]=g[i];
        for(RI i=1;i<=n;++i) k2[i]=1LL*A[i]*ifac[i-1]%mod;
        NTT(k1,kn,1),NTT(k2,kn,1);
        for(RI i=0;i<kn;++i) k1[i]=1LL*k1[i]*k2[i]%mod;
        NTT(k1,kn,-1);
        for(RI i=mid+1;i<=r;++i) f[i]=qm(f[i]+k1[i-l]);
    }
    {   for(RI i=0;i<kn;++i) k1[i]=k2[i]=0;
        for(RI i=l;i<=mid;++i) k1[i-l]=f[i];
        for(RI i=0;i<=n;++i) k2[i]=g[i];
        NTT(k1,kn,1),NTT(k2,kn,1);
        for(RI i=0;i<kn;++i) k1[i]=1LL*k1[i]*k2[i]%mod;
        NTT(k1,kn,-1);
        for(RI i=mid+1;i<=r;++i) g[i]=qm(g[i]+k1[i-l]);
    }
    if(l>1) {
        for(RI i=0;i<kn;++i) k1[i]=k2[i]=0;
        for(RI i=l;i<=mid;++i) k1[i-l]=g[i];
        for(RI i=0;i<=n;++i) k2[i]=f[i];
        NTT(k1,kn,1),NTT(k2,kn,1);
        for(RI i=0;i<kn;++i) k1[i]=1LL*k1[i]*k2[i]%mod;
        NTT(k1,kn,-1);
        for(RI i=mid+1;i<=r;++i) g[i]=qm(g[i]+k1[i-l]);
    }
}
void cdq(int l,int r) {
    if(l==r) {
        f[l]=qm(f[l]+1LL*B[l-1]*ifac[l-1]%mod);
        g[l]=1LL*qm(g[l]+f[l])*inv[l]%mod;
        return;
    }
    int mid=(l+r)>>1;cdq(l,mid),work(l,r),cdq(mid+1,r);
}
int main()
{
    n=read(),ma=read(),mb=read();
    for(RI i=1;i<=ma;++i) A[read()+1]=1;
    for(RI i=1;i<=mb;++i) B[read()]=1;
    prework();
    B[0]=0,g[0]=1,cdq(1,n),ans=1LL*f[n]*fac[n-1]%mod;
    if(n==1) ans=qm(ans+1);
    printf("%d\n",ans);
    return 0;
}