#include <algorithm>
#include <iostream>
#include <vector>
#include <cstring>

#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define MAXN 100
#define MOD 1000000009

using namespace std;

long long X[2][MAXN+7][MAXN+7];
int N,D,T;

int main(void) {
  cin >> T;
  REP(t,T) {
    cin >> N >> D;
    vector<long long> v(N);
    REP(i,N) cin >> v[i];
    memset(X,0,sizeof(X));
    
    for (int len=1; len<=N; ++len)
      for (int i=0; i+len<=N; ++i) {
        X[0][i][i+len] = v[i];
        if (len > 1) X[0][i][i+len] += X[0][i+1][i+len];
        X[0][i][i+len] %= MOD;
      }

    for (int d=1; d<=D; ++d) {
      int cur=d%2, prev=1-cur;
      memset(X[cur],0,sizeof(X[cur]));
      for (int len=1; len<=N; ++len)
        for (int i=0; i+len<=N; ++i) {
          X[cur][i][i+len] = X[prev][i][i+len];
          if (len > 1) {
            X[cur][i][i+len] += X[cur][i+1][i+len];
            X[cur][i][i+len] += X[cur][i][i+len-1];
          }
          if (len > 2) {
            X[cur][i][i+len] -= X[cur][i+1][i+len-1];
          }
          X[cur][i][i+len] += MOD;
          X[cur][i][i+len] %= MOD;
        }
    }
    cout << X[D%2][0][N] << endl;
  }
}