OI XXXI - zyr (Alt)

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

#include <bits/stdc++.h>

const int MOD = 1000000007;

struct Trans {
    int a, b;
};

Trans combine(Trans t1, Trans t2) {
    return {(int)((1LL * t2.a * t1.a) % MOD), (int)((1LL * t2.a * t1.b + t2.b) % MOD)};
}

const int C_SQRT = 35000;
Trans pow_small[C_SQRT + 5];
Trans pow_large[C_SQRT + 5];

int k, q;
std::vector<int> m_seq;
std::vector<int> D_seq;
std::vector<Trans> pref_t;
std::vector<Trans> cycl_t;
int cycle_start;
int P_len, L_len;
Trans full_cycle;

void precompute() {
    std::vector<int> visited(k, -1);
    int current_m = 1 % k;
    int step = 0;

    m_seq.reserve(k);
    D_seq.reserve(k);

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

        long long val = 1LL * current_m * (current_m + 1) / 2 + 1;
        int next_m = val % k;
        long long d = val / k;

        D_seq.push_back(d % MOD);
        current_m = next_m;
        step++;
    }

    P_len = cycle_start;
    L_len = step - cycle_start;

    int H = ((k + 1LL) / 2) % MOD;

    pref_t.assign(P_len + 1, {1, 0});
    for (int i = 0; i < P_len; i++) {
        Trans t = {H, D_seq[i]};
        pref_t[i + 1] = combine(pref_t[i], t);
    }

    cycl_t.assign(L_len + 1, {1, 0});
    for (int i = 0; i < L_len; i++) {
        Trans t = {H, D_seq[cycle_start + i]};
        cycl_t[i + 1] = combine(cycl_t[i], t);
    }

    full_cycle = cycl_t[L_len];

    pow_small[0] = {1, 0};
    for (int i = 1; i <= C_SQRT; i++) {
        pow_small[i] = combine(pow_small[i - 1], full_cycle);
    }

    pow_large[0] = {1, 0};
    Trans giant_step = pow_small[C_SQRT];
    for (int i = 1; i <= C_SQRT; i++) {
        pow_large[i] = combine(pow_large[i - 1], giant_step);
    }
}

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

    Trans total;
    if (G <= P_len) {
        out_m = m_seq[G];
        total = pref_t[G];
    } else {
        long long rem_steps = G - P_len;
        long long num_cycles = rem_steps / L_len;
        int rem = rem_steps % L_len;

        Trans t1 = pref_t[P_len];

        long long y = num_cycles / C_SQRT;
        int z = num_cycles % C_SQRT;
        Trans t2 = combine(pow_large[y], pow_small[z]);

        Trans t3 = cycl_t[rem];

        total = combine(t1, combine(t2, t3));
        out_m = m_seq[cycle_start + rem];
    }

    long long Q0 = 1 / k;
    return (1LL * total.a * Q0 + total.b) % MOD;
}

bool has_child(int X, int Y) {
    long long C = (1LL * X * (X - 1) / 2) % k;
    long long target = (Y - 1) % k;
    long long dist = (target - C - 1 + 2 * k) % k;
    return dist < X;
}

int main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);

    std::cin >> k >> q;

    precompute();

    for (int i = 0; i < q; i++) {
        int d;
        long long p;
        std::cin >> d >> p;

        std::vector<int> a(d);
        for (int j = 0; j < d; j++) {
            std::cin >> a[j];
        }

        int first_bad_L = d;
        for (int j = 1; j < d; j++) {
            if (!has_child(a[j], a[j - 1])) {
                first_bad_L = j;
                break;
            }
        }

        int last_bad_R = -1;
        for (int j = d - 2; j >= 0; j--) {
            if (!has_child(a[j], a[j + 1])) {
                last_bad_R = j;
                break;
            }
        }

        long long total_paths = 0;

        for (int r = 0; r < d; r++) {
            if (r >= first_bad_L) continue;
            if (r <= last_bad_R) continue;
            if (r > 0 && r < d - 1 && a[r - 1] == a[r + 1]) continue;

            long long max_arm = std::max((long long)r, (long long)(d - 1 - r));
            long long max_g = p - max_arm;

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

                long long count = Q;
                if (a[r] <= M) count++;

                total_paths = (total_paths + count % MOD) % MOD;
            }
        }
        std::cout << total_paths << "\n";
    }

    return 0;
}