// Java solution for problem J
// Author: Adam Polak

import java.util.Scanner;

public class j {
  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int Z = in.nextInt();
    while (Z-- > 0) {
      int n = in.nextInt();
      long M = in.nextLong();
      long[] W = new long[n+1];
      for (int i = 0; i <= n; ++i) W[i] = 0;
      W[0] = 1;
      long F_cur = 1, F_prev = 0;
      for (int k = 0; k < n; ++k) {
        long F_temp = (F_cur + F_prev) % M;
        F_prev = F_cur;
        F_cur = F_temp;

        for (int i = n-1; i >= 0; --i) W[i+1] = W[i];
        W[0] = 0;
        for (int i = 0; i < n; i++)
          W[i] = (W[i] - F_cur * W[i+1]) % M;
      }

      long result = 0;
      for (int i = 0; i < n; ++i) {
        long p_i = in.nextLong();
        result += (p_i * W[i]) % M;
      }

      result = -result;
      result = ((result % M) + M) % M;

      System.out.println(result);
    }
  }
}