بعد اليوم الأول من UJGOI، قررت ساكوركو تحليل لوحة التسجيل. تعرف كيف تكون لوحة التسجيل من المكان إلى المكان باستخدام الدالة f(l,r).
إذا كان عدد المشاركين الذين لديهم درجات فردية هو عدد فردي في الفترة (l,r)، فإن g_{odd}(l, r) يساوي مجموع العناصر الفردية هناك، وإلا فهو 0. إذا كان عدد المشاركين الذين لديهم درجات زوجية هو عدد زوجي في الفترة (l,r)، فإن g_{even}(l, r) هو مجموع العناصر الزوجية، وإلا فهو 0. f(l, r)=g_{odd}(l, r)+g_{even}(l,r).
لذا، إذا لم يتم استيفاء كلا الشرطين، فإن f(l,r)=0، وإذا تم استيفاء كلاهما، فإنه يساوي مجموع جميع العناصر في الفترة. تطلب ساكوركو منك إيجاد مجموع f(l, r) على جميع الفترات.
السطر الأول يحتوي على عدد صحيح واحد (1\le n\le 2\cdot 10^5) — عدد الأماكن في لوحة التسجيل.
السطر الثاني يحتوي على عدد صحيح a_1, a_2,\dots, a_n (1\le a_i\le 10^9) — الدرجات لكل مكان في لوحة التسجيل.
أخرج عدد صحيح واحد — مجموع قيم f(l,r) على جميع . أخرج باقي قسمة الإجابة على 10^9+7.
Example 1
في الاختبار الأول، هناك المجالات التالية (l, r):
— عدد الأعداد الفردية هو عدد فردي، عدد الأعداد الزوجية هو عدد زوجي، لذا المجموع هو 1;
— عدد الأعداد الفردية هو عدد زوجي، عدد الأعداد الزوجية هو عدد فردي، لذا المجموع هو 0;
— عدد الأعداد الفردية هو عدد فردي، عدد الأعداد الزوجية هو عدد زوجي، لذا المجموع هو 3;
— عدد الأعداد الفردية هو عدد زوجي، عدد الأعداد الزوجية هو عدد فردي، لذا المجموع هو 0;
— عدد الأعداد الفردية هو عدد فردي، عدد الأعداد الزوجية هو عدد زوجي، لذا المجموع هو 5;
— عدد الأعداد الفردية هو عدد فردي، عدد الأعداد الزوجية هو عدد فردي، لذا المجموع هو 1;
— عدد الأعداد الفردية هو عدد فردي، عدد الأعداد الزوجية هو عدد فردي، لذا المجموع هو 3;
— عدد الأعداد الفردية هو عدد فردي، عدد الأعداد الزوجية هو عدد فردي، لذا المجموع هو 3;
— عدد الأعداد الفردية هو عدد فردي، عدد الأعداد الزوجية هو عدد فردي، لذا المجموع هو 5;
[1, 2, 3] — عدد الأعداد الفردية هو عدد زوجي، عدد الأعداد الزوجية هو عدد فردي، لذا المجموع هو 0;
[2, 3, 4] — عدد الأعداد الفردية هو عدد فردي، عدد الأعداد الزوجية هو عدد زوجي، لذا المجموع هو 9;
[3, 4, 5] — عدد الأعداد الفردية هو عدد زوجي، عدد الأعداد الزوجية هو عدد فردي، لذا المجموع هو 0;
[1, 2, 3, 4] — عدد الأعداد الفردية هو عدد زوجي، عدد الأعداد الزوجية هو عدد زوجي، لذا المجموع هو 6;
[2, 3, 4, 5] — عدد الأعداد الفردية هو عدد زوجي، عدد الأعداد الزوجية هو عدد زوجي، لذا المجموع هو 6;
[1, 2, 3, 4, 5] — عدد الأعداد الفردية هو عدد فردي، عدد الأعداد الزوجية هو عدد زوجي، لذا المجموع هو 15.
لذا، فإن مجموع f(l, r) على جميع المجالات الصالحة (l, r) هو 1+0+3+0+5+1+3+3+5+0+9+6+6+15=57.
( نقاط): a_i فردي لجميع ، n\le 1000;
( نقاط): n\le 1000;
( نقاط): a_i فردي لجميع ;
( نقاط): بدون قيود إضافية.