P13465 [GCJ 2008 #1C] Increasing Speed Limits

你在高速公路上行驶时因超速被交警拦下。原来他们一直在跟踪你，他们惊讶地发现你一路都在加速，完全没有踩刹车！现在你急需一个借口来解释这一切。 你决定说：“我看到的所有限速标志都是递增的，所以我一直在加速。”警察听后大笑，并把你经过的这段高速公路上所有的限速标志都告诉了你，并表示你不太可能这么幸运，刚好只看到了一段递增的标志。 现在你需要估算这种情况发生的概率，换句话说，就是要找出给定序列中有多少个不同的严格递增子序列。空子序列不计入答案，因为那意味着你根本没看任何限速标志！ 例如，$(1, 2, 5)$ 是 $(1, 4, 2, 3, 5, 5)$ 的一个递增子序列，并且我们要计数两次，因为有两种方式可以从原序列中选出 $(1, 2, 5)$。

第一行输入一个整数 $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 ``` 注意：输入的生成方式仅用于减小输入文件的体积，与解题方法无关。

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

**样例说明** 对于第 $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 翻译