import java.io.File; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.io.IOException; import java.io.InputStream; import java.util.Arrays; import java.util.BitSet; import java.util.HashMap; import java.util.NoSuchElementException; public class Main { public static void main(String[] args) { new Main(); } public Main() { InputChecker ic = new InputChecker(System.in); java.io.PrintWriter out = new java.io.PrintWriter(System.out); solve(ic, out); out.flush(); } public void solve(InputChecker ic, java.io.PrintWriter out) { int T = ic.nextInt(1, 6000); if (!isPrime(T)) throw new AssertionError(T + "is not prime"); ic.readNewLine(); int sum = 0; HashMap data = new HashMap<>(); for (int i : new int[] { 2, 3, 5, 7, 11, 13 }) { data.put(i, new Data(i)); } while (T-- > 0) { int N = ic.nextInt(1, 300); if (!isPrime(N)) throw new AssertionError(N + " is not prime"); ic.nextChar(' '); int P = ic.nextInt(100_000_000, 1_000_000_000); if (!isPrime(P)) throw new AssertionError(P + " is not prime"); ic.readNewLine(); sum += N; int[] A = new int[N]; for (int i = 0; i < N; ++i) { A[i] = ic.nextInt(1, 1_000_000_000); if (!isPrime(A[i])) throw new AssertionError(A[i] + " is not prime"); if (i == N - 1) ic.readNewLine(); else ic.nextChar(' '); } for (int i = 2; i < N; ++i) if (A[i] - A[i - 1] != A[1] - A[0]) throw new AssertionError(Arrays.toString(A) + " is not arithmetic progression"); // 等差数列 int a = A[0], d = A[1] - A[0]; long ans = data.get(N).calc(a, d); System.out.println(ans % P); } if (sum > 6000) throw new AssertionError("sum N is over 6000: " + sum); ic.checkEOF(); } static final class Data { int N; static final class Search { final int N, M, positive; final int first; final int[] left, right; Search(BitSet set, int positive, int N, int M) { this.N = N; this.M = M; this.positive = positive; first = set.nextSetBit(0); int last = set.previousSetBit(set.length()); left = new int[last - first + 1]; right = new int[left.length]; left[0] = first; for (int i = 1; i < left.length; ++i) { if (set.get(i + first)) left[i] = i + first; else left[i] = left[i - 1]; } right[right.length - 1] = last; for (int i = left.length - 1; i >= 0; --i) { if (set.get(i + first)) right[i] = i + first; else right[i] = right[i + 1]; } } long calc(int a, int d) { // 初項a, 公差dの数列 long weight = (long) a * (2 * positive - M); int shift = N * (N + 1) / 2; long mid = shift - weight / d; if (first >= mid) return Math.abs(weight + (long) (first - shift) * d); // 最適: a - first d int last = first + left.length - 1; if (mid >= last) return Math.abs(weight + (long) (last - shift) * d); // 最適: a - last d int l = left[(int) mid - first], r = right[(int) mid - first]; return Math.min(Math.abs(weight + (long) (l - shift) * d), Math.abs(weight + (long) (r - shift) * d)); // 最適は隣接するどちらか } } Search[][] compress; // compress[S][x]: {0,1,…,N-1}の部分集合Sに対して、x個を正として選ぶ時に作れる答え Data(int N) { this.N = N; compress = new Search[1 << N][]; BitSet[][] dp = dp(N); for (int i = 1; i < compress.length; ++i) { int len = Integer.bitCount(i); Search[] array = compress[i] = new Search[len + 2 >> 1]; for (int j = 0; j < array.length; ++j) array[j] = new Search(dp[i][j], j, N, len); } } private BitSet[][] dp(int N) { BitSet[][] dp = new BitSet[1 << N][N + 1]; // dp[S][x]: {0,1,…,N-1}の部分集合Sに対して、x個を正として選ぶ時に作れる総和 int mid = N * (N + 1) / 2, setLen = mid << 1 | 1; for (int i = 0; i < dp.length; ++i) { int len = Integer.bitCount(i); { // 初項 dp[i][len] = new BitSet(setLen); // 全部を正で選ぶ int sum = mid; for (int j = 0; j < N; ++j) if ((i >> j & 1) != 0) sum += j; dp[i][len].set(sum); } for (int j = 0; j < len; ++j) { dp[i][j] = new BitSet(setLen); for (int k = 0; k < N; ++k) { if ((i >> k & 1) == 0) continue; dp[i][j].or(dp[i ^ 1 << k][j].get(k, setLen)); } } } return dp; } long calc(int a, int d) { long sum = 0; for (int i = 1; i < compress.length; ++i) { long min = Long.MAX_VALUE; for (Search s : compress[i]) { long calc = s.calc(a, d); min = Math.min(min, calc); } sum += min; } return sum; } } public static class Barrett { private final int mod; private final long h, l; private final long MAX = 1L << 62; private final int MASK = (1 << 31) - 1; Barrett(final int mod) { this.mod = mod; final long t = MAX / mod; h = t >>> 31; l = t & MASK; } int reduce(final long x) { final long xh = x >>> 31, xl = x & MASK; long z = xl * l; z = xl * h + xh * l + (z >>> 31); z = xh * h + (z >>> 31); int ret = (int) (x - z * mod); return ret < 0 || ret >= mod ? ret - mod : ret; } } private static boolean isSPRP(Barrett n, int a) { int d = n.mod - 1, s = Integer.numberOfTrailingZeros(d); d >>= s; int cur = 1, pw = d; do { if ((pw & 1) != 0) cur = n.reduce((long) cur * a); a = n.reduce((long) a * a); pw >>= 1; } while (pw != 0); if (cur == 1) return true; while (s-- > 0) { if (cur == n.mod - 1) return true; cur = n.reduce((long) cur * cur); } return false; } private static final int bases[] = { 15591, 2018, 166, 7429, 8064, 16045, 10503, 4399, 1949, 1295, 2776, 3620, 560, 3128, 5212, 2657, 2300, 2021, 4652, 1471, 9336, 4018, 2398, 20462, 10277, 8028, 2213, 6219, 620, 3763, 4852, 5012, 3185, 1333, 6227, 5298, 1074, 2391, 5113, 7061, 803, 1269, 3875, 422, 751, 580, 4729, 10239, 746, 2951, 556, 2206, 3778, 481, 1522, 3476, 481, 2487, 3266, 5633, 488, 3373, 6441, 3344, 17, 15105, 1490, 4154, 2036, 1882, 1813, 467, 3307, 14042, 6371, 658, 1005, 903, 737, 1887, 7447, 1888, 2848, 1784, 7559, 3400, 951, 13969, 4304, 177, 41, 19875, 3110, 13221, 8726, 571, 7043, 6943, 1199, 352, 6435, 165, 1169, 3315, 978, 233, 3003, 2562, 2994, 10587, 10030, 2377, 1902, 5354, 4447, 1555, 263, 27027, 2283, 305, 669, 1912, 601, 6186, 429, 1930, 14873, 1784, 1661, 524, 3577, 236, 2360, 6146, 2850, 55637, 1753, 4178, 8466, 222, 2579, 2743, 2031, 2226, 2276, 374, 2132, 813, 23788, 1610, 4422, 5159, 1725, 3597, 3366, 14336, 579, 165, 1375, 10018, 12616, 9816, 1371, 536, 1867, 10864, 857, 2206, 5788, 434, 8085, 17618, 727, 3639, 1595, 4944, 2129, 2029, 8195, 8344, 6232, 9183, 8126, 1870, 3296, 7455, 8947, 25017, 541, 19115, 368, 566, 5674, 411, 522, 1027, 8215, 2050, 6544, 10049, 614, 774, 2333, 3007, 35201, 4706, 1152, 1785, 1028, 1540, 3743, 493, 4474, 2521, 26845, 8354, 864, 18915, 5465, 2447, 42, 4511, 1660, 166, 1249, 6259, 2553, 304, 272, 7286, 73, 6554, 899, 2816, 5197, 13330, 7054, 2818, 3199, 811, 922, 350, 7514, 4452, 3449, 2663, 4708, 418, 1621, 1171, 3471, 88, 11345, 412, 1559, 194 }; public static boolean isPrime(final int x) { if (x == 2 || x == 3 || x == 5 || x == 7) return true; if ((x & 1) == 0 || x % 3 == 0 || x % 5 == 0 || x % 7 == 0) return false; if (x < 121) return x > 1; return checkPrime(x); } private static boolean checkPrime(final int x) { if (x < 121) return x > 1; long h = x; h = (h >> 16 ^ h) * 0x45d9f3b; h = (h >> 16 ^ h) * 0x45d9f3b; h = (h >> 16 ^ h) & 0xFF; return isSPRP(new Barrett(x), bases[(int) h]); } public static int exponent10(int n, int e) { return n * pow(10, e); } public static long exponent10L(int n, int e) { return n * pow(10L, e); } public static int pow(int a, int b) { int ans = 1; for (int mul = a; b > 0; b >>= 1, mul *= mul) if ((b & 1) != 0) ans *= mul; return ans; } public static long pow(long a, long b) { long ans = 1; for (long mul = a; b > 0; b >>= 1, mul *= mul) if ((b & 1) != 0) ans *= mul; return ans; } public static class CharSet { private final BitSet set = new BitSet(256); public void add(char... c) { for (char i : c) set.set(i); } public void add(CharSet... s) { for (CharSet i : s) set.or(i.set); } public boolean contains(char... c) { for (char i : c) if (!set.get(i)) return false; return true; } public boolean contains(String s) { return contains(s.toCharArray()); } private static final class Chars extends CharSet { public Chars(char... c) { super.add(c); } public Chars(CharSet... s) { super.add(s); } @Override public void add(char... c) { throw new UnsupportedOperationException(); } @Override public void add(CharSet... s) { throw new UnsupportedOperationException(); } } public static final CharSet NUMBER = new Chars('0', '1', '2', '3', '4', '5', '6', '7', '8', '9'); public static final CharSet LOWER = new Chars('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'); public static final CharSet UPPER = new Chars('A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'); public static final CharSet ALPHABET = new Chars(LOWER, UPPER); } public static class InputChecker { private InputStream in; private final byte[] buffer = new byte[1024]; private final byte[] undo = new byte[1024]; private int undoSize = 0; private int read = 0; private int length = 0; public InputChecker(InputStream in) { this.in = in; } public final void setInputStream(InputStream in) { this.in = in; } public final void setInputStream(File in) { try { this.in = new FileInputStream(in); } catch (FileNotFoundException e) { e.printStackTrace(); } } private boolean hasNextByte() { if (undoSize > 0) return true; if (read < length) return true; read = 0; try { length = in.read(buffer); } catch (IOException e) { e.printStackTrace(); } return length > 0; } private byte readByte() { if (hasNextByte()) return undoSize > 0 ? undo[--undoSize] : buffer[read++]; throw new NoSuchElementException(); } private void undo(byte b) { undo[undoSize++] = b; } private void undo(char c) { if ((c & 0xFF80) == 0) { undo((byte) c); return; } undo((byte) (c & 0x3F | 0x80)); if ((c & 0xF800) == 0) { undo((byte) (c >> 6 & 0x1F | 0xC0)); } else { undo((byte) (c >> 6 & 0x3F | 0x80)); undo((byte) (c >> 12 | 0xE0)); } } public final boolean hasNext() { return hasNextByte(); } public final char nextChar() { byte b = readByte(); if ((b & 0x80) == 0) return (char) b; if ((b & 0x20) == 0) return (char) ((b & 0x1F) << 6 | readByte() & 0x3F); return (char) ((b & 0xF) << 12 | (readByte() & 0x3F) << 6 | readByte() & 0x3F); } public final char nextChar(char estimate) { char c = nextChar(); if (estimate == c) return estimate; undo(c); throw new AssertionError(); } public final char nextChar(CharSet estimate) { char c = nextChar(); if (estimate.contains(c)) return c; undo(c); throw new AssertionError(); } public final void readNewLine() { char c = nextChar(); if (c == '\r') { c = nextChar(); if (c != '\n') undo(c); return; } else if (c == '\n') return; undo(c); throw new AssertionError(); } public final void checkEOF() { if (hasNextByte()) throw new AssertionError(); } public final String next(CharSet contains) { StringBuilder sb = new StringBuilder(); try { do { char c = nextChar(); if (!contains.contains(c)) { undo(c); return sb.toString(); } sb.append(c); } while (true); } catch (NoSuchElementException e) { if (sb.length() <= 0) throw new AssertionError(); return sb.toString(); } } public final int nextInt() { byte b = readByte(); int n = 0; if (b == '-') { if (!isNumber(b = readByte())) { undo(b); throw new NumberFormatException(); } try { if (b == '0') { if (!isNumber(b = readByte())) { undo(b); return 0; } throw new NumberFormatException(); } do n = Math.addExact(Math.multiplyExact(n, 10), '0' - b); while (isNumber(b = readByte())); undo(b); } catch (NoSuchElementException e) {} return n; } if (!isNumber(b)) { undo(b); throw new NumberFormatException(); } try { if (b == '0') { if (!isNumber(b = readByte())) { undo(b); return 0; } throw new NumberFormatException(); } do n = Math.addExact(Math.multiplyExact(n, 10), b - '0'); while (isNumber(b = readByte())); undo(b); } catch (NoSuchElementException e) {} return n; } public final int nextInt(int min, int max) { int n = nextInt(); if (min <= n && n <= max) return n; throw new NumberFormatException(); } private static boolean isNumber(byte c) { return '0' <= c && c <= '9'; } public final long nextLong() { byte b = readByte(); long n = 0; if (b == '-') { if (!isNumber(b = readByte())) { undo(b); throw new NumberFormatException(); } try { if (b == '0') { if (!isNumber(b = readByte())) { undo(b); return 0; } throw new NumberFormatException(); } do n = Math.addExact(Math.multiplyExact(n, 10), '0' - b); while (isNumber(b = readByte())); undo(b); } catch (NoSuchElementException e) {} return n; } if (!isNumber(b)) { undo(b); throw new NumberFormatException(); } try { if (b == '0') { if (!isNumber(b = readByte())) { undo(b); return 0; } throw new NumberFormatException(); } do n = Math.addExact(Math.multiplyExact(n, 10), b - '0'); while (isNumber(b = readByte())); undo(b); } catch (NoSuchElementException e) {} return n; } public final long nextLong(long min, long max) { long n = nextLong(); if (min <= n && n <= max) return n; throw new NumberFormatException(); } public final double nextDouble() { StringBuilder sb = new StringBuilder(); byte b = readByte(); if (b == '-') { sb.append(b); b = readByte(); } if (b == '0') { sb.append(b); b = readByte(); } else { while (isNumber(b)) { sb.append(b); b = readByte(); } } if (b == '.') { sb.append(b); b = readByte(); while (isNumber(b)) { sb.append(b); b = readByte(); } } if (b == 'e' || b == 'E') { sb.append(b); b = readByte(); if (b == '-' || b == '+') { sb.append(b); b = readByte(); } while (isNumber(b)) { sb.append(b); b = readByte(); } } undo(b); return Double.parseDouble(sb.toString()); } } }