Centroid Conundrum

Let \(x = 40^{76^{93}}\) and consider \(n\) points on the plane, where the \(i\)th point is \(P_i = (x^i, 0)\). We perform \(m\) operations. In each operation we select two (distinct) points \(A\) and \(B\), then rotate \(A\) clockwise about \(B\) by \(60^\circ\) (i.e. multiply the vector \(A-B\) by \(e^{-\pi i/3}\) ) and finally remove point \(B\) from the set of points.

After performing all \(m\) operations the number of remaining points is \(n-m\). Denote by \(G\) the centroid (i.e. the arithmetic mean) of the remaining points. The final position of \(G\) can be written as a \(\mathbb{Z}[e^{-\pi i/3}]\)-linear combination of the numbers \(x,x^2,\dots,x^n\) (which, because \(x\) is enormous, may be regarded as linearly independent over \(\mathbb{Z}[e^{-\pi i/3}]\)). In other words, each outcome is uniquely determined by a tuple of coefficients \(c_1,\dots,c_n\) (with \(\sum_{i=1}^n c_i = 1\) ) so that

[ G = \frac{c_1 x + c_2 x^2 + \cdots + c_n x^n}{n-m}. ]

It turns out that every operation is an affine (but not average) transformation: if we denote (e = e^{-\pi i/3} = \frac12 - \frac{\sqrt3}{2}i) then the operation replacing (A) and (B) by

[ C = B + e (A - B) = e,A + (1-e),B ]

preserves the property that the total coefficient is (1) (each initial point starts with coefficient (1) and every operation replaces two coefficients (a) and (b) by (e,a+(1-e),b)). Hence each final remaining point is a weighted sum of the original (x^i)’s, with weights of the form

[ \prod_{j=1}^{d} \Bigl(e\Bigr)^{r_j} \Bigl(1-e\Bigr)^{d_j - r_j}, \quad \text{with } r_j\in \mathbb{Z}{\ge0}, \quad \sum{j} d_j = \text{(number of merges in that tree)}]

so that the overall centroid is

[ G = \frac{1}{n-m}\sum_{i=1}^n \gamma_i x^i\quad\text{with}\quad \gamma_i \in \mathbb{Z}[e,1-e]. ]

Since the monomials (x^i) can be regarded as "independent", the number of possible centroid positions equals the number of possible distinct coefficient vectors ((\gamma_1,\dots,\gamma_n)) arising from some sequence of operations. It can be shown that this number is given by

[ \sum_{\substack{k_1+\cdots+k_{n-m}=n\k_i\ge1}} \frac{n!}{k_1!\cdots k_{n-m}!}\prod_{j=1}^{n-m} \binom{2k_j-2}{k_j-1} \pmod{998244353}. ]

Your task is to compute (modulo 998244353) the number of possible positions for the centroid (G) after the (m) operations.

Note: Although \(x\) is huge, since the \(x^i\) are in independent "directions" the answer depends only on the combinatorics of the operations.

inputFormat

The first and only line of input contains two integers \(n\) and \(m\) (2 ≤ n ≤ 407693, 1 ≤ m ≤ n-1).

outputFormat

Output one integer: the number of possible centroid positions modulo 998244353.

sample

2 1

2

</p>