“真开心呢，凤同学。”——Asahina Mafuyu。
给出一个长度为 \(n\) 的排列 \(P\) 和一个定义在集合 \(\{1, 2, 3,\cdots, n − 1\}\) 上的函数 \(f\) ，我们称该排列“生成”的图为这样的一张图 \(G\)：

1. \(G\) 具有编号为 \(1\) 到 \(n\) 的 \(n\) 个顶点。
2. 如果 \(i < j\) 且 \(P_i > P_j\) （即 \((i, j)\) 为一个逆序对），那么在 \(G\) 中存在一条无向边 \((i, j)\)。

在此基础上，如果 \(D\) 是长度为正偶数的顶点序列 \(\{D_1 , D_2 , \cdots D_{2m-1} , D_{2m} \}\)，其中 \(m\) 是任意的正整数，并且满足以下性质：

1. \(\forall 1 \le k < 2m\)，\(D_k < D_{k+1}\)。
2. \(\forall 1 \le k \le m\)，存在一条无向边 \((D_{2k-1}, D_{2k})\)。
3. \(\forall 1 \le j, k \le m\)，\(j \neq k\)，图中不存在一条起点是 \(D_{2j}\)，终点是 \(D_{2k}\) 的简单路径。
   （即选择若干条顶点编号递增的边，并且任意两条边不在同一个连通块中）

则我们称序列 \(D\) 是“开心”的，记该序列的权值为 \(\prod _{k=1}^m f (P_{D_{2k-1}} - P_{D_{ 2k}})\)。

定义一个排列的权值为所有“开心”的序列 \(D\) 的权值之和，即

现在，你需要求出所有排列的权值之和对 \(998244353\) 取模的结果。

\(1 \le n \le 5000\)，\(1 \le f(i) \le 10^9\)。

#include <cstdio>
#include <algorithm>

#define int long long

using namespace std;

const int N = 5005;
const int mod = 998244353;
const int inv = mod + 1 >> 1;

int n, a[N], F[N], fac[N], f[N][2], g[N][2];

// f[i][0], g[i][0] 表示方案数，f[i][1], g[i][1] 表示权值和。

signed main()
{
    freopen("graph.in", "r", stdin);
    freopen("graph.out", "w", stdout);

    scanf("%lld", &n);
    for(int i = 1; i < n; ++ i)
        scanf("%lld", &a[i]);

    fac[0] = 1;
    for(int i = 1; i <= n; ++ i)
        fac[i] = fac[i - 1] * i % mod;

    g[0][0] = 1;
    for(int i = 1; i <= n; ++ i)
        g[i][0] = g[i - 1][0] * i % mod;
    for(int i = 2; i <= n; ++ i)
        for(int j = 1; j < i; ++ j)
            g[i][1] = (g[i][1] + a[j] * (i - j) % mod * fac[i - 2] % mod * i % mod * (i - 1) % mod * inv) % mod;
    
    f[1][0] = 1;
    for(int i = 2; i <= n; ++ i)
    {
        f[i][0] = g[i][0], f[i][1] = g[i][1];
        for(int j = 1; j < i; ++ j)
        {
            f[i][0] = (f[i][0] - g[j][0] * f[i - j][0]) % mod;
            f[i][1] = (f[i][1] - g[j][0] * f[i - j][1] - g[j][1] * f[i - j][0]) % mod;
        }
    }

    for(int i = 1; i <= n; ++ i)
        for(int j = 0; j < i; ++ j)
            F[i] = (F[i] + F[j] * f[i - j][1] + F[j] * f[i - j][0] + g[j][0] * f[i - j][1]) % mod;

    printf("%lld\n", (F[n] + mod) % mod);

    return 0;
}

彩梦喜欢一个集合 \(S\)，当且仅当存在另一个集合 \(T\) ，使得 \((S, T)\) 满足以下条件：

• \(\lvert S \rvert = n, \lvert T \rvert = m, 1 \in S\)。
• \(S \subseteq [1, nm] \cap \Z, T \subseteq \Z\)。
• \(\{i + j \mid i \in S, j \in T \} = \{1, 2, \cdots , nm\}\)。

给定 \(n, m\)，求彩梦喜欢的集合数量对质数 \(998244353\) 取模的值。
为了方便选手，\(n\) 和 \(m\) 都使用唯一分解形式给出。

给定的 \(n, m\) 分别为 \(\prod p_i^{x_i}\) 和 \(\prod p_i^{y_i}\)。

\(0 \le \sum_{x_i},\sum_{y_i} \le 2\times 10^5\)。

#include <cstdio>
#include <cassert>
#include <algorithm>

#define int long long

using namespace std;

const int N = 600005;
const int mod = 998244353;

int n = 600000, m, ans, lim, l, I, rev[N], a[N], b[N], f[N], g[N], h[N], fac[N], ifa[N];

int Pow(int x, int y)
{
    int r = 1;
    for(; y; y >>= 1, x = x * x % mod)
        if(y & 1)
            r = r * x % mod;
    return r;
}

void init(int n)
{
    for(l = 0, lim = 1; lim < n; lim <<= 1, ++ l);
    I = Pow(lim, mod - 2);
    for(int i = 0; i < lim; ++ i)
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << l - 1);
}

void NTT(int *a, int type)
{
    for(int i = 0; i < lim; ++ i)
        if(i < rev[i])
            swap(a[i], a[rev[i]]);
    for(int i = 1; i < lim; i <<= 1)
    {
        int x = Pow(type ? 3 : (mod + 1) / 3, (mod - 1) / (i << 1));
        for(int j = 0; j < lim; j += (i << 1))
        {
            for(int k = 0, y = 1; k < i; ++ k, y = y * x % mod)
            {
                int p = a[j + k], q = y * a[i + j + k] % mod;
                a[j + k] = (p + q) % mod;
                a[i + j + k] = (p - q) % mod;
            }
        }
    }
    if(!type)
        for(int i = 0; i < lim; ++ i)
            a[i] = a[i] * I % mod;
}

int C(int n, int m)
{
    return fac[n] * ifa[m] % mod * ifa[n - m] % mod;
}

signed main()
{
    freopen("set.in", "r", stdin);
    freopen("set.out", "w", stdout);

    fac[0] = ifa[0] = 1;
    for(int i = 1; i <= n; ++ i)
        fac[i] = fac[i - 1] * i % mod;
    ifa[n] = Pow(fac[n], mod - 2);
    for(int i = n - 1; i >= 0; -- i)
        ifa[i] = ifa[i + 1] * (i + 1) % mod;

    scanf("%lld", &m);
    for(int i = 1, x, u, v; i <= m; ++ i)
        scanf("%lld%lld%lld", &x, &u, &v), ++ a[u], ++ b[v];

    for(int i = 1; i <= 2e5; ++ i)
        f[i] = g[i] = 1;
    for(int i = 1; i <= 2e5; ++ i)
        if(a[i])
            for(int j = 1; j <= 2e5; ++ j)
                f[j] = f[j] * Pow(C(i + j - 1, j - 1), a[i]) % mod;
    for(int i = 1; i <= 2e5; ++ i)
        if(b[i])
            for(int j = 1; j <= 2e5; ++ j)
                g[j] = g[j] * Pow(C(i + j - 1, j - 1), b[i]) % mod;

    for(int i = 0; i <= 2e5; ++ i)
    {
        f[i] = f[i] * ifa[i] % mod;
        g[i] = g[i] * ifa[i] % mod;
        h[i] = ifa[i] * (i & 1 ? -1 : 1) % mod;
    }

    init(4e5 + 1);
    NTT(f, 1);
    NTT(g, 1);
    NTT(h, 1);
    
    for(int i = 0; i < lim; ++ i)
    {
        f[i] = f[i] * h[i] % mod;
        g[i] = g[i] * h[i] % mod;
    }

    NTT(f, 0);
    NTT(g, 0);

    for(int i = 0; i < lim; ++ i)
    {
        f[i] = f[i] * fac[i] % mod;
        g[i] = g[i] * fac[i] % mod;
    }

    for(int i = 1; i <= 2e5; ++ i)
    {
        ans = (ans + 2 * f[i] * g[i]) % mod;
        if(i)
            ans = (ans + f[i] * g[i - 1]) % mod;
        if(i != 2e5)
            ans = (ans + f[i] * g[i + 1]) % mod;
    }

    printf("%lld\n", (ans + mod) % mod);

    return 0;
}