운 조작

Nathan O. Davis 군은 어떤 게임을 공략 중이며, 매우 희귀한 아이템을 얻기 위해 애를 쓰고 있었다. 이 희귀한 아이템은 카지노의 슬롯 머신에서 특수한 그림을 한 줄로 맞췄을 때 얻을 수 있다. 슬롯 머신에는 N개의 릴이 있고, 버튼을 한 번 누르면 현재 회전 중인 가장 왼쪽 릴이 멈춘다. 따라서 이 희귀 아이템을 얻으려면 버튼을 N번 눌러야 한다. 또한 특수한 그림에서 멈추게 하려면 특정 타이밍에 버튼을 눌러야 한다. 그런데 이 버튼을 누르는 타이밍이 매우 까다로워서 좀처럼 잘 되지 않아 골머리를 앓고 있었다. 그래서 Nathan 군은 메모리 뷰어를 이용해 게임 중 메모리 값을 확인하면서 게임을 분석하기로 했다.

Nathan 군의 분석 결과, 그 특수한 그림으로 릴을 멈추게 하려면 버튼이 눌렸을 때 메모리의 007E0D1F 번지에 쓰인 '난수'가 특정한 값이 되어 있어야 한다는 것을 알아냈다. 난수 값은 1프레임마다 선형 합동법에 따라 변화하며, 버튼이 눌렸는지 판정도 1프레임마다 1회 이루어진다는 것도 알았다. 여기서 선형 합동법은 의사 난수를 생성하는 방법 중 하나이며, 다음 식으로 값을 정한다.

x' = (A × x + B) mod C

여기서 x는 현재 난수 값, x'는 다음 난수 값, A, B, C는 어떤 상수다. 또한 y mod z는 y를 z로 나눈 나머지를 나타낸다.

예를 들어 릴이 2개인 슬롯 머신에서 A = 5, B = 7, C = 11이고 처음 '난수' 값이 10이라고 하자. 그리고 특수한 그림으로 릴을 멈추기 위한 조건이 왼쪽 릴이 2, 오른쪽 릴이 4라고 하자. 이때 1프레임에서 난수 값은 (5 × 10 + 7) mod 11 = 2이므로, 1프레임에 버튼을 누르면 왼쪽 릴은 특수한 그림에서 멈춘다. 이어지는 2프레임에서 난수 값은 (5 × 2 + 7) mod 11 = 6이므로, 2프레임에 버튼을 눌러도 오른쪽 릴은 특수한 그림에서 멈추지 않는다. 이어지는 3프레임에서는 난수 값이 (5 × 6 + 7) mod 11 = 4가 되므로, 3프레임에 버튼을 누르면 오른쪽 릴은 특수한 그림에서 멈춘다. 따라서 최단 3프레임에 모든 릴을 특수한 그림에서 멈추게 할 수 있고, 희귀한 아이템을 얻을 수 있다.

여러분의 일은 최단 몇 프레임째에 모든 릴을 특수한 그림에서 멈추게 할 수 있는지 구하는 프로그램을 작성해 Nathan 군이 희귀한 아이템을 얻을 수 있도록 도와주는 것이다.

입력은 여러 데이터 세트로 이루어진다. 각 데이터 세트는 다음 형식으로 주어진다.

N A B C X
Y1 Y2 ... YN

첫째 줄에는 5개의 정수 N (1 ≤ N ≤ 100), A, B (0 ≤ A, B ≤ 10,000), C (1 ≤ C ≤ 10,000), X (0 ≤ X < C)가 각각 공백 하나로 구분되어 주어진다. 여기서 X는 처음 난수 값을 나타낸다. 다음 줄에는 N개의 정수 Y1, Y2, ..., Y**N (0 ≤ Y**i ≤ 10,000)이 공백 하나로 구분되어 주어진다. 이들은 릴을 특정 그림에서 멈추기 위한 조건을 나타내며, i번째 수 Y**i는 왼쪽에서 i번째 릴을 특수한 그림에서 멈추려면 난수 값이 Y**i여야 한다는 뜻이다.

입력의 끝은 공백으로 구분된 5개의 0을 포함한 한 줄로 나타낸다.

각 데이터 세트마다 특수한 그림에서 멈추게 하는 데 필요한 최단 프레임 수를 한 줄에 출력하라. 10,000프레임 이내에 멈추게 할 수 없는 경우에는 프레임 수 대신 -1을 출력하라. 출력에 불필요한 공백이나 줄바꿈을 포함해서는 안 된다.