#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

## 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 A_{x} = A_{x+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 + A _{s}*, 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 + A*.

_{s}
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, *A _{0}* to

*A*.

_{N-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 ≤ 10^{18}, 1 ≤ A_{i} ≤ 10^{6}.

Subtask 1 (41%): 1 ≤ N ≤ 300000, 0 ≤ X ≤ 10^{6}.

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

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 41 | 22 | 1s | 256MB | Minimum |

2 | 5 | 21 | 1s | 256MB | Minimum |

3 | 26 | 52 | 1s | 256MB | Minimum |

4 | 28 | 82 | 1s | 256MB | Minimum |

5 | 0 | 2 | 1s | 256MB | Minimum |

### Judge Compile Command

g++-7 ans.cpp -o periodicity -Wall -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512