K1-K2 Tree Expected Score

We call a rooted tree \(\mathcal{T}\) a \(k_1\!\!\! - k_2\)-ary tree if and only if every node \(p\) that has children has either exactly \(k_1\) children or exactly \(k_2\) children, where \(k_1 \neq k_2\). The children of every node are ordered, while the nodes themselves are unlabelled. Two such trees are defined to be isomorphic if and only if the following pseudo-code returns the same string for both trees:

1. Input: The edges of the tree \(\mathcal{T}\).
2. Output: The eigenvalue of the tree \(\mathcal{T}\).
3. Algorithm: dfs(u)
4.     result ← '(' 
5.     for each edge (u, v) in \(\mathcal{T}\)
6.         if v is not the father of u
7.             result ← result + dfs(v)
8.     result ← result + ')'
9.     return result
10. Method: check(\(\mathcal{T}\))
11.     return dfs(root of \(\mathcal{T}\))

A \(k_1\!\!\!-k_2\)-ary tree has a unique root, the order among the children of any node is significant, and nodes have no labels.

For a given \(k_1\!\!\!-k_2\) tree \(\mathcal{T}\) with n nodes, assign a score as follows: each node that is a \(k_1\)-ary node contributes a score of \(a\) and each node that is a \(k_2\)-ary node contributes a score of \(b\); leaf nodes contribute 0. The score of \(\mathcal{T}\) is defined as the sum of the scores of all its nodes, denoted by \(v(\mathcal{T})\).

Now, consider all the non-isomorphic \(k_1\!\!\!-k_2\) trees with n nodes. A tree \(\mathcal{T}\) is generated uniformly at random from this set, and let \(\mathbb{E}(v(\mathcal{T}))\) denote the expected score. It can be shown that \(\mathbb{E}(v(\mathcal{T}))\) is a rational number. When \(\mathbb{E}(v(\mathcal{T})) \neq 0\), write \[ \mathbb{E}(v(\mathcal{T})) = \frac{p}{q}, \quad \gcd(p,q)=1. \] You are required to compute the smallest natural number \(x\) such that \[ p \equiv qx \pmod{998244353}. \] It can be proven that such a natural number \(x\) exists. (In the case when \(\mathbb{E}(v(\mathcal{T})) = 0\), output 0.)

Input Format: The input consists of a single line containing five space‐separated integers: n k₁ k₂ a b, where n is the number of nodes in the tree, \(k_1\) and \(k_2\) are the two possible branching factors, and a and b are the scores associated with \(k_1\)-ary and \(k_2\)-ary nodes respectively.

Output Format: Output a single integer, namely the smallest natural number \(x\) that satisfies \(p \equiv qx \pmod{998244353}\), where \(\frac{p}{q}\) is the reduced fraction representing \(\mathbb{E}(v(\mathcal{T}))\). (If \(\mathbb{E}(v(\mathcal{T}))=0\), output 0.)

inputFormat

The input consists of a single line containing five integers n k1 k2 a b separated by spaces.

• n: the number of nodes in the tree.
• k1 and k2: the two possible numbers of children for an internal node (\(k1 \neq k2\)).
• a and b: the scores for a \(k1\)-ary node and a \(k2\)-ary node respectively.

outputFormat

Output a single integer: the smallest natural number \(x\) such that if \(\mathbb{E}(v(\mathcal{T})) = \frac{p}{q}\) in lowest terms (and nonzero), then \(p \equiv qx \pmod{998244353}\). If \(\mathbb{E}(v(\mathcal{T})) = 0\), output 0.

sample

1 2 3 5 7

0