在藏蓝铁路的碧水湖大桥落成之际，一群铁路工程蚤聚在一起，庆祝这一伟大的建筑工程。

他们在桥上放置了代表各个工程团队的 $n$ 个石堆，每一个石堆代表了一个工程团队带来的材料和设备。

根据工程蚤 M 蚤的说法，他们为了保证碧水湖大桥的稳定性，特意研制了一种名为「跳蚤搭堆法」的搭建材料方法。为了体现这种方法的优越性，每个石堆由至少一个石子按顺序排布再根据「跳蚤搭堆法」依次搭建形成，相当于可以用一个非空有序列表描述，石子的数量代表了该团队所贡献的资源数量。每个石子还根据其大小分配了一个不大于 $m$ 的正整数编号，象征着这份资源对大桥工程所带来的贡献大小。不同石子之间的编号可能相同。对于两个编号相同的石子，我们认为它们是相同的。

为了纪念这一时刻，工程蚤们决定将这些石堆合并成一个大石堆，从而来构建一个代表团结和合作的雕塑。

由于「跳蚤搭堆法」的特性，合并两个石堆 $A$ 和 $B$ 的过程可以用如下 C++ 代码表示：

#define stone int
#define stones std::vector<stone>
stones merge(stones A, stones B)
{
    stones C;
    while (A.size() && B.size())
        if (A[0] <= B[0])
            C.push_back(A[0]), A.erase(A.begin());
        else
            C.push_back(B[0]), B.erase(B.begin());
    while(A.size())
        C.push_back(A[0]), A.erase(A.begin());
    while(B.size())
        C.push_back(B[0]), B.erase(B.begin());
    return C;
}

返回的石堆就是最终搭建的结果。

作为睿智的数学家伏特，你当然看出来这就是所谓的「二路归并算法」，只是石堆内部的石子不一定有序。

工程蚤们首先选择了一个基础的石堆 $A_1$，然后依次选择其他的石堆与其合并。

合并的规则如下：对于 $i=2,3,\dots,n$，他们选择石堆 $A_1$ 与 $A_i$ 合并，形成一个新的大石堆，作为新的石堆 $A_1$。

完成所有合并后，他们惊奇地发现：$A_1$ 的大小恰好为 $m$！而里面的石头编号依次为 $a_1,a_2,\dots,a_m$。

这个时候跳蚤国王来了，他看到这个雕塑非常满意。他问道：“在开始的时候，这些石堆是怎样的呢？”

他想知道，给定合并后的石堆，有多少种可能的初始石堆 $A_1,A_2,\dots,A_n$ 组合可以得到这样的结果。

作为杰出的数学家伏特，你能帮助跳蚤国王解决这个问题吗？

你需要计算有多少种可能的初始石堆形态，并输出答案模 $998244353$ 后的值。由于可能搭建过程难免会产生失误，可能会没有合法方案，如果这样请输出 $0$。

简要题意

目前有 $n$ 个非空数组 $A_1,A_2,\dots,A_n$（每个数组内部不一定有序），其元素均在 $[1,m]$ 之间。

对 $i=2,3,\dots,n$ 依次执行 $A_1\leftarrow\textrm{merge}(A_1,A_i)$ 后，$A_1$ 大小恰为 $m$，且 $A_1$ 中的元素依次为 $a_1,a_2,\dots a_m$。

现给定 $a_1,a_2,\dots,a_m$，问有多少种可能的初始数组 $A_1,A_2,\dots,A_n$，对 $998244353$ 取模。

无解时请输出 $0$。

输入格式

第一行三个整数 $n,m,o$，其中 $o$ 表示该测试点的一些特殊性质（请参见「数据范围」一节的描述）。

接下来一行 $m$ 个整数，依次为 $a_1,a_2,\dots a_m$。

输出格式

一行一个整数，表示方案数对 $998244353$ 取模后的结果。

样例一

input

3 8 0
1 3 4 2 5 2 7 8

output

540

样例二

input

4 8 0
2 4 1 4 1 2 3 2

output

0

样例三 $\sim$ 样例二十

见附件下载。

M 蚤的小提示

为了方便非 C++ 选手的理解，善良的 M 蚤给了你在「跳蚤搭堆法」下合并两个石堆的一份伪代码：

$ \begin{aligned} &\mathop{\bf function}\textrm{merge}(\mathop{\bf stones}A,\mathop{\bf stones}B)\\ &\quad\mathop{\bf stones}C\leftarrow\varnothing\\ &\quad\mathop{\bf while}A\neq\varnothing\land B\neq\varnothing\\ &\quad\quad x\leftarrow\textrm{the first stone of }A\\ &\quad\quad y\leftarrow\textrm{the first stone of }B\\ &\quad\quad\mathop{\bf if}x\le y\\ &\quad\quad\quad C\textrm{ push back }x\\ &\quad\quad\quad\textrm{pop the front of }A\\ &\quad\quad\mathop{\bf else}\\ &\quad\quad\quad C\textrm{ push back }y\\ &\quad\quad\quad\textrm{pop the front of }B\\ &\quad\quad\mathop{\bf fi}\\ &\quad\mathop{\bf end}\mathop{\bf while}\\ &\quad\mathop{\bf while}A\neq\varnothing\\ &\quad\quad x\leftarrow\textrm{the first stone of }A\\ &\quad\quad C\textrm{ push back }x\\ &\quad\quad\textrm{pop the front of }A\\ &\quad\mathop{\bf end}\mathop{\bf while}\\ &\quad\mathop{\bf while}B\neq\varnothing\\ &\quad\quad x\leftarrow\textrm{the first stone of }B\\ &\quad\quad C\textrm{ push back }x\\ &\quad\quad\textrm{pop the front of }B\\ &\quad\mathop{\bf end}\mathop{\bf while}\\ &\quad\mathop{\bf return}C\\ &\mathop{\bf end}\mathop{\bf function} \end{aligned} $

数据范围

所有数据保证 $2\le n\le2\times10^5$，$n\le m\le5\times10^5$，$1\le a_i\le m$，$0\le o\le 5$。

具体的数据规模分布可以见下表。$o$ 为指示特殊性质的参数，其含义将在之后注明。

接下来阐述关于 $o$ 的特殊性质。

• 当 $o\in\{1,3,5\}$ 时，保证 $\forall1\le i< m,a_i\le a_{i+1}$。
• 当 $2\le o\le3$ 时，保证 $\forall1\le i< m,a_i\le20$。
• 当 $4\le o\le5$ 时，保证每种编号出现次数均不超过 $5$ 次。

时间限制：$2\texttt{s}$

空间限制：$1\texttt{GB}$