先通过前(n+1)项，插值求出f(n+1)，然后通过这(n+2)项来插值求出f(x)的前缀和函数S(x)，答案为S(r)-S(l-1)。

// Author: Feng
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define pii pair<int,int>
#define pll pair<ll, ll>
#define pli pair<ll, int>
#define pb push_back
#define X first
#define Y second
inline ll gcd(ll a, ll b) { while (b != 0) { ll c = a % b; a = b; b = c; }return a < 0 ? -a : a; }
inline ll lowbit(ll x) { return x & (-x); }
int head[1000010], Edge_Num;
struct Edge { int to, next; ll w; }e[2000010];
inline void ade(int x, int y, ll w) { e[++Edge_Num] = { y,head[x],w }; head[x] = Edge_Num; }
inline void G_init(int n) { memset(head, 0, sizeof(int) * (n + 100)); Edge_Num = 0; }
int dir[8][2] = { {-1,0},{0,-1},{1,0},{0,1},{-1,-1},{-1,1},{1,-1},{1,1} };
const long double PI = 3.14159265358979323846;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
inline ll rd() {
    ll x = 0; bool f = 1; char ch = getchar();
    while (ch<'0' || ch>'9') { if (ch == '-')f = 0; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); }
    return f ? x : -x;
}
const double eps = 1e-8;
const ll mod = 9999991;
const int M = 5e6 + 10;
const int N = 1e3 + 10;
ll inv[mod + 10], fac[N];
ll fac_inv[N];
void get_inv(int n) {
    inv[0] = inv[1] = 1;
    for (ll i = 2; i <= n; i++) {
        inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    }
}
int n;
ll f[N];
inline ll qpow(ll x, ll n) {
    ll res = 1;
    while (n) {
        if (n & 1)res = res * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return res;
}
ll cal(int x, int n) {//拉格朗日插值法
    if (x <= n)return f[x];
    ll res = 0;
    ll p = 1;
    for (int i = 0; i <= n; i++) {
        p = p * (1ll * x - i) % mod;
    }
    for (int i = 0; i <= n; i++) {
        ll temp = f[i] * p % mod * inv[x - i] % mod * fac_inv[i] % mod * fac_inv[n - i] % mod;
        if ((n - i) & 1)res -= temp;
        else res += temp;
        res %= mod;
    }
    return (res + mod) % mod;
}
void solve() {
    n = rd();
    int q = rd();
    for (int i = 0; i <= n; i++)f[i] = rd();
    f[n + 1] = cal(n + 1, n);
    for (int i = 1; i <= n + 1; i++) {
        f[i] += f[i - 1];
        f[i] %= mod;
    }
    while (q--) {
        int l = rd(), r = rd();
        printf("%lld\n", (cal(r, n + 1) - cal(l - 1, n + 1) + mod) % mod);
    }
}
void init() {
    get_inv(mod);//线性求逆元
    fac[0] = 1;
    for (int i = 1; i <= 1007; i++)
        fac[i] = fac[i - 1] * i % mod;
    fac_inv[1007] = qpow(fac[1007], mod - 2);
    for (int i = 1006; i >= 0; i--)//线性求阶乘逆元
        fac_inv[i] = fac_inv[i + 1] * (i + 1) % mod;
}
int main() {
    init();
    int _T = rd();
    while (_T--)solve();
}