#include <iostream>#include <cstring>#include <stdio.h>using namespace std;const int MAX_N = 100000 + 100;const int MOD = 1000000007;struct Matrix{ long long m[2][2]; Matrix(){memset(m, 0, sizeof(m));} Matrix operator * (const Matrix &b) { Matrix temp; for(int i = 0; i < 2; i++) for(int j = 0; j < 2; j++) for(int k = 0; k < 2; k++) temp.m[i][j] = ((m[i][k] * b.m[k][j]) + temp.m[i][j]) % MOD; return temp; }};struct Node{ int l, r; Matrix mat;};Node node[MAX_N << 2];int a[MAX_N];void Build(int rt, int l, int r){ int m; node[rt].l = l; node[rt].r = r; if(l == r) { node[rt].mat.m[0][0] = 1; node[rt].mat.m[0][1] = a[l]; node[rt].mat.m[1][0] = 1; node[rt].mat.m[1][1] = 0; } else { m = (l + r) >> 1; Build(rt << 1, l, m); Build(rt << 1 | 1, m + 1, r); node[rt].mat = node[rt << 1 | 1].mat * node[rt << 1].mat; }}Matrix Query(int rt, int ql, int qr){ int m; if(ql == node[rt].l && node[rt].r == qr) return node[rt].mat; else { m = (node[rt].l + node[rt].r) >> 1; if(qr <= m) return Query(rt << 1, ql, qr); else if(ql > m) return Query(rt << 1 | 1, ql, qr); else return Query(rt << 1 | 1, m + 1, qr) * Query(rt << 1, ql, m); }}int T, n, m, ql, qr;int main(){ scanf("%d", &T); while(T--) { Matrix res, f; scanf("%d%d",&n, &m); for(int i = 1; i <= n; i++) scanf("%d", &a[i]); Build(1, 1, n); for(int i = 1; i<= m; i++) { scanf("%d%d", &ql, &qr); if(qr - ql >= 2) { f.m[0][0] = a[ql + 1]; f.m[1][0] = a[ql]; res = Query(1, ql + 2, qr) * f; printf("%dn", res.m[0][0]); } else printf("%dn", a[qr]); } } return 0;}
