#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <cassert>
#include <cstring>

using namespace std;

#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define FOR(i,a,n) for(int (i)=(a);(i)<(int)(n);(i)++)

using namespace std;

typedef long long ll;

const int NON_PRIME = 17;
const int MAXMAKS = (1 << NON_PRIME) + 2;
const int MAXN = 300;
const int MAXK = 50;
const int mod = (int) 1e9 + 7;

int T, n, K, L, a[MAXN];
int result[MAXMAKS][50];
int C[MAXN][MAXN], GCD[MAXN][MAXN];
int isImportant[MAXN];
int importantIndex[MAXN];
vector<int> imp;

void precompute() {
  for (int n = 0; n < MAXN; n++) {
    C[n][0] = 1;
  }
  for (int n = 1; n < MAXN; n++) {
    for (int r = 1; r < MAXN; r++) {
      C[n][r] = (C[n - 1][r - 1] + C[n - 1][r]) % mod;
    }
  }
  for (int i = 1; i < MAXN; i++) {
    for (int j = 1; j < MAXN; j++) {
      GCD[i][j] = __gcd(i, j);
    }
  }
}

int prime(int n) {
  if (n < 2) return false;
  for (int i = 2; i * i <= n; i++) if (n % i == 0) return false;
  return true;
}

int dp[MAXMAKS];

vector<int> computeRequired(int mask) {
  int newMask = 0;
  int alreadyMask = 0;
  for (int i = 0; i < n; i++) {
    if (isImportant[a[i]]) {
      newMask |= (1 << importantIndex[a[i]]);
    }
    alreadyMask |= (1 << (a[i] - 1));
  }
  for (int i = 0; i < imp.size(); i++) {
    if (mask & (1 << i)) {
      newMask |= (1 << i);
      alreadyMask |= (1 << (imp[i] - 1)); 
    }
  }
  vector<int> required;
  for (int i = 0; i < L; i++) {
    if ((dp[newMask] & (1 << i)) && (alreadyMask & (1 << i)) == 0) {
      required.push_back(i + 1);
    }
  }
  return required;
}

void doit(int mask) {
  vector<int> required = computeRequired(mask);

  for (auto x : required) if (isImportant[x]) return;

  for (int k = required.size(); k <= K; k++) {
    int remK = k - required.size();
    int total = L - imp.size();
    int ans = C[remK + total - 1][total - 1];
    result[mask][k] = ans;
  }
}


void findRequired() {
  // Precompute all closed sets in O(2**(imp.size()) * imp.size())
  for(int mask = 0; mask < (1 << imp.size()); mask++) {
    int low_bit = 0;
    for(int i = 0; i < imp.size(); i++){
      if(mask & (1 << i)){
          low_bit = i;
          break;
      }
    }
    int closed_set = dp[mask ^ (1 << low_bit)];
    for(int i = low_bit; i < imp.size(); i++){
      if(mask & (1 << i)){
        int g = GCD[imp[i]][imp[low_bit]];
        closed_set |= (1 << (g - 1));
      }
    }
    dp[mask] = closed_set;
    //cerr << "mask " << mask << " " << dp[mask] << endl;
  }
}

int doDp() {
  cerr << "imp.size() " << imp.size() << endl;
  int ans = 0;
  if (imp.size() == 0) ans = result[0][K];
  else {
    // ways[mask][x]
    int anotherAns = 0;
    anotherAns += result[0][K];
    if (anotherAns >= mod) anotherAns -= mod;
    FOR(mask, 1, (1 << imp.size())) FOR(x, 1, K + 1) {
      int cnt = __builtin_popcount(mask);
      // a_1 + a_2 + .. + a_cnt = x - cnt
      if (x < cnt) continue;
      int ways = C[x - 1][cnt - 1];
      anotherAns = (anotherAns + (ways * (long long) result[mask][K - x])) % mod;
    }
    ans = anotherAns;
  }
  return ans;
}

int solve() {
  memset(dp, 0, sizeof(dp));
  findRequired();
  memset(result, 0, sizeof(result));
  REP(mask, (1 << imp.size())) doit(mask);
  return doDp();
}

void computeImportantElements() {
  memset(isImportant, 0, sizeof(isImportant));
  memset(importantIndex, 0, sizeof(importantIndex));
  imp.clear();
  int idx = 0;
  for (int i = 2; i <= L; i++) {
    if (!prime(i)) {
      imp.push_back(i);
      isImportant[i] = true;
      importantIndex[i] = idx++;
    }
  }
}

const int VALUE = 27;

void readInput() {
  cin >> n >> K >> L;
  assert(n >= 1 && n <= VALUE);
  assert(K >= 1 && K <= VALUE);
  assert(L >= 1 && L <= VALUE);
  int one = false;
  int mx = 0;
  REP(i, n) {
    cin >> a[i];
    assert(a[i] >= 1 && a[i] <= 27);
    if (a[i] == 1) one = true;
    mx = max(mx, a[i]);
  }
  assert(L >= mx);
  assert(one);
}

int main() {
  precompute();

  cin >> T;
  assert(T >= 1 && T <= 10);
  int tc = 1;
  while (T--) {
    cerr << "processing test case " << tc++ << endl;

    readInput();
    computeImportantElements();
    int ans = solve();

    cout << ans << endl;
  }
  return 0;
}