Description

你在高速公路上行驶时因超速被交警拦下。原来他们一直在跟踪你，他们惊讶地发现你一路都在加速，完全没有踩刹车！现在你急需一个借口来解释这一切。

你决定说：“我看到的所有限速标志都是递增的，所以我一直在加速。”警察听后大笑，并把你经过的这段高速公路上所有的限速标志都告诉了你，并表示你不太可能这么幸运，刚好只看到了一段递增的标志。

现在你需要估算这种情况发生的概率，换句话说，就是要找出给定序列中有多少个不同的严格递增子序列。空子序列不计入答案，因为那意味着你根本没看任何限速标志！

例如，$(1, 2, 5)$ 是 $(1, 4, 2, 3, 5, 5)$ 的一个递增子序列，并且我们要计数两次，因为有两种方式可以从原序列中选出 $(1, 2, 5)$。

Input Format

第一行输入一个整数 $N$，表示测试用例的数量。接下来有 $N$ 组测试数据。每组测试数据的第一行为 $n$、$m$、$X$、$Y$ 和 $Z$，用空格分隔。$n$ 表示限速标志序列的长度，$m$ 表示生成数组 $A$ 的长度。接下来的 $m$ 行，每行一个整数，依次为 $A[0]$ 到 $A[m-1]$。

使用 $A$、$X$、$Y$ 和 $Z$，按照如下伪代码生成限速标志序列。mod 表示取余操作。

for i = 0 to n-1
  print A[i mod m]
  A[i mod m] = (X * A[i mod m] + Y * (i + 1)) mod Z

注意：输入的生成方式仅用于减小输入文件的体积，与解题方法无关。

Output Format

对于每个测试用例，输出一行，格式为 “Case #$T$: $S$”，其中 $T$ 表示测试用例编号，$S$ 表示非空严格递增子序列的数量，对 $1\ 000\ 000\ 007$ 取模。

2
5 5 0 0 5
1
2
1
2
3
6 2 2 1000000000 6
1
2

Case #1: 15
Case #2: 13

Hint

样例说明

对于第 $2$ 个测试用例，限速标志序列应为 $1, 2, 0, 0, 0, 4$。

数据范围

• $1 \leq N \leq 20$
• $1 \leq m \leq 100$
• $0 \leq X \leq 10^9$
• $0 \leq Y \leq 10^9$
• $1 \leq Z \leq 10^9$
• $0 \leq A[i] < Z$

小数据范围（15 分，测试点 1 - 可见）

• $1 \leq m \leq n \leq 1000$

大数据范围（35 分，测试点 2 - 隐藏）

• $1 \leq m \leq n \leq 500000$

由 ChatGPT 4.1 翻译