from sys import stdin

MOD = 1000000009

def solve(A,D):
  global MOD
  if D==0: return sum(A) % MOD
  result = 0
  for i in range(len(A)):
    for j in range(i+1,len(A)+1):
      result += solve(A[i:j],D-1)
  return result % MOD

T = int( stdin.readline() )
input = stdin.readlines()
for t in range(T):
  N, D = [ int(x) for x in input[3*t+1].split() ]
  A = [ int(x) for x in input[3*t+2].split() ]
  print solve(A,D)