Description
Elephants are not only cute but also love to compete in tug of war.
The rules of the game are simple:
- The team must contain at least one elephant;
- The total weight of the team must be divisible by $k$.
elfnt, the coach of the NTHU elephant team, has $n$ elephants standing in a line. the weight of the $i$-th elephant is $x_i$. to keep things fair, a team must be chosen as a contiguous segment of elephants in that line.
Your task is to help elfnt count how many different teams can be formed that satisfy the rules above.
Formally, count the number of pairs $(l, r)$ with $1 \le l \le r \le n$ such that
$$ (x_l + x_{l+1} + \dots + x_r) \equiv 0 \pmod{k} $$
Input
The first line contains an integers $n$.
The second line contains an integers $k$.
The third line contains $n$ integers $x_1, x_2, \dots, x_n$, where $x_i$ is the weight of the $i$-th elephant.
Constraints
- $1 \le n \le 10^6$
- $1 \le x_i \le 10^9$
- $1 \le k \le 10^9$
Subtask
- (Testcases 1-2) $1 \leq k \leq n \leq 100$
- (Testcases 3-5) $1 \leq k \leq n \leq 1000$
- (Testcases 6-7) $1 \leq k \leq n$
- (Testcase 8) No additional constraints.
Output
Print the answer followed by a newline.
Hint
In the sample test case
Valid teams include:
- $(1,3)$: $1+1+4=6 \equiv 0\ \pmod{3}$
- $(1,5)$: $1+1+4+5+1=12 \equiv 0\ \pmod{3}$
- $(2,6)$: $1+4+5+1+4=15 \equiv 0\ \pmod{3}$
- $(3,4)$: $4+5=9 \equiv 0\ \pmod{3}$
- $(4,5)$: $5+1=6 \equiv 0\ \pmod{3}$
Thus, there are $5$ possible teams.