权值和 plus
题号：NC265078
时间限制：C/C++/Rust/Pascal 5秒，其他语言10秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

给定素数 P 和一个包含 Q 个整数的集合 S，定义一个合法的构造方案包括两个长度均为 K 的数组 a, b 满足：

\bullet \displaystyle\prod_{i=1}^{K} a_i \equiv N \pmod {P}
\bullet \displaystyle\prod_{i=1}^{K} b_i \equiv M \pmod {P}
\bullet 对所有的 i = 1, 2, \ldots, K，满足 a_i, b_i 均属于集合 S。

对于一种合法的构造方案，它的权值为 \displaystyle\sum_{i=1}^K \min (a_i, b_i)。

请你计算所有合法的构造方案的权值的和。

输入描述:

第一行 5 个整数 P, Q, N, M, K (1 \leqslant P, Q, K \leqslant {10}^5, 0 \leqslant N, M < P)，其中 P 是素数。

第二行 Q 个互不相同的整数 S_1, S_2, \ldots, S_Q (0 \leqslant S_i < 998244353)，其中 S_i 表示集合 S 中的第 i 个数。

输出描述:

一行一个整数，表示所有合法的构造方案的权值的和。

由于答案可能很大，请输出答案对 998244353 取模之后的值。
示例1

输入

复制 
5 3 1 4 2
1 2 4

输出

复制 
20

说明

有 6 种合法的构造方案：

1. a = [1, 1], b = [1, 4]，权值为 1 + 1 = 2.
2. a = [1, 1], b = [2, 2]，权值为 1 + 1 = 2.
3. a = [1, 1], b = [4, 1]，权值为 1 + 1 = 2.
4. a = [4, 4], b = [1, 4]，权值为 1 + 4 = 5.
5. a = [4, 4], b = [2, 2]，权值为 2 + 2 = 4.
6. a = [4, 4], b = [4, 1]，权值为 4 + 1 = 5.

故所有合法构造方案的权值和为 2 + 2 + 2 + 5 + 4 + 5 = 20。
示例2

输入

复制 
5 4 0 4 3
114 514 1919 810

输出

复制 
1383075