#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));
    
    REP(i,N)
      for(int j=i;j<N;++j)
        if (j==i) X[0][i][j] = v[i];
        else X[0][i][j] = X[0][i][j-1]+v[j];

    REP(d,D) {
      REP(x,N)
        for(int y=x;y<N;++y) {
          if (x==y) X[(d+1)%2][x][y] = X[d%2][x][y];
          else {
            X[(d+1)%2][x][y] = X[(d+1)%2][x][y-1];
            for(int i=x;i<=y;++i) {
              X[(d+1)%2][x][y] += X[d%2][i][y];
            }
            X[(d+1)%2][x][y] %= MOD;
          }
        }
    }
    cout << X[D%2][0][N-1] << endl;
  }
}