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, A_x = A_x+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+A_s 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 + A_s.

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, A₀ to A_N-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 ≤ 10¹⁸, 1 ≤ A_i ≤ 10⁶.

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

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