Increasing Speed Limits (Large)

You were driving along a highway when the road police pulled you over 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 badly need an excuse.

You decide it sounds reasonable to say "every speed limit sign I saw was in increasing order, that is why I kept accelerating". The officer laughs, reads out all the signs placed along the stretch of highway you drove, in order, and says you could not have been lucky enough to see only a part of them that happened to be increasing.

Estimate that likelihood. In other words, count how many subsequences of the given sequence are strictly increasing. The empty subsequence does not count, since that would mean you never looked at a single speed limit sign.

Two subsequences that pick different positions count separately even when the values match. For example, $(1, 2, 5)$ is an increasing subsequence of $(1, 4, 2, 3, 5, 5)$, and it is counted twice because there are two ways to select those values from the list.

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

The first line of each test case contains $n$, $m$, $X$, $Y$ and $Z$, separated by spaces. $n$ is the length of the sequence of speed limits and $m$ is the length of the generating array $A$. The next $m$ lines contain the $m$ 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 way the input is generated has nothing to do with the intended solution. It exists only to keep the input files small.

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 500000$

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

In the example, the second test case generates the speed limit sequence 1, 2, 0, 0, 0, 4.