题目描述

定义一棵树 $\mathcal T$ 为 $k_1-k_2$ 叉树，当且仅当每个节点 $p\in \mathcal T$ 有儿子，要么有 $k_1$ 个儿子，要么有 $k_2$ 个儿子，$k_1 \ne 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)) = 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))=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))$ 不为零。