Mimi is helping out at a daycare! There are children and boxes of crayons in a row, the of which has crayons. Mimi will choose a single contiguous section of crayon boxes to give to the children. In order to be fair, she also wants the total number of crayons in the subarray she chooses to be divisible by so that it can be split equally. How many ways can she do this?
For all subtasks, .
Subtask 1 [20%]
Subtask 2 [20%]
Subtask 3 [40%]
Subtask 4 [20%]
The first line will have two space separated integers, and .
The second line will have space separated integers, .
A single integer, the number of subarrays which have a total which is a multiple of . This number may overflow 32-bit numbers.
5 6 3 5 9 6 10
Explanation for Sample
The two subarrays with a sum divisible by 6 are and .