Cho một dãy số nguyên không âm ~a_1, a_2, ..., a_n~. Một cặp số ~(i, j)~ được gọi là cặp đôi "tam giác căn" khi và chỉ khi ~(\sqrt{i}, \sqrt{j}, \sqrt{i + j})~ là bộ ba cạnh của một tam giác. Nhiệm vụ của bạn là đếm số cặp vị trí ~1 \le u \le v \le n~ mà ~(a_u, a_v)~ là một cặp đôi "tam giác căn".

Dữ liệu vào

• Dòng đầu tiên gồm một số nguyên dương ~n~ ~(1 \le n \le 10^5)~.
• Dòng tiếp theo gồm ~n~ số nguyên không âm ~a_1, a_2, ..., a_n~ ~(0 \le a_i \le 10^{18})~.

Dữ liệu ra

• Một dòng duy nhất là phần dư của kết quả bài toán sau khi chia cho ~10^9 + 7~.

Ví dụ

Ví dụ 1

Dữ liệu vào

2
1 2

Dữ liệu ra

3

Giải thích

• Hình trên là ví dụ về các tam giác có các bộ số cạnh ~(1, 1, \sqrt{2}), (1, \sqrt{2}, \sqrt{3})~ và ~(\sqrt{2}, \sqrt{2}, 2)~.