증가하는 제한 속도

고속도로를 따라 운전하던 중 과속으로 교통경찰에게 붙잡혔다. 알고 보니 경찰은 계속 당신을 따라오고 있었으며, 당신이 브레이크를 사용하지 않고 내내 가속했다는 사실에 놀랐다! 이제 이를 설명할 변명이 절실히 필요하다.

당신은 "내가 본 모든 제한 속도 표지판이 증가하는 순서였기 때문에 가속했다"라고 말하는 것이 그럴듯하겠다고 생각했다. 경찰관은 그 말을 듣고 웃으며, 당신이 주행한 고속도로 구간에 설치된 모든 표지판을 알려 주고, 그 표지판들 가운데 증가하는 순서로 된 일부만 볼 정도로 운이 좋았을 가능성은 낮다고 말한다.

이제 그 가능성을 추정해야 한다. 다시 말해, 주어진 수열에서 엄격히 증가하는 서로 다른 부분 수열이 몇 개인지 알아내야 한다. 빈 부분 수열은 제한 속도 표지판을 전혀 보지 않았다는 뜻이므로 세지 않는다!

예를 들어, (1, 2, 5)는 (1, 4, 2, 3, 5, 5)의 증가하는 부분 수열이며, 목록에서 (1, 2, 5)를 선택하는 방법이 두 가지이므로 이를 두 번 센다.

제한

시간 제한: 테스트 세트당 60초. 메모리 제한: 1GB. 1 ≤ N ≤ 20 1 ≤ m ≤ 100 0 ≤ X ≤ $10^{9}$ 0 ≤ Y ≤ $10^{9}$ 1 ≤ Z ≤ $10^{9}$ 0 ≤ A[i] < Z

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ m ≤ n ≤ 1000

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ m ≤ n ≤ 500000

입력의 첫째 줄에 케이스의 수 N이 주어진다. 이어서 N개의 테스트 케이스가 주어진다. 각 케이스의 첫째 줄에는 각각 공백으로 구분된 n, m, X, Y, Z가 주어진다. n은 제한 속도 수열의 길이이다. m은 생성 배열 A의 길이이다. 다음 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는 비어 있지 않은 증가하는 부분 수열의 수를 1000000007로 나눈 나머지이다.

케이스 2의 제한 속도 표지판 수열은 1, 2, 0, 0, 0, 4이어야 한다.