Snuke 见到了一个空的黑板、

Snuke 要在黑板上进行 $N$ 次操作，第 $i$ 次操作选择一个 $[1,a_i]$ 中的正整数，将之写在黑板上。

写完 $N$ 个数之后，先手太郎和后手次郎要在黑板上玩游戏。先手太郎先开始，两人轮流进行以下操作：

• 考虑当前黑板上的最大数 $X$。
  • 若 $X=0$，则当前操作的玩家获胜，游戏结束。
• 选择一个 $[1,X]$ 中的正整数 $m$。
• 将 $N$ 个数全部对 $m$ 取模。

对于 Snuke 所有可能的 $\prod_{i=1}^Na_i$ 种写数字的方法，若两人都采取最优策略，请求出先手太郎能获胜的情况数取模 $998244353$ 的结果。