Bit Array

You are given four integers: , , , . You will use them in order to create the sequence  with the following pseudo-code.

a[0] = S (modulo 2^31)
for i = 1 to N-1
    a[i] = a[i-1]*P+Q (modulo 2^31) 

Your task is to calculate the number of distinct integers in the sequence .

Input Format

Four space separated integers on a single line, , , , and  respectively.

Output Format

A single integer that denotes the number of distinct integers in the sequence .

Constraints

Sample Input

3 1 1 1

Sample Output

3

Explanation

Hence, there are  different integers in the sequence.

---

이 문제는 문제에 주어진 슈도 코드처럼 연산을 했을 때, 서로 다른 정수가 몇개나 나오는지 카운팅 하는 문제이다.

문제에 보면, the number of distinct integers 를 구하는 문제이다.

얼핏 주어진 슈도 코드대로 코드를 작성해보면

a 라는 배열을 엄청 크게 잡아놓고 0 부터 N 까지 계산을 해서 a 배열에 넣어놓고 나중에 a 배열의 값을 0 부터 끝까지 중복되지 않은 숫자만을 카운팅하는 코드를 작성할 수도 있고, a 라는 백터를 잡아놓고 계산을 한 후 unique로 추려서 size()를 구할 수도 있다.

문제는 이런식으로 하면 1차로 모두 계산을 해야 하고, 카운팅을 위한 계산을 다시 또 해줘야 한다.

당연히...HackerRank 특성상 타임아웃 100% 이다.

계산과 카운팅을 한번에 끝내야 성공할 수 있다.