#include <bits/stdc++.h>

using LL = long long;
using ULL = unsigned LL;

constexpr int N = 122;

int mod;
struct BarrettModulo {
    uint64_t p; // The modulus
    uint64_t m; // Precomputed value for optimization
    BarrettModulo(uint64_t modulus) : p(modulus) { m = ((__uint128_t)1 << 64) / p; }
    uint64_t operator()(uint64_t x) const { return x - ((__uint128_t(x) * m) >> 64) * p; }
};
BarrettModulo bmod(2);

int n;
int inv[201];
int hl[N], hr[N];
struct Poly : std::array<int, N> {
    template <typename... Args>
    Poly(Args... args): std::array<int, N>::array{args...} {}
    Poly friend operator*(Poly a, Poly b) {
        Poly c = {};
        for (int i = 0; i < N; i++) if (a[i]) for (int j = 0; i + j < N; j++) c[i + j] = bmod(c[i + j] + (ULL)a[i] * b[j]);
        return c;
    }
};

Poly h[N][2];
struct ST {
    Poly poly[N * 4][3][3];
    int ls(int u) { return u << 1; }
    int rs(int u) { return u << 1 | 1; }
    void push_up(int u, int l, int r) {
        int mid = (l + r) >> 1;
        for (int o0 : {0, 1, 2}) for (int o1 : {0, 1, 2}) poly[u][o0][o1] = {};
        for (int o0 : {0, 1, 2}) for (int o1 : {0, 1, 2}) for (int _o0 : {0, 1, 2}) for (int _o1 : {0, 1, 2}) {
            if (o1 + _o0 < 2) continue;
            for (int i = 0; i <= mid - l + 1; i++) for (int j = 0; j <= r - mid; j++) 
                poly[u][o0][_o1][i + j] = bmod(poly[u][o0][_o1][i + j] + (ULL)poly[ls(u)][o0][o1][i] * poly[rs(u)][_o0][_o1][j]);
        }
    }
    void build(int u, int l, int r) {
        if (r - l + 1 <= 3) {
            int t = r - l + 1;
            for (int o0 : {0, 1, 2}) for (int o1 : {0, 1, 2}) poly[u][o0][o1] = {};
            if (t == 2) {
                poly[u][1][0] = h[l + 0][0] * h[l + 1][1];
                poly[u][0][1] = h[l + 0][1] * h[l + 1][0];
                poly[u][2][2] = h[l + 0][0] * h[l + 1][0];
            }
            else {
                poly[u][0][2] = h[l + 0][1] * h[l + 1][0] * h[l + 2][0];
                poly[u][2][0] = h[l + 0][0] * h[l + 1][0] * h[l + 2][1];
                poly[u][1][1] = h[l + 0][0] * h[l + 1][1] * h[l + 2][0];
                poly[u][2][2] = h[l + 0][0] * h[l + 1][0] * h[l + 2][0];
            }
            return;
        }
        int mid = (l + r) >> 1;
        build(ls(u), l, mid);
        build(rs(u), mid + 1, r);
        push_up(u, l, r);
    }
    void upd(int u, int l, int r, int x) {
        if (r - l + 1 <= 3) return build(u, l, r);
        int mid = (l + r) >> 1;
        if (x <= mid) upd(ls(u), l, mid, x);
        else upd(rs(u), mid + 1, r, x);
        push_up(u, l, r);
    }
};
ST st;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int T;
    std::cin >> T >> mod;
    bmod = mod;
    inv[0] = inv[1] = 1;
    for (int i = 2; i <= 200; i++) inv[i] = bmod((ULL)(mod - mod / i) * inv[mod % i]);
    while (T--) {
        std::cin >> n;
        std::vector<int> hash = {0};
        for (int i = 1; i <= n; i++) {
            std::cin >> hl[i];
            hash.push_back(--hl[i]);
        }
        for (int i = 1; i <= n; i++) {
            std::cin >> hr[i];
            hash.push_back(hr[i]);
        }
        std::sort(hash.begin(), hash.end());
        hash.resize(std::unique(hash.begin(), hash.end()) - hash.begin());
        int all = 1;
        for (int i = 1; i <= n; i++) all = bmod((ULL)all * (hr[i] - hl[i]));
        int ans = bmod((ULL)all * (hash.back() + 1));
        const auto upd = [&](int i, int cur) {
            if (cur >= hr[i]) {
                h[i][0] = {hr[i] - hl[i]};
                h[i][1] = {};
            }
            else if (cur < hl[i]) {
                h[i][0] = {};
                h[i][1] = {hr[i] - hl[i]};
            }
            else {
                h[i][0] = {mod - hl[i] % mod, 1};
                h[i][1] = {hr[i], mod - 1};
            }
        };
        for (int i = 1; i <= n; i++) upd(i, hash[0]);
        st.build(1, 1, n);
        for (int o = 0; o + 1 < hash.size(); o++) {
            Poly poly = {};
            for (int o0 : {0, 1, 2}) for (int o1 : {0, 1, 2}) for (int i = 0; i <= n; i++) poly[i] = bmod(poly[i] + st.poly[1][o0][o1][i]);
            const auto calc = [&](int i) {
                int x = 1, res = 0;
                for (int j = 0; j <= n; j++) {
                    res = bmod(res + (ULL)x * poly[j]);
                    x = bmod((ULL)x * i);
                }
                return res;
            };
            if (hash[o + 1] - hash[o] <= n + 2) for (int i = hash[o] + 1; i <= hash[o + 1]; i++) ans = bmod(ans + (ULL)(mod - 1) * calc(i));
            else {
                std::vector<std::pair<int, int>> vec;
                for (int i = hash[o] + 1; i <= hash[o] + n + 2; i++) vec.push_back({i, calc(i)});
                for (int i = 1; i < vec.size(); i++) vec[i].second = bmod(vec[i - 1].second + vec[i].second);
                int res = 0;
                for (int i = 0; i < vec.size(); i++) {
                    int t = vec[i].second, t0 = mod - 1, t1 = 1;
                    for (int j = 0; j < vec.size(); j++) if (i != j) {
                        t = bmod((ULL)t * inv[std::abs(i - j)]);
                        if (i < j) t = bmod((ULL)t * (mod - 1));
                        int _j = mod - bmod(vec[j].first);
                        t0 = bmod((ULL)t0 * (hash[o] + _j));
                        t1 = bmod((ULL)t1 * (hash[o + 1] + _j));
                    }
                    res = bmod(res + (ULL)t * (t0 + t1));
                }
                ans = bmod(ans + (ULL)res * (mod - 1));
            }
            for (int i = 1; i <= n; i++) if (hash[o + 1] == hl[i] || hash[o + 1] == hr[i]) {
                upd(i, hash[o + 1]);
                st.upd(1, 1, n, i);
            }
        }
        std::cout << ans << '\n';
    }
    return 0;
}