Koxia and Game

Koxia and Mahiru are playing a game with three arrays $$$a$$$, $$$b$$$, and $$$c$$$ of length $$$n$$$. Each element of $$$a$$$, $$$b$$$ and $$$c$$$ is an integer between $$$1$$$ and $$$n$$$ inclusive.

The game consists of $$$n$$$ rounds. In the $$$i$$$-th round, they perform the following moves:

• Let $$$S$$$ be the multiset $$$\{a_i, b_i, c_i\}$$$.
• Koxia removes one element from the multiset $$$S$$$ by her choice.
• Mahiru chooses one integer from the two remaining in the multiset $$$S$$$.

Let $$$d_i$$$ be the integer Mahiru chose in the $$$i$$$-th round. If $$$d$$$ is a permutation$$$^\dagger$$$, Koxia wins. Otherwise, Mahiru wins.

Currently, only the arrays $$$a$$$ and $$$b$$$ have been chosen. As an avid supporter of Koxia, you want to choose an array $$$c$$$ such that Koxia will win. Count the number of such $$$c$$$, modulo $$$998\,244\,353$$$.

Note that Koxia and Mahiru both play optimally.

$$$^\dagger$$$ A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).