让正数带的系数尽量大。
如果要使系数最小的话，全部从左往右合并，可以让除了左端点之外全部系数为 \(2\) 。
如果增大系数可以考虑先右再左。
那么实际上就是分成若干组，组内从右往左，组外从左往右，也就是组内系数为 \(1,2,4,8,\cdots\) 。值得注意的是除了第一组外都多一个 \(2\) 的系数。
分组：先将每个数分别开一组，将总和为正的组往左合并，容易发现这得到的分组方式是唯一的。
将询问离线，增量法每次直接尽量往左合并，询问时需要二分出左端点在哪个块，空缺的块贡献用前缀和之类的方法去除。
#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fd(i,a,b) for(int i=a;i>=b;--i)
using namespace std;
typedef long long ll;
const int N=1e5+10, mod=1e9+7, inv2=5e8+4;
int n,T,a[N],cnt,q[N],siz[N],mi[N],imi[N],pre[N];
int sum[N];
ll val[N];
struct que{
int l,r,id;
}q1[N];
int ans[N];
bool cmp(que a,que b){return a.r<b.r;}
int add(int a,int b){return a+b>=mod?a+b-mod:a+b;}
int dec(int a,int b){return a>=b?a-b:a-b+mod;}
int calc(int x,int y){
if(val[y]==mod)return mod;
int len=q[y]-q[x];ll ret=val[y];
fo(i,1,len){
ret=ret*2;
if(ret+val[x]>=mod)return mod;
}
return ret+val[x];
}
int main(){
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
scanf("%d%d",&n,&T);
mi[0]=imi[0]=1;
fo(i,1,n){
scanf("%d",&a[i]);
mi[i]=(ll)mi[i-1]*2%mod;
imi[i]=(ll)imi[i-1]*inv2%mod;
int v=(a[i]<0?a[i]+mod:a[i]);
pre[i]=((ll)v*mi[i-1]%mod + pre[i-1]) % mod;
}
fo(i,1,T){
scanf("%d%d",&q1[i].l,&q1[i].r);
q1[i].id=i;
}
sort(q1+1,q1+T+1,cmp);
for(int i=1,j=1;i<=n && j<=T;++i){
q[++cnt]=i;val[cnt]=a[i];siz[cnt]=(a[i]+mod)%mod;
sum[cnt]=add(sum[cnt-1],siz[cnt]);
for(;cnt>1 && val[cnt]>0;){
--cnt;
val[cnt]=calc(cnt,cnt+1);
siz[cnt]=((ll)siz[cnt+1]*mi[q[cnt+1]-q[cnt]] % mod + siz[cnt]) % mod;
sum[cnt]=add(sum[cnt-1],siz[cnt]);
}
q[cnt+1]=i+1;
for(;j<=T && q1[j].r==i;++j){
int l=1,r=cnt+1,mid;
while(l<r-1){
mid=l+r>>1;
if(q[mid]<=q1[j].l)l=mid;
else r=mid;
}
int ret=dec(sum[cnt],sum[l-1]);
if(q1[j].l==q[l]){ans[q1[j].id]=add(ret, dec(sum[cnt],sum[l]) );continue;}
else{
int L=q1[j].l,R=q[l+1]-1;
ret=dec(ret , siz[l]);ret=(ret*2)%mod;
int ret1=(ll)dec(pre[R] , pre[L-1]) * imi[L-1] % mod;
ret=add(ret , ret1);
ans[q1[j].id]=ret;
}
}
}
fo(i,1,T)printf("%d\n",ans[i]);
return 0;
}