Score : 400 points
There are N boxes arranged in a row from left to right. The i-th box from the left contains A_i candies.
You will take out the candies from some consecutive boxes and distribute them evenly to M children.
Such being the case, find the number of the pairs (l, r) that satisfy the following:
Input is given from Standard Input in the following format:
N M A_1 A_2 ... A_N
Print the number of the pairs (l, r) that satisfy the conditions.
Note that the number may not fit into a 32-bit integer type.
3 2 4 1 5
3
The sum A_l + A_{l+1} + ... + A_r for each pair (l, r) is as follows:
Among these, three are multiples of 2.
13 17 29 7 5 7 9 51 7 13 8 55 42 9 81
6
10 400000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
25