U286657 ？

给定一个 $n$ 个节点，初始没有边的有标号图，以及一个操作参数$k$，求 $q$ 次操作后该图成为一个欧拉回路的概率。 操作定义： - 操作 $1$ 随机选定 $k$ 个点，对于每一个点，随机删除它的 $\text{max}(\text{deg}_u-2,0)$ 条边。其中，$\text{deg}_u$ 指点 $u$ 的度。 - 操作 $2$ 随机选定 $k$ 个点，将他们按照标号大小排序，然后依次连 $1$ 条无向边，特别的，标号最大的与标号最小的点之间需要连接一条边。 形式化的，有一个随机选择的点集 $a_1,a_2,\dots,a_k$，$\forall i \in[1,k)$，连接一条从 $a_i$ 到 $a_{i+1}$ 的边，当 $i=k$ 时，连接一条从 $a_k$ 到 $a_1$ 的边。 当**两个点之间**已经有了一条边时，操作 $2$ 不会带来新边。 答案对 $998244353$ 取模。

**本题采用压缩输入。** 输入共 $2$ 行。 第一行，输入三个正整数 $n$,$q$,$k$，含义入题目描述所示。 第二行，有 $\frac{q}{31}$ 个数，第 $i$ 个数 $a_i$ 表示操作的参数。 一个显然的结论，$\forall x \in \N$，都有： $$x=\sum_{i=0}^{30}2^i\cdot (q_i-1)$$ $\forall i \in[0,30],q_i\in\{1,2\}$。 你的任务即是将每一个 $a_i$ 分解成 $31$ 个数，含义如上,然后执行你解压后的每一个操作。

一行一个整数，表示答案。

对于所有的数据，满足：$1\le n\le 10^5,1\le q\le 10^6$。 保证 $q$ 是 $31$ 的倍数。