UJGOI Տեղեկատու#410

UJGOI Տեղեկատու

1 վայրկյան
256 մեգաբայթ
Hard

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) գումարը բոլոր միջակայքներում:

Input

Առաջին տողը պարունակում է մեկ ամբողջ թիվ (1\le n\le 2\cdot 10^5) — մրցաշարային աղյուսակի երկարությունը:

Երկրորդ տողը պարունակում է ամբողջ թիվ a_1, a_2,\dots, a_n (1\le a_i\le 10^9) — մրցաշարային աղյուսակի յուրաքանչյուր տեղում միավորները:

Output

Արտածեք մեկ ամբողջ թիվ — f(l,r) արժեքների գումարը բոլոր համար: Արտածեք պատասխանը 10^9+7 մոդուլով:

Examples

Example 1

Loading
Loading

Note

Առաջին թեստում կան հետևյալ միջակայքները (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:

Scoring

  • ( միավոր): a_i բոլոր համար կենտ է, n\le 1000;

  • ( միավոր): n\le 1000;

  • ( միավոր): a_i բոլոր համար կենտ է;

  • ( միավոր): առանց լրացուցիչ սահմանափակումների.