문제
무작위 숫자 생성기(random number generator)는 여러 방면에서 상당히 중요한 역할을 한다.
다음과 같은 방법의 무작위 숫자 생성기가 있다고 하자, 만들어진 숫자의 길이가 최대 D자리가 되게 하고자 한다. 우선 10^D 보다 임의의 작은 소수(prime number) P를 선택하고 임의의 자연수 A와 B를 선택한다. 그 다음에 0 이상 P-1 이하의 임의의 정수 S를 선택한다. 무작위 숫자 생성기에서 처음 생성되는 숫자는 S이다. 그 다음에 다음 숫자 S'를 생성할 때 부터는 다음의 수식을 이용한다.
S' := (A*S + B) mod P.
위에서 mod는 P로 나눈 나머지를 뜻하며, 위의 수식을 통해서 구한 S'은 다음에 생성되는 숫자가 된다. 그런 다음 S를 S'로 대치하고, 위의 수식을 반복하여 다음에 발생할 숫자를 구하게 된다.
예를 들어 D = 2 이고, P = 3 이며, A = 1, B = 1, S = 0 일 경우 생성되는 무작위 숫자들은 다음과 같다.
0 1( (1*0+1) mod 3 ) 2( (1*1+1) mod 3 ) 0( (1*2+1) mod 3 ) 1( (1*0+1) mod 3 ) ...
P, 그리고 A와 B, 그리고 S를 알지 못하는 상태에서 위의 방법으로 생성된 연속된 구간의 K개의 숫자가 주어졌을 때 다음에 생성되는 숫자가 무엇인지 알아내는 프로그램을 작성하라. 단, 발생하는 무작위 숫자의 범위에 대한 D는 주어진다.
제출파일의 이름은 2274.cpp로하고 실행시간은 5초를 넘을 수 없다.
입력
입력파일은 INPUT.TXT로 한다. 첫번째 줄에는 D(1<=D<=4)와 K(1<=K<=10)이 입력된다. 두번째 줄에는 위에 설명된 무작위 숫자 생성기를 통해 생성한 K개의 연속된 숫자들이 입력된다.
출력
출력파일은 OUTPUT.TXT로 한다. 입력에 대해 바로 다음에 생성될 숫자를 출력한다. 만약 생성될 수 있는 숫자가 여럿이거나 존재하지 못할 경우 "I don't know."를 출력한다.
예제 #1
2 10
0 1 2 3 4 5 6 7 8 9
10
예제 #2
3 1
13
I don't know.
예제 #3
1 5
6 6 6 6 6
6
로그인해야 코드를 작성할 수 있어요.