Description

Define a tree $\mathcal T$ to be a $k_1-k_2$-ary tree if and only if every node $p \in \mathcal T$ that has children has either $k_1$ children or $k_2$ children, with $k_1 \ne k_2$. We define two $k_1-k_2$ trees to be isomorphic if and only if the strings returned by the following pseudocode are the same:

$$\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}$$

Formally, a $k_1-k_2$-ary tree has a fixed root, the children of each node are ordered, but the nodes are unlabeled.

If a $k_1-k_2$-ary tree $\mathcal T$ has a $k_1$-branching node, it gains score $a$; if it has a $k_2$-branching node, it gains score $b$; leaf nodes give no score. Define the score of a tree as the sum of the scores of all its nodes, denoted by $v(\mathcal T)$.

Now, among all pairwise non-isomorphic $k_1-k_2$-ary trees with $n$ nodes, we generate one tree $\mathcal T$ uniformly at random. Let the expected value of $v(\mathcal T)$ be $\mathbb{E}(v(\mathcal T))$.

It can be proven that $\mathbb{E}(v(\mathcal T))$ is a rational number. When $\mathbb{E}(v(\mathcal T)) \ne 0$, write $\mathbb{E}(v(\mathcal T)) = p/q$, where $p$ and $q$ are coprime. You need to output the smallest natural number $x$ such that $p \equiv qx \pmod P$, where $P = 998244353$. It can be proven that such a natural number $x$ must exist.

Input Format

The input contains five integers $k_1,\ k_2,\ n,\ a,\ b$, with meanings as described above.

Output Format

Output an integer $x$, the smallest natural number solution to $p \equiv qx \pmod P$, where $P = 998244353$.

2 3 6 1 2

3

Hint

Sample Explanation.

There are $5$ non-isomorphic $2-3$-ary trees with $6$ nodes. Each tree has score $3$, so $\mathbb{E}(v(\mathcal T)) = 15/5 = 3$. Therefore $p = 3$ and $q = 1$, so $x = 3$.

---

Constraints

There are $10$ test points in total.

For test point $1$, $1 \le k_1,\ k_2 < n \le 10$.

For test point $2$, $1 \le k_1,\ k_2 < n \le 15$.

For test points $3 \sim 4$, $1 \le k_1,\ k_2 < n \le 5 \times 10^3$.

For test points $5 \sim 6$, $a = b = 1,\ 1 \le k_1,\ k_2 < n \le 10^5$.

For $100\%$ of the testdata, $1 \le k_1,\ k_2 < n \le 10^7,\ k_1 \ne k_2,\ k_1 + k_2 \le n,\ 1 \le a,\ b \le 10^7$.

---

Notes

• The testdata guarantees that $\mathbb{E}(v(\mathcal T)) \ne 0$.

Translated by ChatGPT 5