Après le premier jour de l'UJGOI, Sakurako a décidé d'analyser le tableau des scores. Elle définit la qualité du tableau des scores de la place à la place en utilisant la fonction f(l,r).
Si le nombre de participants ayant des scores impairs est impair dans l'intervalle (l,r), alors g_{odd}(l, r) est égal à la somme des éléments impairs dans cet intervalle, sinon c'est 0. Si le nombre de participants ayant des scores pairs est pair dans l'intervalle (l,r), alors g_{even}(l, r) est la somme des éléments pairs, sinon c'est 0. f(l, r)=g_{odd}(l, r)+g_{even}(l,r).
Ainsi, si aucune des deux conditions n'est satisfaite, alors f(l,r)=0, et si les deux sont satisfaites, alors cela équivaut à la somme de tous les éléments de l'intervalle. Sakurako vous demande de trouver la somme de f(l, r) sur tous les intervalles.
La première ligne contient un entier (1\le n\le 2\cdot 10^5) — le nombre de places dans le tableau des scores.
La deuxième ligne contient entiers a_1, a_2,\dots, a_n (1\le a_i\le 10^9) — les scores de chaque place dans le tableau des scores.
Affichez un entier — la somme des valeurs de f(l,r) sur tous les . Affichez la réponse modulo 10^9+7.
Example 1
Dans le premier test, il y a les intervalles suivants (l, r) :
— le nombre de nombres impairs est impair, le nombre de nombres pairs est pair, donc la somme est 1;
— le nombre de nombres impairs est pair, le nombre de nombres pairs est impair, donc la somme est 0;
— le nombre de nombres impairs est impair, le nombre de nombres pairs est pair, donc la somme est 3;
— le nombre de nombres impairs est pair, le nombre de nombres pairs est impair, donc la somme est 0;
— le nombre de nombres impairs est impair, le nombre de nombres pairs est pair, donc la somme est 5;
— le nombre de nombres impairs est impair, le nombre de nombres pairs est impair, donc la somme est 1;
— le nombre de nombres impairs est impair, le nombre de nombres pairs est impair, donc la somme est 3;
— le nombre de nombres impairs est impair, le nombre de nombres pairs est impair, donc la somme est 3;
— le nombre de nombres impairs est impair, le nombre de nombres pairs est impair, donc la somme est 5;
[1, 2, 3] — le nombre de nombres impairs est pair, le nombre de nombres pairs est impair, donc la somme est 0;
[2, 3, 4] — le nombre de nombres impairs est impair, le nombre de nombres pairs est pair, donc la somme est 9;
[3, 4, 5] — le nombre de nombres impairs est pair, le nombre de nombres pairs est impair, donc la somme est 0;
[1, 2, 3, 4] — le nombre de nombres impairs est pair, le nombre de nombres pairs est pair, donc la somme est 6;
[2, 3, 4, 5] — le nombre de nombres impairs est pair, le nombre de nombres pairs est pair, donc la somme est 6;
[1, 2, 3, 4, 5] — le nombre de nombres impairs est impair, le nombre de nombres pairs est pair, donc la somme est 15.
Ainsi, la somme de f(l, r) sur tous les intervalles valides (l, r) est 1+0+3+0+5+1+3+3+5+0+9+6+6+15=57.
( points): a_i est impair pour tous les , n\le 1000;
( points): n\le 1000;
( points): a_i est impair pour tous les ;
( points): sans contraintes supplémentaires.