#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

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

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

int main(void) {
  cin >> T;
  while (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) {
          X[(d+1)%2][x][y] = 0;
          for(int i=x;i<=y;++i)
            for(int j=i;j<=y;++j) 
              X[(d+1)%2][x][y] += X[d%2][i][j];
          X[(d+1)%2][x][y] %= MOD;
        }
    }

    cout << X[D%2][0][N-1] << endl;
  }
}