mod = 10**9 + 7 def compute_f1(W, A): target = W dp = [0] * (target + 1) dp[0] = 1 for x in range(1, target + 1): for a in A: if x - a >= 0: dp[x] = (dp[x] + dp[x - a]) % mod return dp[target] def compute_f2(W, A): target = 2 * W dp = [0] * (target + 1) dp[0] = 1 for x in range(1, target + 1): if x == W: dp[x] = 0 continue for a in A: prev = x - a if prev >= 0 and prev != W: dp[x] = (dp[x] + dp[prev]) % mod return dp[target] def multiply(a, b): res = [[0] * 2 for _ in range(2)] for i in range(2): for j in range(2): for k in range(2): res[i][j] = (res[i][j] + a[i][k] * b[k][j]) % mod return res def matrix_power(mat, power): result = [[1, 0], [0, 1]] # Identity matrix while power > 0: if power % 2 == 1: result = multiply(result, mat) mat = multiply(mat, mat) power //= 2 return result n, w, k = map(int, input().split()) a = list(map(int, input().split())) f1 = compute_f1(w, a) f2 = compute_f2(w, a) T = [ [f1, f2], [1, 0] ] mat = matrix_power(T, k) ans = mat[0][0] % mod print(ans)