B.哈希树

题目描述

时隔两年，小 H 又一次在某场比赛中写了树哈希，他写出了以下的代码：

const int N = 1e6 + 10, B = 233, mod = 998244353; 

int hs[N], sz[N];
// hs[x] 表示节点 x 的 hash 值； sz[x] 表示 x 的子树节点总数

vector<int> tu[N];
// tu[x] 表示 x 的子节点

long long qpow(long long x, int y) {
    long long ans = 1;
    while (y) {
        if (y & 1) ans = ans * x % mod;
        x = x * x % mod;
        y >>= 1; 
    }
    return ans;
}

void dfs(int x) {
    hs[x] = sz[x] = 1;
    vector<pair<int, int>> V;
    for (int p : tu[x]) {
        dfs(p);
        V.push_back({sz[p], hs[p]});
        sz[x] += sz[p];
    }
    sort(V.begin(), V.end());
    // 按照子树大小排序
    for (auto now : V) {
        hs[x] = (hs[x] + qpow(B, now.first) % mod * now.second) % mod;
    }
}

事后，小 H 发现他的树哈希非常有意思，于是想要研究它的性质。 如果一棵有根树，每个节点的父亲节点编号都比这个节点大，那么小 H 就会非常喜欢它。 小 H 想知道，对于所有的 $n$ 个节点的“好树”，它们根节点的哈希值的和是多少？

---

输入格式

• 第一行一个整数 $T$，表示数据组数。
• 下面接着 $T$ 行，每行一个整数 $n$，表示树的节点数。

---

输出格式

• 输出 $T$ 行，每行一个整数，表示该组数据的答案。输出对 998244353 取模。

---

样例

样例输入

3
4
2
5

样例输出

76223160
234
164636081

---

题目说明

存在两棵 A, B 均为 $n$ 个节点的好树，当存在某个节点，在 A 和 B 两棵树中的父节点不同时，则 A 和 B 为不同树。