증가하는 제한 속도

고속도로를 달리다가 과속으로 경찰에 잡혔다. 경찰은 한동안 뒤를 따라오고 있었고, 브레이크를 한 번도 밟지 않고 계속 가속만 했다는 사실에 놀랐다. 이제 그럴듯한 변명이 필요하다.

"내가 본 제한 속도 표지판은 모두 커지는 순서였다. 그래서 계속 가속했다"라고 말하기로 했다. 경찰은 웃으면서 그 구간에 세워진 표지판을 순서대로 전부 알려주고, 그중에서 커지는 순서로 놓인 것만 보게 될 만큼 운이 좋았을 리는 없다고 한다.

그 운이 어느 정도인지 가늠해 보자. 주어진 수열에서 엄격하게 증가하는 부분수열이 몇 개인지 세면 된다. 빈 부분수열은 세지 않는다. 표지판을 하나도 보지 않았다는 뜻이 되기 때문이다.

부분수열은 값이 아니라 위치로 구분한다. 예를 들어 수열 $(1, 4, 2, 3, 5, 5)$에서 값이 $(1, 2, 5)$인 엄격하게 증가하는 부분수열은 $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

입력을 이렇게 생성하는 이유는 입력 크기를 줄이는 것뿐이고, 풀이 방법과는 관계가 없다.

제한:

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

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

$n = 6$, $m = 2$, $X = 2$, $Y = 1000000000$, $Z = 6$, $A = (1, 2)$이면 의사 코드는 $1, 2, 0, 0, 0, 4$를 출력한다.