Background

With Cirno’s careful care, the hexagon has grown into a cute parallelogram-like hexagon.

Now, Cirno really wants to know how strong its fighting power is.

Problem Description

In this cute parallelogram-like hexagon, the angle between every pair of adjacent sides is $\frac{2\pi}{3}$. The lengths of the three pairs of opposite sides are $a$, $b$, and $c$ units, respectively, as shown in the figure.

During the fighting power evaluation, the evaluator builds, for each line containing a side of the hexagon, a family of parallel lines spaced $\frac{\sqrt{3}}{2}$ units apart. In this way, the hexagon warrior is divided into several equilateral triangles, as shown in the figure.

The evaluator then connects all equilateral triangles that share a common edge. Since there is no odd cycle, it is easy to see that this is a bipartite graph. Then the evaluator tries to construct a perfect matching of this bipartite graph, as shown in the figure.

The fighting power of this hexagon warrior is the number of possible perfect matchings of the above bipartite graph. As a trainee evaluator, you need to help Cirno compute the fighting power of this hexagon.

Since the answer may be too large, you only need to output it modulo $998244353$.

Input Format

One line with three integers separated by spaces, representing $a$, $b$, and $c$.

Output Format

One line with one integer, representing the fighting power of the hexagon warrior modulo $998244353$.

1 1 1

2

3 4 3

4116

Hint

Constraints and Notes

For $100\%$ of the data, it is guaranteed that $1 \le a, b, c \le 10^6$.

Subtasks

Subtask 1 ($10$ points): $a, b, c \le 3$.

Subtask 2 ($10$ points): $a, b, c \le 8$.

Subtask 3 ($70$ points): $a, b, c \le 100$.

Subtask 4 ($10$ points): No special constraints.

Hint

• Krattenthaler’s formula
  $\displaystyle\det\left(\prod\limits_{k=2}^j(x_i+a_k)\prod\limits_{k=j+1}^n(x_i+b_k)\right)_{i,j=1}^{n}=\prod\limits_{1\le i<j\le n}{(x_i-x_j)}\prod\limits_{2<i\le j\le n}(a_i-b_j)$。

Translated by ChatGPT 5