Problem Statement

You are given $N$ positive integers $A_1,A_2,...,A_N$ and a positive integer $M$.

Let $S$ be the set whose elements are $A_1,A_2...,A_N$.

Among the sets that are subsets of $S$ and satisfy the following condition, find the number of elements of a set with the maximum number of elements.

Condition

Take 2 distinct numbers from the elements of the set, and call them $P, Q$ respectively.

Then, no matter how the numbers are taken, $P+Q$ is never a multiple of $M$.

(If the set has $1$ element, it is considered to always satisfy this condition.)

Constraints

• $\displaystyle 1 \leq N \leq 10^5$
• $\displaystyle 1 \leq M \leq 10^{12}$
• $\displaystyle 1 \leq A_i \leq 10^{12} \ (1 \leq i \leq N)$
• $\displaystyle A_i \neq A_j \ (1 \leq i,j \leq N, \ i \neq j)$
• All inputs are integers.

Input

The input is given from standard input in the following format.

$N \ \ M$
$A_1 \ \ A_2 \ \dots \ A_N$

Output

Output the value you found, followed by a newline.

Sample

4 5
7 14 3 5

3

1 8
3

1

14 5
218 64 142 792 323 402 594 857 394 977 577 495 264 29

12