Divisible by 3#12839

Divisible by 3

2 seconds
256 megabytes
Hard

For an array [b_1, b_2, \ldots, b_m] of integers, let's define its weight as the sum of pairwise products of its elements, namely as the sum of b_ib_j over 1 \le i < j \le m.

You are given an array of integers [a_1, a_2, \ldots, a_n], and are asked to find the number of pairs of integers (l, r) with 1 \le l \le r \le n, for which the weight of the subarray [a_l, a_{l+1}, \ldots , a_r] is divisible by .

Input

The first line of the input contains a single integer (1 \le n \le 5\cdot 10^5) — the length of the array.

The second line contains integers a_1, a_2, \ldots, a_n (0\le a_i \le 10^9) — the elements of the array.

Output

Output a single integer — the number of pairs of integers (l, r) with 1 \le l \le r \le n, for which the weight of the corresponding subarray is divisible by .

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Example 3

Loading
Loading

Note

In the first sample, the weights of exactly subarrays are divisible by :

  • \text{weight}([5]) = \text{weight}([23]) = \text{weight}([2021]) = 0

  • \text{weight}([5, 23, 2021]) = 56703 = 3 \cdot 41 \cdot 461