Xét một dãy ~b_1, b_2, \ldots, b_m~ gồm các số nguyên không âm, ta định nghĩa giá trị của dãy là tổng của tích các cặp phần tử của dãy, hay nói cách khác là tổng của ~b_i \cdot b_j~ với ~1 \le i < j \le m~.

Cho một dãy ~a_1, a_2, \ldots , a_n~, hãy tính số lượng cặp ~(l, r)~ với ~1 \le l \le r \le n~, thoả điều kiện giá trị của dãy con ~a_l, a_{l+1}, \ldots, a_r~ chia hết cho ~7~.

Dữ liệu

• Dòng đầu tiên gồm số nguyên dương ~n~ ~(1 \le n \le 10^5)~ — độ dài của dãy.

• Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ ~(0 \le a_i \le 10^9)~ — các phần tử của dãy ~a~.

Kết quả

In ra một số nguyên duy nhất là số cặp ~(l, r)~ với ~1 \le l \le r \le n~, thoả điều kiện giá trị của dãy con tương ứng chia hết cho ~7~.

Ví dụ

Sample Input 1

3
5 23 2021

Sample Output 1

3

Sample Input 2

5
0 0 1 7 7

Sample Output 2

15

Sample Input 3

10
0 1 2 3 4 5 6 7 8 9

Sample Output 3

26

Chấm điểm

• Subtask 1 (~15\%~ số test): ~n \le 300~

• Subtask 2 (~35\%~ số test): ~n \le 5000~

• Subtask 3 (~50\%~ số test): Không có ràng buộc gì thêm.