考虑一切合法 c 均可以用如下方式得到：选 l_1 个位置排列 a_1 的元素；然后在后方排列 l_2 个 a_2 的元素，以此类推；记一个 a 序列的是一组。然后考虑所有空位 i，不难发现 i 上只要不放其所在位置所属的组（一个空位置 p 如果 p>r_k 且 p<r_{k+1}）则位置 p 属于组 k+1，最后的若干个空位不属于任何组）位于 i 后面的元素即可。
倘若我们已知 a 的排列，方案数是好计算的：每个空位的方案数均形如 m-k，其中 k 是同组被禁止放的数的个数，k\in[1,l_i]（当空位位于最后方时 k=0）。但我们不知道 a 的排列，于是考察以下计算方法：
看起来很不可做，但是注意到 $l_i\leq 5$，于是我们可以把所有相同的 $m-e$（$e\in[0,5]$）放在一起，我们考虑单独插入 $5$ 次，第 $i$ 次插入所有 $e=i$ 的空位，那么记 $e$ 为常数，枚举 $C$ 为这样的空位的总数量，$c_e$ 为满足 $m-(l_i-j+1)=e$ 的 $(i,j)$ 数对个数，那么单次插入的方案数就是
$\displaystyle\left(\sum_{\sum_{i,j:l_i-j+1=e}L_{i,j}=C}(m-e)^{C}\right)\binom{C+c_e-1}{C}$，后面是个插板。
不难发现可以卷积。把上式记作 $\displaystyle [x^C]F_e(x)=(m-e)^C\binom{C+c_e-1}{C}$，整个题的答案就是 $\displaystyle\left(\prod_{i=1}^k(l_i!)\right)[x^{n-\sum l}]\prod_{e=0}^5F_e(x)$，NTT 可以做到 $O(nl\log n)$。
fun fact：jly 有很牛的 $O(nl)$ 做法，但我没看懂 XD。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN 2000005
#define mod 998244353
typedef vector<int> poly;
int g,ig,gpow[25],igpow[25],rev[MAXN],fac[MAXN],inv[MAXN],ifac[MAXN];
inline int C( int n , int m ){ return n >= m ? fac[n] * ifac[m] % mod * ifac[n - m] % mod : 0; }
inline int fp( int x , int p ){
int res = 1;
while( p ){
if( p & 1 ) res = res * x % mod;
x = x * x % mod;
p >>= 1;
}
return res;
}
inline void polypre(){
g = 3,ig = fp( g , mod - 2 );
for( int i = 1 ; i <= 23 ; i ++ ) gpow[i] = fp( g , ( mod - 1 ) / ( 1 << i ) );
for( int i = 1 ; i <= 23 ; i ++ ) igpow[i] = fp( ig , ( mod - 1 ) / ( 1 << i ) );
}
inline int redadd( int x ){ return x >= mod ? x - mod : x; }
inline int reduce( int x ){ return x < 0 ? x + mod : x; }
inline void NTT( vector<int> &F , int typ ){
int len = F.size();
for( int i = 0 ; i < len ; i ++ ) rev[i] = ( rev[i >> 1] >> 1 ) | ( ( i & 1 ) * ( len >> 1 ) );
for( int i = 0 ; i < len ; i ++ ) if( i < rev[i] ) swap( F[i] , F[rev[i]] );
for( int i = 1 , t = 1 ; i < len ; i <<= 1 , t ++ ){
int step = typ == 1 ? gpow[t] : igpow[t];
for( int j = 0 ; j < len ; j += i << 1 ){
int omega = 1;
for( int k = 0 ; k < i ; k ++ , omega = omega * step % mod ){
int X = F[j + k],Y = omega * F[i + j + k] % mod;
F[j + k] = redadd( X + Y ),F[i + j + k] = reduce( X - Y );
}
}
}
if( typ == -1 )
for( int i = 0 , ilen = fp( len , mod - 2 ) ; i < len ; i ++ ) F[i] = F[i] * ilen % mod;
}
inline poly polymul( poly F , poly G ){
int n = F.size(),m = G.size(),L = n + m - 1;
int len = 1; while( len < L ) len <<= 1;
F.resize( len ),G.resize( len );
NTT( F , 1 ),NTT( G , 1 );
for( int i = 0 ; i < len ; i ++ ) F[i] = F[i] * G[i] % mod;
NTT( F , -1 ),F.resize( L );
return F;
}
int n,m,k,l[MAXN],c[6];
poly P;
inline void solve(){
scanf("%lld%lld%lld",&n,&m,&k);
for( int i = 1 ; i <= k ; i ++ ) scanf("%lld",&l[i]);
for( int i = 1 ; i <= k ; i ++ ){
int x;
for( int j = 1 ; j <= l[i] ; j ++ ) scanf("%lld",&x);
}
for( int e = 0 ; e <= 5 ; e ++ ) c[e] = 0;
for( int i = 1 ; i <= k ; i ++ )
for( int j = l[i] - 1 ; j >= 0 ; j -- ) c[l[i] - j] ++;
c[0] ++;
poly A; A.resize( n , 0 ),A[0] = 1;
for( int e = 0 ; e <= 5 ; e ++ ){
P.resize( n + 1 ); P[0] = 1;
for( int i = 1 ; i <= n ; i ++ ) P[i] = P[i - 1] * ( m - e ) % mod;
for( int i = 1 ; i <= n ; i ++ ) P[i] = P[i] * C( i + c[e] - 1 , i ) % mod;
A = polymul( A , P ); A.resize( n + 2 );
}
int sl = 0; for( int i = 1 ; i <= k ; i ++ ) sl += l[i];
int ans = A[n - sl];
for( int i = 1 ; i <= k ; i ++ ) ans = ans * fac[l[i]] % mod;
printf("%lld\n",ans);
}
signed main(){
polypre();
fac[0] = inv[1] = ifac[0] = 1;
for( int i = 1 ; i < MAXN ; i ++ ) fac[i] = fac[i - 1] * i % mod;
for( int i = 2 ; i < MAXN ; i ++ ) inv[i] = ( mod - mod / i ) * inv[mod % i] % mod;
for( int i = 1 ; i < MAXN ; i ++ ) ifac[i] = ifac[i - 1] * inv[i] % mod;
int testcase = 1;
while( testcase -- ) solve();
}
```