Given a sequence of
N natural numbers. All its continuous subsequences starting from the first element of the sequence are considered. Find the number of subsequences whose sum is a multiple of
K.
Input
The first line contains two numbers: the number of numbers in the sequence
N (1 <= N <= 10
8) and the number
K ( 1 <= K <= 100). Next comes
N lines, one natural number per line. Each number does not exceed
10000.
Imprint
Display the answer to the problem
Examples
| # |
Input |
Output |
| 1 |
5 3
33
41
19
22
40 |
2 |