Increasing Speed Limits

You were driving along a highway when the road police caught you for speeding. They had been following you for a while, and they were amazed that you kept accelerating the whole time without ever touching the brakes. Now you need an excuse that sounds plausible.

You decided to say "every speed limit sign I saw was in increasing order, so I kept accelerating". The officer laughs, tells you every sign placed along the stretch of highway you drove, in order, and says you could not have been lucky enough to see only the ones that happened to be in increasing order.

Estimate how much luck that would take. Count how many subsequences of the given sequence are strictly increasing. The empty subsequence does not count, since it would mean you looked at no sign at all.

Subsequences are distinguished by position, not by value. In the sequence $(1, 4, 2, 3, 5, 5)$, the strictly increasing subsequence with values $(1, 2, 5)$ is counted twice, because there are two ways to pick the $5$.

The first line contains the number of test cases $N$. The $N$ test cases follow.

The first line of each test case contains $n$, $m$, $X$, $Y$ and $Z$, separated by single spaces. $n$ is the length of the speed limit sequence, and $m$ is the length of the generating array $A$. The next $m$ lines contain the elements of $A$, one integer per line, from $A[0]$ to $A[m-1]$.

Using $A$, $X$, $Y$ and $Z$, the following pseudocode prints the speed limit sequence in order. mod is the remainder operation.

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

The input is generated this way only to keep the input small. It has nothing to do with how the problem is solved.

Limits:

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

For each test case, print one line in the form Case #T: S, where $T$ is the test case number and $S$ is the number of non-empty strictly increasing subsequences modulo $1000000007$.

With $n = 6$, $m = 2$, $X = 2$, $Y = 1000000000$, $Z = 6$ and $A = (1, 2)$, the pseudocode prints $1, 2, 0, 0, 0, 4$.