For an array of integers, let's define its weight as the sum of pairwise products of its elements, namely as the sum of over .
You are given an array of integers , and are asked to find the number of pairs of integers with , for which the weight of the subarray is divisible by .
The first line contains a single integer — the length of the array.
The second line contains integers — the elements of the array.
Output a single integer — the number of pairs of integers with , for which the weight of the corresponding subarray is divisible by .