#include <algorithm>
#include <array>
#include <cstdlib>
#include <iostream>
#include <vector>

#include <atcoder/all>

#include "atcoder/math.hpp"

int main() {
    using namespace std;
    using i64 = long long;
    using A = array<i64, 4>;
    vector<vector<A>> data{
        {},
        {},
        {},
        {},
        {},
        {
            {1, 2, 0, 44},
            {1, 1, 4, 42},
            {2, 1, 8, 38},
            {4, 1, 14, 26},
            {1, 0, 16, 18},
        },
        {},
        {
            {1, 3, -24, 180},
            {1, 2, -18, 178},
            {1, 1, 10, 164},
            {3, 2, 14, 160},
            {2, 1, 26, 142},
            {5, 2, 30, 134},
            {3, 1, 34, 124},
            {4, 1, 40, 106},
            {5, 1, 46, 82},
            {6, 1, 48, 72},
            {7, 1, 56, 24},
            {9, 1, 62, -18},
            {1, 0, 64, -36},
        },
        {},
        {},
        {},
        {
            {1, 4, -896, 2252},   {1, 3, -784, 2224},   {1, 2, -304, 2064},
            {2, 3, 4, 1910},      {3, 4, 436, 1622},    {1, 1, 484, 1586},
            {5, 4, -370, 2440},   {4, 3, -354, 2420},   {3, 2, -72, 2044},
            {5, 3, 308, 1474},    {2, 1, 536, 1094},    {7, 3, -146, 2458},
            {5, 2, -32, 2192},    {8, 3, 428, 1042},    {3, 1, 506, 834},
            {10, 3, 6, 2334},     {7, 2, 36, 2234},     {11, 3, 436, 834},
            {4, 1, 454, 768},     {13, 3, 120, 2104},   {9, 2, 126, 2078},
            {5, 1, 418, 764},     {11, 2, 222, 1744},   {6, 1, 390, 820},
            {13, 2, 302, 1348},   {7, 1, 386, 802},     {15, 2, 346, 1082},
            {8, 1, 386, 782},     {17, 2, 418, 526},    {9, 1, 430, 424},
            {19, 2, 480, -26},    {10, 1, 484, -64},    {11, 1, 586, -1084},
            {12, 1, 666, -1964},  {13, 1, 730, -2732},  {14, 1, 780, -3382},
            {15, 1, 826, -4026},  {16, 1, 868, -4656},  {17, 1, 904, -5232},
            {18, 1, 944, -5912},  {19, 1, 970, -6380},  {20, 1, 990, -6760},
            {21, 1, 1004, -7040}, {22, 1, 1008, -7124}, {23, 1, 1016, -7300},
            {25, 1, 1022, -7438}, {1, 0, 1024, -7488},
        },
        {},
        {
            {1, 5, -4792, 7576},   {1, 4, -4662, 7550},   {1, 3, -3422, 7240},
            {2, 5, -620, 6306},    {1, 2, -540, 6274},    {3, 5, -416, 6212},
            {2, 3, -366, 6182},    {3, 4, 2388, 4346},    {4, 5, 3244, 3704},
            {1, 1, 3274, 3680},    {6, 5, -2934, 9888},   {5, 4, -2924, 9876},
            {4, 3, -2444, 9276},   {3, 2, -164, 6236},    {5, 3, 788, 4808},
            {7, 4, 2870, 1338},    {2, 1, 3118, 904},     {9, 4, -2004, 11148},
            {7, 3, -1884, 10878},  {5, 2, -366, 7336},    {8, 3, 1430, 2846},
            {11, 4, 2690, -514},   {3, 1, 2738, -646},    {13, 4, -1328, 11552},
            {10, 3, -1312, 11500}, {7, 2, -520, 8860},    {11, 3, 1720, 1020},
            {4, 1, 2350, -1290},   {13, 3, -766, 11174},  {9, 2, -400, 9588},
            {14, 3, 1744, -60},    {5, 1, 2014, -1320},   {16, 3, -326, 10380},
            {11, 2, -200, 9708},   {17, 3, 1624, -324},   {6, 1, 1708, -800},
            {19, 3, 96, 8872},     {13, 2, 126, 8682},    {20, 3, 1494, -210},
            {7, 1, 1512, -330},    {22, 3, 360, 7734},    {15, 2, 366, 7690},
            {8, 1, 1338, 400},     {17, 2, 642, 5968},    {9, 1, 1270, 630},
            {19, 2, 846, 4446},    {10, 1, 1218, 912},    {21, 2, 1134, 1752},
            {11, 1, 1326, -264},   {23, 2, 1362, -660},   {12, 1, 1450, -1672},
            {25, 2, 1702, -4696},  {13, 1, 1742, -5196},  {27, 2, 1954, -7952},
            {14, 1, 1966, -8114},  {29, 2, 2166, -10914}, {15, 1, 2170, -10972},
            {16, 1, 2364, -13882}, {17, 1, 2562, -17050}, {18, 1, 2752, -20280},
            {19, 1, 2914, -23196}, {20, 1, 3120, -27110}, {21, 1, 3274, -30190},
            {22, 1, 3450, -33886}, {23, 1, 3590, -36966}, {24, 1, 3696, -39404},
            {25, 1, 3778, -41372}, {26, 1, 3858, -43372}, {27, 1, 3920, -44984},
            {28, 1, 3964, -46172}, {29, 1, 4008, -47404}, {30, 1, 4040, -48332},
            {31, 1, 4062, -48992}, {32, 1, 4076, -49426}, {33, 1, 4080, -49554},
            {34, 1, 4088, -49818}, {36, 1, 4094, -50022}, {1, 0, 4096, -50094},
        },
    };
    auto solve = [&](int n, i64 a, i64 d, i64 mod) {
        if (d == 0) return a * atcoder::pow_mod(2, n - 1, mod) % mod;
        for (const auto &x : data[n]) {
            if (d * x[0] >= a * x[1]) return (a * x[2] + d * x[3]) % mod;
        }
        return 0ll;
    };
    int t;
    cin >> t;
    while (t--) {
        i64 n, p;
        cin >> n >> p;
        vector<i64> a(n);
        for (auto &e : a) cin >> e;
        if (a[1] < a[0]) ranges::reverse(a);
        cout << solve(n, a[0], a[1] - a[0], p) << "\n";
    }
}