Counting Colored Trees in a Bipartite Graph

In an undirected connected graph \(G\) there are exactly \(n\) black nodes, \(n\) white nodes and 1 red node. Every node is labeled. The graph has exactly \(2n\) edges and every pair of adjacent (i.e. directly connected) nodes have different colors. (Note: The problem statement has been updated so that any two adjacent nodes have distinct colors.)

The graph \(G\) is necessarily a tree on \(2n+1\) nodes (since any tree on \(2n+1\) nodes has exactly \(2n\) edges). The allowed edges are only those connecting nodes of different colors. In particular, edges are allowed only between a black node and a white node, between the red node and a black node, or between the red node and a white node.

Depending on the value of an input parameter type, you are to count the number of such graphs modulo \(998244353\) under two different conditions:

• \(\texttt{type} = 0\): No extra conditions.
• \(\texttt{type} = 1\): For every maximal connected subgraph (i.e. each connected component) of \(G \setminus \{\text{red}\}\) (that is, after removing the red node), exactly one node in that component is given a special mark. (All marked nodes are considered distinct.)

It can be shown that the total number of valid trees (i.e. spanning trees of the allowed complete bipartite graph on the black and white nodes with the red node attached) for the two cases are given by the formulas below. Let \(M = 998244353\). Then:

• For \(\texttt{type} = 0\), the answer is \[ A(n)= (n+1)^{2n-2} \cdot (2n+1) \pmod{M}. \]
• For \(\texttt{type} = 1\), the answer is \[ B(n)= (n+1)^{2n-2} \cdot (2n^2+3n) \pmod{M}. \]
  Explanation: Notice that when the red node is removed from the tree, the tree splits into several connected components. For \(\texttt{type} = 1\), from each such component (which consists only of black and white nodes) one vertex is chosen (in \(|C|\) ways if \(C\) is the vertex set of the component) as a special marked node. The extra multiplicative factor \(\prod_{\text{component } C}\, |C|\) then simplifies overall to the factor \((2n^2+3n)\) in the formula above. (You may verify that for instance when \(n=1\) the answers are 3 and 5 respectively.)

Your task is to compute the answer according to the value of \(n\) and \(\texttt{type}\).

inputFormat

The input consists of two space‐separated integers: \(n\) and \(\texttt{type}\) (which is either 0 or 1).

\(1 \le n \le 10^5\) (or as specified by the problem constraints).

outputFormat

Output a single integer, the answer modulo \(998244353\).

sample

1 0

3