本题在 2021 CoE 挑战编程 II 中作为 E 题使用。

采用了 metaphysis 修缮后的题面。

题目描述

定义一棵树 $\mathcal T$ 为 $k_1-k_2$ 叉树，当且仅当每个节点 $p\in \mathcal T$ 有儿子，要么有 $k_1$ 个儿子，要么有 $k_2$ 个儿子。

我们定义两颗 $k_1-k_2$ 树同构，当且仅当下面伪代码返回的字符串相同：

$$\begin{array}{ll} 1 & \textbf{Input. } \text{The edges of the tree } \mathcal T \\ 2 & \textbf{Output. } \text{The eigenvalue of tree } \mathcal T.\\ 3 & \textbf{Algorithm. } \text{dfs}(u)\\ 4 & \qquad result \gets \texttt{'('} \\ 5 & \qquad \textbf{for} \text{ each } (u, v) \text{ in the } \mathcal T \\ 6 & \qquad \qquad \textbf{if } v \text{ is not the father of } u \\ 7 & \qquad \qquad\qquad result \gets result\ +\ \mathrm{dfs}(v) \\ 8 & \qquad result\gets result\ +\ \texttt{')'} \\ 9 & \qquad \textbf{return } result \\ 10 & \textbf{Method. } \text{check}(\mathcal T) \\ 11 & \qquad \textbf{return } \text{dfs(the root of the tree } \mathcal T\text{)} \end{array} $$

形式化地，$k_1-k_2$ 叉树有确定的根节点，每个节点的若干儿子之间有顺序，但是节点没有标号。

若 $k_1-k_2$ 叉树 $\mathcal T$ 有一个 $k_1$ 叉节点，则得分 $a$，若有一个 $k_2$ 叉节点，则得分 $b$，叶节点无得分。定义一棵树的得分为其所有节点的得分之和，记为 $v(\mathcal T)$。

现在我们在所有互不同构的 $n$ 个节点的 $k_1-k_2$ 叉树中等概率随机生成一棵 $\mathcal T$，记 $v(\mathcal T)$ 的期望值为 $\mathbb{E}(v(\mathcal T))$。

可以证明 $\mathbb{E}(v(\mathcal T))$ 为有理数。当 $\mathbb{E}(v(\mathcal T))$ 不为零时，令答案 $\mathbb{E}(v(\mathcal T)) = \dfrac{p}{q}$，其中 $p$ 与 $q$ 互质。你需要输出最小的自然数 $x$ 使得 $p\equiv qx\pmod P$，其中 $P=998244353$，可以证明这样的自然数 $x$ 必定存在。

输入格式

一行输入五个整数 $k_1,k_2,n,a,b$，含义如题面所示。

输出格式

一行输出一个自然数 $x$，表示方程 $p\equiv qx\pmod P$ 的解，其中 $P=998244353$。

2 3 6 1 2

3

样例说明

具有 $6$ 个结点的不同构 $2-3$ 叉树共有 $5$ 棵，每棵得分均为 $3$ 分，则 $\mathbb{E}(v(\mathcal T))= \dfrac {15} 5=3$，故 $p=3$ 且 $q=1$，则 $x=3$。

数据范围

共 $10$ 个测试点。
对于测试点 $1$，满足 $1 \le k_1,k_2<n\leq 10$。
对于测试点 $2$，满足 $1 \le k_1,k_2<n\leq 15$。
对于测试点 $3\sim 4$，满足 $1 \le k_1,k_2<n\leq 5 \times 10^3$。
对于测试点 $5\sim 6$，满足 $a=b=1$，$1 \le k_1,k_2<n\leq 10^5$。
对于 $100\%$ 的数据，满足 $1 \le k_1,k_2<n\leq 10^7,k_1 \ne k_2,k_1+k_2 \le n$，$1 \le a,b\leq 10^7$ 。 测试数据保证 $\mathbb{E}(v(\mathcal T))$ 不为零。