난수 생성기 역추적 (Large)

온라인 포커 사이트를 만들려고 한다. 이런 시스템에서 난수 생성기는 중요한 부품이고, 빠르면서 충분히 무작위여야 한다. 내가 생각한 절충안은 다음과 같다.

자릿수가 $D$ 이하인 난수를 만들고 싶다. 먼저 $10^D$ 이하인 소수 $P$를 고른다. 음이 아닌 정수 $A$와 $B$도 고른다. 마지막으로 $0$ 이상 $P-1$ 이하인 정수 씨앗값 $S$를 고른다.

수열은 이렇게 만든다. 먼저 $S$를 출력하고, 다음 식으로 $S$를 갱신한다.

$S := (A \times S + B) \bmod P$

갱신한 $S$를 수열의 다음 항으로 출력하고, 같은 식으로 $S$를 또 갱신한다. 이 과정을 원하는 만큼 반복한다.

이 난수 생성기가 좋다고 생각하는가? 이 방식으로 만든 수열에서 연속한 $K$개의 항을 읽어 그다음 항을 출력하는 프로그램을 작성하라.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 각 테스트 케이스가 두 줄씩 주어진다. 첫 줄에는 $D$와 $K$가 주어지고, 둘째 줄에는 위에서 설명한 난수 생성기가 만든 수열의 연속한 항 $K$개가 주어진다.

제한

• $1 \le T \le 100$
• $1 \le D \le 6$
• $1 \le K \le 10$
• 주어진 $K$개의 정수는 위 방식의 난수 생성기가 만든 수열의 연속한 항이다. 즉 이 $K$개의 항을 그대로 만들어 내는 $(P, A, B)$가 적어도 한 가지 있다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 테스트 케이스 번호이고 1부터 시작한다.

$10^D$ 이하인 소수 $P$와 음이 아닌 정수 $A$, $B$의 조합 중에서 주어진 $K$개의 항을 그대로 만들어 내는 것을 모두 생각한다. 이 조합들이 모두 같은 다음 항을 주면 그 값을 $y$ 자리에 출력한다. 다음 항이 서로 다르게 나오는 조합이 있으면 $y$ 자리에 I don't know.를 마침표까지 그대로 출력한다.