Anna Nikolaevna has
N boxes of sweets. The
i-th box contains
Ai the number of sweets. Anna Nikolaevna takes sweets from several consecutive boxes and evenly distributes them < code>M children. Find the number of pairs (
l,
r) that satisfy the following conditions:
-
l and
r are integers and satisfy the condition
1<=l<=r<=N;
-
Al + Al+1 +< /code> ... + Ar is divisible by M.
Input
The program receives two lines as input. The first line contains two integers N (1<=N<=105) and M (2<=M<=109). The second line contains N numbers Ai (1<=Ai<=109< /sup>, 1<=i<=N).
Imprint
Print the number of pairs (l, r) that satisfy the conditions. Note that the number may not correspond to a 32-bit integer type.
Examples
| # |
Input |
Output |
| 1 |
3 2
4 1 5
| 3 |
| 2 |
13 17
29 7 5 7 9 51 7 13 8 55 42 9 81
| 6 |