증가하는 제한 속도 (큰 입력)

고속도로를 달리다가 과속으로 단속에 걸렸다. 경찰은 한참 전부터 뒤를 따라오고 있었고, 브레이크를 한 번도 밟지 않고 계속 가속했다는 사실에 놀랐다. 이제 변명이 필요하다.

그래서 "내가 본 제한 속도 표지판이 모두 오름차순이었으니 계속 가속한 것이다"라고 말하기로 했다. 경찰은 웃으면서 지나온 구간에 세워진 표지판을 순서대로 전부 알려주고, 그중 오름차순인 일부만 골라서 볼 만큼 운이 좋았을 리는 없다고 한다.

그 가능성을 계산해 보자. 다시 말해 주어진 수열의 부분 수열 중 엄격하게 증가하는 것이 몇 개인지 센다. 빈 부분 수열은 세지 않는다. 표지판을 하나도 보지 않았다는 뜻이 되기 때문이다.

값이 같아도 고른 위치가 다르면 서로 다른 부분 수열로 센다. 예를 들어 $(1, 2, 5)$는 $(1, 4, 2, 3, 5, 5)$의 증가하는 부분 수열이고, 이 값을 고르는 방법이 두 가지이므로 두 번 센다.

첫 줄에 테스트 케이스의 수 $N$이 주어진다. 이어서 $N$개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 $n$, $m$, $X$, $Y$, $Z$가 공백으로 구분되어 주어진다. $n$은 제한 속도 수열의 길이이고, $m$은 생성 배열 $A$의 길이다. 다음 $m$개 줄에 $A[0]$부터 $A[m-1]$까지 배열 $A$의 원소가 한 줄에 하나씩 주어진다.

제한 속도 수열은 $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

입력을 이렇게 생성하는 방식은 의도한 풀이와 아무 관계가 없다. 입력 파일 크기를 작게 유지하려는 목적뿐이다.

제한:

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

각 테스트 케이스마다 Case #T: S 형식으로 한 줄을 출력한다. $T$는 1부터 시작하는 테스트 케이스 번호이고, $S$는 비어 있지 않은 엄격하게 증가하는 부분 수열의 개수를 $1000000007$로 나눈 나머지다.

예제의 두 번째 테스트 케이스가 만드는 제한 속도 수열은 1, 2, 0, 0, 0, 4이다.