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.


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.


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.


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

Sample Output 1


Sample Input 2

3 10
1 4 2

Sample Output 2