Problem Description
Gug's AI is bored, so it has gone on a mental adventure. As Gug has provided a huge amount of computing power to his AI, it has generated an infinitely long array A, consisting of only positive integers, in its mind. The array A has a special property: it is periodic with period N. What this means is that Ax = Ax+N, for x ≥ 0.
Gug's AI will choose a random non-negative integer from which to start. Let this integer be s. It will then write down this number on a piece of paper. Then, it will compute the next number in the sequence s + As, and write that down. It will keep repeating this same action. 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, Gug wants to know, how many possible numbers could the AI 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 Gug's AI will write the number X on its paper at some point.
Limits
For all subtasks: 0 ≤ X ≤ 1018, 1 ≤ Ai ≤ 106.
Subtask 1 (41%): 1 ≤ N ≤ 300000, 0 ≤ X ≤ 106.
Subtask 2 (5%): N = 1.
Subtask 3 (26%): 1 ≤ N ≤ 2000.
Subtask 4 (28%): 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