ROTATION

Problem

In a circle, there are ~T~ colored lights placed symmetrically at equal distances around the circumference of the circle. Each light has a different color and can be either on or off. We know exactly which lights are on and which are off.

If we rotate the circle clockwise by an angle φ = 2π/T, each light will move to the position immediately to its right. The resulting image of the colored lights will be different from the original, as we mentioned that the lights have different colors. Thus, by rotating the circle successively for angles φ that are multiples of φ = 2π/T, we can form a total of ~T~ distinct images (including the original one).

My dog Azor is colorblind. To him, all colors look the same and only the on or off states make a difference. How many distinct images of the lights does Azor see?

Input:

The first line of the input will contain two positive integers, ~N~ and ~T~, the number of lights that are on and the total number of lights, respectively. Assume that the lights are numbered from ~0~ to ~T-1~.

The second line will contain exactly ~N~ integers, ~A_1~, ~A_2~, ~...~ , ~A_N~, separated in pairs by a single space: the numbers of the lights that are turned on in the initial arrangement.

In the following examples, we arbitrarily assume that light ~0~ is positioned at the northernmost position of the circle, and the rest are numbered in increasing order according to the clockwise direction.

Output:

The output should consist of one line containing an integer: the number of different images that Azor sees if we rotate the circle as described above.

Constraints

• ~1 \le N \le T \le 10^{18}~
• ~N \le 10^6~
• Time Limit: ~2~ sec.
• Memory Limit: ~128~ MB.

Attention: The values of ~T~, and therefore the value of the result to be printed, can be larger than ~2^{32}~. Also, note that the size of the input data can be large. We recommend reading the data efficiently (see <cstdio> and scanf).

• For test cases with a total value of ~10%~, ~T \le 10^3~.
• For test cases with a total value of ~10%~, ~N \le 16.000~.
• For test cases with a total value of ~40%~, ~T \le 10^6~.
• For test cases with a total value of ~70%~, ~T \le 10^9~.

Examples of Input - Output Files:

1st

STDIN (rotation.in)

2 5
1 3

STDOUT (rotation.out)

5

Explanation of the first example

In this example, ~T = 5~ and initially only two lights are turned on. Together with the initial image, there are five images resulting from rotating the lights, for φ ~\in~ {~0~, 2π/5, 4π/5, 6π/5, 8π/5}, as shown in the diagram below. All images appear different to Azor.

2nd

STDIN (rotation.in)

2 4
1 3

STDOUT (rotation.out)

2

Explanation of the second example

In this example, ~T = 4~, and initially only two lights are turned on. Together with the initial image, there are four images resulting from the rotation of the lights, as shown below. However, for Azor, who is colorblind, the image when φ = π appears identical to the initial image. Additionally, the image when φ = 3π/2 appears identical to that when φ = π/2. Therefore, Azor sees only two different images.

3d

STDIN (rotation.in)

6 12
0 1 3 6 7 9

STDOUT (rotation.out)

6

Explanation of the third example

In this example, Azor sees six different images resulting respectively when φ ~\in~ {~0~, π/6, π/3, π/2, 2π/3, 5π/6}.