Infinite Looping Sequence

Problem Description

Orange likes infinte loops. He has an infinitely long array A of positive integers. However, as he only has 2 brain cells, the array is periodic with period N. In other words, Ax = Ax+N, for x ≥ 0.

Orange will choose a random non-negative integer to start. Let the number be s. He will then write down this number and compute the next number s+As and write that down. He will keep repeating that, i.e. if the last number that was written down was s, the next number written down would be s + As.

Given a number X, Orange wants to know, how many possible numbers could he have started with such that it, at some point, writes X on its piece of paper.

Input

The first line of input will contain two integers, N and X.

The second line of input will contain N integers, A0 to AN-1.

Output

The output should contain one line with one integer, the number of possible starting numbers such that Orange will write the number X on its paper at some point.

Limits

For all subtasks: 0 ≤ X ≤ 1018, 1 ≤ Ai ≤ 106.

Subtask 1 (37%): 1 ≤ N ≤ 300000, 0 ≤ X ≤ 106.

Subtask 2 (10%): N = 1.

Subtask 3 (24%): 1 ≤ N ≤ 2000.

Subtask 4 (29%): 1 ≤ N ≤ 300000.

Subtask 5 (0%): Sample Testcases.

Sample Input 1

1 4
2

Sample Output 1

3

Sample Input 2

3 10
1 4 2

Sample Output 2

6

Submitting to 'Infinite Looping Sequence'


You're not logged in! Click here to login


Submitting .cpp to 'Infinite Looping Sequence'


You're not logged in! Click here to login


Compile Errors


							
Time Limit: 1 Seconds
Memory Limit: 256MB
No. of ACs: 19
Your best score: 0
Source: 2017 RI Dec Course Sel (pwypeanut)

Subtask Score
1 37
2 10
3 24
4 29
5 0