R. Deque 2 (Hard Version)
time limit per test
2.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

The only difference between the easy version and the hard version is the constraint on $$$n$$$.

Gunga just learned what a double-ended queue is in his data structure class. a double-ended queue (deque) is an abstract data type that generalizes a queue, for which elements can be added to or removed from either the front (head) or back (tail).

Now, he is playing with his own double-ended queue. He has an empty double-ended queue $$$B$$$ and an array of integers $$$A$$$. In the $$$i$$$-th move, he will add $$$A_i$$$ to one end of $$$B$$$. This time, he wants to find the total sum of the sum of values $$$B_L$$$ to $$$B_R$$$ over all the $$$2^n$$$ possible $$$B$$$ formed. Since the answer can be large, output the answer $$$\pmod{10^9+7}$$$. Two queues are considered different if Gunga's operation on some $$$A_i$$$ is different.

Input

The first line contains an integer $$$n,L,R$$$ $$$(1 \leq n \leq 5 \times 10^5,1\le L\le R\le n)$$$ – the number of integers and Gunga's favorite interval.

The second line contains $$$n$$$ space-separated integers $$$A_1, A_2, \ldots, A_n$$$ $$$(-10^9 \leq A_i \leq 10^9)$$$.

Output

A single integer, the answer $$$\pmod{10^9+7}$$$.

Examples
Input
5 1 5
1 1 1 1 1
Output
160
Input
3 1 2
1 2 3
Output
30
Note

In the first example, no matter which end of the queue Gunga adds the number to, the resulting queue will be $$$[1,1,1,1,1]$$$. The total sum is $$$32\times(1+1+1+1+1)=160$$$.

In the second example, there are $$$8$$$ possible queues $$$B$$$: $$$[1,2,3],[1,2,3],[2,1,3],[2,1,3],[3,2,1],[3,2,1],[3,1,2],[3,1,2]$$$.

The total sum of the sum of $$$B_1$$$ to $$$B_2$$$ is $$$2\times (1+2+2+1+3+2+3+1)=30$$$.