Cho một mảng ~a~ gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~. Gọi trọng số của mảng là tổng của các (~a_i + a_j~) ~(1 \le i \le j \le n~) thỏa mãn ~a_i + a_j~ lẻ. Bạn hãy tìm trọng số của mảng ~a~.

Vì trọng số có thể rất lớn, hãy in ra kết quả ~\mod 10^9+7~.

Input

Dòng đầu tiên gồm số nguyên dương ~n~ (~1 \le n \le 10^6~).

Dòng thứ hai gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ (~1 \le a_i \le 10^9~).

Output

Gồm một dòng duy nhất là trọng số của mảng ~a~ ~\mod 10^9+7~.

Scoring

Sample Input 1

5
3 7 2 1 9

Sample Output 1

28

Sample Input 2

5
6 8 2 2 10

Sample Output 2

0

Notes

Trong test ví dụ đầu tiên, các cặp số thỏa mãn là (~1, 3~), (~2, 3~), (~3, 4~), (~3, 5~). Vậy trọng số là ~(a_1 + a_3) + (a_2 + a_3) + (a_3 + a_4) + (a_3 + a_5)~ = ~3 + 2 + 7 + 2 + 2 + 1 + 2 + 9 = 28~.

Trong test ví dụ thứ hai, không có bất kì cặp nào có tổng là số lẻ nên trọng số của mảng ~[6, 8, 2, 2, 10]~ là ~0~.