from sys import stdin

MOD = 1000000009

def modexp(x,y):
  if y==0: return 1
  if y==1: return x % MOD
  z = modexp(x,y/2)
  z = (z*z) % MOD
  if y%2: z=(z*x) % MOD
  return z

def inverse(x): return modexp(x,MOD-2)

fact = [1,1]
for i in range(2,10047): fact.append( (fact[-1]*i) % MOD )
ifact = [1,1]
for i in range(2,10047): ifact.append( inverse(fact[i]) )

def comb(n,k): return (fact[n] * ifact[k] * ifact[n-k]) % 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() ]
  result = 0
  for i in range(N): result = (result + A[i] * comb(D+i,D) * comb(D+N-1-i,D)) % MOD
  print result