Problem I
Veggur

Nú er fjórtánda öldin og byggja á kastalann á Trakaieyju á næstunni. Fyrsta verkefnið á dagskrá arkitektsins er að hanna aðalvegg kastalans.

Að byggja vegg sem getur varið kastala frá hvaða árás sem er getur reynst erfitt. Til að tryggja öryggi varðanna hefur arkitektinn takmarkað hönnunina þónokkuð.

Þar sem árásir frá miðju vatninu eru ólíklegri en nálægu strandlínunni er óþarfi að byggja hringlaga vegg. Í staðinn er veggurinn bein lína og mun samanstanda af $N$ hlutum sem eru í röð frá öðrum endanum að hinum og eru númeraðir frá $1$ upp í $N$. Það sem á eftir að gera er að velja hæðina á hverjum hluta veggsins.

Arkitektinn hefur valið tvær mögulegar hæðir fyrir hvern hluta. Hann hefur ákveðið að hæð hluta númer $i$ skal vera annað hvort $a_ i$ eða $b_ i$. Því eru $2^ N$ möguleikar í boði.

Það fylgja vandamál með því að staðsetja kastalann á lítilli eyju. Þegar óveður skellur á getur flætt vatn um kastalann. Þá safnast vatn fyrir ofan hlutana ef að það eru hærri hlutar sitt hvorum megin við þá, sem kemur í veg fyrir að vatnið leki niður.

Fyrir sérstakt val af hæðum höfum við áhuga á magni vatns sem safnast á veggnum í óveðri. Þetta má sjá í eftirfarandi mynd, þar sem hæðir hlutanna frá vinstri til hægri eru $4, 2, 1, 8, 6, 2, 7, 1, 2, 3$ og hæð vatnsins í hverjum hluta er $4, 4, 4, 8, 7, 7, 7, 3, 3, 3$.

Formlega má segja að fyrir sérhvert $i = 1, 2, \dotsc , N$ er hæð vatnsins á staðsetningu $i$ að minnsta kosti $h$ þá og því aðeins ef það eru til heiltölur $l$ og $r$ þannig að $l \leq i$ og $i \leq r$ og hæðirnar á staðsetningum $l$ og $r$ eru að minnsta kosti $h$. Þá sérstaklega er hæð vatnsins á staðsetningum $1$ og $N$ er alltaf jöfn hæðum samsvarandi hluta og hæðin á vatninu á hinum staðsetningunum er alltaf að minnsta kosti hæðin á samsvarandi hluta. Magn vatnsins sem hefur safnast fyrir á staðsetningu $i$ er jöfn mismunarins á hæð vatnsins og hæð hlutans. Samtals magn vatns sem safnast fyrir er summan af magn vatns á staðsetningum $1, 2, \dotsc , N$.

Verkefni

Verkefnið þitt er að reikna summuna af magni vatns sem safnast fyrir alla $2^ N$ mögulega veggi. Þú skalt skrifa svarið mátað við $10^9 + 7$. Í öðrum orðum skaltu skrifa út afganginn af summunni deilt með $10^9 + 7$.

Inntak

Fyrsta lína inntaksins inniheldur eina heiltölu $N$.

Önnur lína inntaksins inniheldur $N$ heiltölur $a_1, a_2, \dotsc , a_ N$.

Þriðja lína inntaksins inniheldur $N$ heiltölur $b_1, b_2, \dotsc , b_ N$.

Úttak

Forritið þitt skal skrifa út eina heiltölu, summuna af magni vatns sem safnast yfir alla mögulega veggi mátaða við $10^9 + 7$.

Takmarkanir

• $1 \leq N \leq 5 \cdot 10^5$.

• $1 \leq a_ i, b_ i \leq 10^9$ og $a_ i \neq b_ i$ (fyrir öll $1 \leq i \leq N$)

Hlutverkefni

Sýnidæmi

Það er einn mögulegur veggur þar sem tvær einingar af vatni safnast fyrir:

• $2 \, 1 \, 1 \, 2$

og fjórir mögulegir veggir þar sem ein eining af vatni safnast fyrir:

• $1 \, 2 \, 1 \, 2$,

• $2 \, 1 \, 2 \, 1$,

• $2 \, 1 \, 2 \, 2$,

• $2 \, 2 \, 1 \, 2$.

4
1 1 1 1
2 2 2 2

6

10
1 2 3 4 5 6 7 8 9 10
10 9 8 7 6 5 4 3 2 1

21116