Description

有 $n$ 次操作，每次操作会等概率地进行以下事件中的一个：

1. 将 $a_i$ 加入团队，操作后 $a_i$ 为成员。
2. 将 $a_i$ 踢出团队。
3. 将 $a_i$ 设置为管理员。
4. 将 $a_i$ 设置为成员。

注意：

• 开始时没有人在团队里。
• 如果 $a_i$ 不在团队中，则 2、3、4 操作无效果。
• 如果 $a_i$ 为成员，则 1、4 操作无效果。
• 如果 $a_i$ 是管理员，则 1、2、3 操作无效果。

最后输出团队中管理员个数的期望，答案对 $998244353$ 取模。

Input Format

第一行一个整数 $\text{type}$。
如果 $\text{type}$ 为 $1$，则采用第一种输入方式，否则采用第二种输入方式。

第一种输入方式：

第一行一个正整数 $n$。
第二行共 $n$ 个整数表示数组 $a$。

第二种输入方式：

共一行四个整数分别是 $n,a_0,p,q$。

注意：第二种输入方式中，数组 $a$ 需要你计算得出，满足 $a_i=(a_{i-1}\times p+p)\bmod q+ 1$ $(i \geq 1)$。

Output Format

输出一个整数表示团队中管理员个数的期望，对 $998244353$ 取模。

1
6
1 1 2 1 2 1

760381441

2
11 4 5 14

686292993

Hint

本题采用捆绑测试。

对于所有数据，$1\le n\le 10^{18}$。