OI XXXI - zyr

// https://szkopul.edu.pl/problemset/problem/AWwhm-sG6VDE2LwvWMCNS-fB/site/?key=statement

#include <bits/stdc++.h>

// #define GARY_DBG
#define GARY_LIB

constexpr int sizik = 10 * 1000 * 1001;

#define ar std::array

#define int int64_t

typedef std::vector<std::vector<int>> _kra;

constexpr int MOD = 1e9 + 7;
int k, q;

struct Func {
    int a, b;
    Func(int a1, int b1) : a(a1), b(b1) {}
};

Func combine(Func f1, Func f2) {
    return {(f2.a * f1.a) % MOD, (f2.a * f1.b + f2.b) % MOD};
}

Func ident() {
    return {1, 0};
}

Func power(Func f1, int p) {
    Func res = ident();
    while (p > 0) {
        if (p & 1) res = combine(res, f1);
        f1 = combine(f1, f1);
        p >>= 1;
    }
    return res;
}

int apply(Func f, int x) {
    return (f.a * x + f.b) % MOD;
}

bool has_child(int x, int y) {
    int target = (y - 1) % k;
    int start = (1 + (x * (x - 1LL)) / 2) % k;
    int dist = (target - start + k) % k;
    return dist < x;
}

std::vector<int> M_val, B_val, M_val_cycle;
int visited[sizik];
std::vector<Func> pref_t, cycl_t;
Func full_cycle{1, 0};

int P_len = 0, L_len = 0;

void precompute() {
    for (int i = 0; i <= k; i++) {
        visited[i] = -1;
    }

    const int M_start = 1 % k;
    int M = M_start, step = 0;
    int cycle_start = -1;

    auto calc_next_MB = [](int old_M) -> std::pair<int, int> {
        int val = old_M * (old_M + 1) / 2 + 1;
        int next_M = val % k;
        int B = val / k;
        return std::make_pair(next_M, B);
    };

    while (true) {
        if (visited[M] != -1) {
            cycle_start = M;
            break;
        }
        visited[M] = step;
        M_val.push_back(M);

        auto [next_M, B] = calc_next_MB(M);

        B_val.push_back(B);

        M = next_M, step++;
    }

    M = M_start;
    bool is_cycle = false;
    M_val_cycle.reserve(k);
    while (true) {
        if (M == cycle_start) {
            if (!is_cycle) {
                is_cycle = true;
            } else {
                break;
            }
        }

        if (is_cycle) {
            L_len++;
            M_val_cycle.push_back(M);
        } else
            P_len++;

        auto [new_M, B] = calc_next_MB(M);
        M = new_M;
    }

    int H = ((k + 1) / 2) % MOD;
    pref_t.reserve(k);
    cycl_t.reserve(k);
    pref_t.push_back(ident());
    cycl_t.push_back(ident());
    M = M_start;
    for (int i = 1; i <= P_len; i++) {
        auto [M_new, B] = calc_next_MB(M);
        Func curr{H, B};
        pref_t.push_back(combine(pref_t.back(), curr));
        M = M_new;
    }
    M = cycle_start;
    for (int i = 1; i <= L_len; i++) {
        auto [M_new, B] = calc_next_MB(M);
        Func curr{H, B};
        cycl_t.push_back(combine(cycl_t.back(), curr));
        M = M_new;
    }
    assert(M == cycle_start);
    full_cycle = cycl_t.back();
}

int get_Q(int G, int& out_m) {
    if (G == 0) {
        out_m = 1 % k;
        return 1 / k;
    }

    int Q0 = 1 / k;
    Func total_func = ident();
    if (G <= P_len) {
        out_m = M_val[G];
        total_func = pref_t[G];
    } else {
        int rem_steps = G - P_len;
        int num_cycles = rem_steps / L_len, reszta = rem_steps % L_len;
        total_func = combine(total_func, pref_t[P_len]);
        total_func = combine(total_func, power(full_cycle, num_cycles));
        total_func = combine(total_func, cycl_t[reszta]);
        out_m = M_val_cycle[reszta];
    }

    int Q = apply(total_func, Q0);
    return Q;
}

void solve() {
    std::cin >> k >> q;

    precompute();

    for (; q > 0; q--) {
        int d, p;
        std::cin >> d >> p;
        std::vector<int> av(d);
        for (auto& a : av) {
            std::cin >> a;
        }

        int first_bad_L = d, last_bad_R = -1;
        for (int i = 1; i < d; i++) {
            if (!has_child(av[i], av[i - 1])) {
                first_bad_L = i;
                break;
            }
        }
        for (int i = d - 2; i >= 0; i--) {
            if (!has_child(av[i], av[i + 1])) {
                last_bad_R = i;
                break;
            }
        }

        int wynik = 0;
        for (int r = 0; r < d; r++) {
            if (r > 0 && r < d - 1 && av[r - 1] == av[r + 1]) {
                continue;
            }
            if (r >= first_bad_L || r <= last_bad_R) {
                continue;
            }
            int max_arm = std::max(r, d - r - 1);
            int max_g = p - max_arm;

            if (max_g >= 1) {
                int M;
                int Q = get_Q(max_g - 1, M);

                int cnt = Q;
                if (av[r] <= M) cnt++;

                cnt %= MOD;
                wynik = (wynik + cnt) % MOD;
            }
        }
        std::cout << wynik << '\n';
    }
}

int32_t main() {
#ifndef GARY_DBG
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
#endif

    int t = 1;
    // std::cin >> t;

    for (; t > 0; t--) {
        solve();
    }

    return 0;
}