## https://yukicoder.me/problems/no/1847 MOD = 10 ** 9 + 7 MAX_INT = 10 ** 10 def main(): L, N, M = map(int, input().split()) K = list(map(int, input().split())) L0 = L forbidden_k_map = [MAX_INT] * (N + 1) for k in K: forbidden_k_map[k] = k # 状態の数 state_list = [] for k in range(1, N + 1): for j in range(1, k + 2): state_list.append((k, j)) state_map = {} for i, state in enumerate(state_list): state_map[state] = i state_count = len(state_list) def prod(left, right): new_matrix = [ [0 for _ in range(state_count)], [[0 for _ in range(state_count)] for _ in range(state_count)] ] # 0と0どうし left_ = left[0] right_ = right[0] for l in range(state_count): l_state, l_count = state_list[l] for r in range(state_count): r_state, r_count = state_list[r] if l_state == r_state: new_count = min(l_state + 1, l_count + r_count) new_value = (left_[l] * right_[r]) % MOD new_matrix[0][state_map[(l_state, new_count)]] += new_value new_matrix[0][state_map[(l_state, new_count)]] %= MOD else: new_value = (left_[l] * right_[r]) % MOD new_matrix[1][l][r] += new_value new_matrix[1][l][r] %= MOD # left:1, right:0 left_ = left[1] right_ = right[0] for l_l in range(state_count): for l_r in range(state_count): l_state, l_count = state_list[l_r] for r in range(state_count): r_state, r_count = state_list[r] if l_state == r_state: new_count = min(l_state + 1, l_count + r_count) new_value = (left_[l_l][l_r] * right_[r]) % MOD new_matrix[1][l_l][state_map[(l_state, new_count)]] += new_value new_matrix[1][l_l][state_map[(l_state, new_count)]] %= MOD else: if forbidden_k_map[l_state] == l_count: continue new_value = (left_[l_l][l_r] * right_[r]) % MOD new_matrix[1][l_l][r] += new_value new_matrix[1][l_l][r] %= MOD # left:0 ,right1 left_ = left[0] right_ = right[1] for l in range(state_count): l_state, l_count = state_list[l] for r_l in range(state_count): for r_r in range(state_count): r_state, r_count = state_list[r_l] if l_state == r_state: new_count = min(l_state + 1, l_count + r_count) new_value = (left_[l] * right_[r_l][r_r]) % MOD new_matrix[1][state_map[(l_state, new_count)]][r_r] += new_value new_matrix[1][state_map[(l_state, new_count)]][r_r] %= MOD else: if forbidden_k_map[r_state] == r_count: continue new_value = (left_[l] * right_[r_l][r_r]) % MOD new_matrix[1][l][r_r] += new_value new_matrix[1][l][r_r] %= MOD # left1: right1 left_ = left[1] right_ = right[1] for l_l in range(state_count): base = 0 left_base = [0] * (N + 1) for l_r in range(state_count): base += left_[l_l][l_r] base %= MOD l_r_number, _ = state_list[l_r] left_base[l_r_number] += left_[l_l][l_r] left_base[l_r_number] %= MOD for r_l in range(state_count): r_l_number, r_l_count = state_list[r_l] if forbidden_k_map[r_l_number] == r_l_count: ans = left_base[r_l_number] else: ans = base for mid in range(1, N + 1): if forbidden_k_map[mid] == mid: if mid != r_l_number: ans -= left_[l_l][state_map[(mid, mid)]] ans %= MOD else: y = r_l_number - r_l_count if 1 <= y <= r_l_number + 1: ans -= left_[l_l][state_map[(r_l_number, y)]] ans %= MOD for r_r in range(state_count): new_matrix[1][l_l][r_r] += (ans * right_[r_l][r_r]) % MOD new_matrix[1][l_l][r_r] %= MOD return new_matrix def prod_vec(matrix, vector): new_vector = [0 for _ in range(state_count)] # matrix 0 mat = matrix[0] for vec_state in range(state_count): vec_number, vec_count = state_list[vec_state] for l in range(state_count): l_number, l_count = state_list[l] if vec_number == l_number: new_count = min(vec_number + 1, l_count + vec_count) new_vector[state_map[(l_number, new_count)]] += (mat[l] * vector[vec_state]) % MOD new_vector[state_map[(l_number, new_count)]] %= MOD else: if forbidden_k_map[vec_number] == vec_count: continue new_vector[l] += (mat[l] * vector[vec_state]) % MOD new_vector[l] %= MOD # matrix1 mat = matrix[1] for vec_state in range(state_count): vec_number, vec_count = state_list[vec_state] for l in range(state_count): l_number, l_count = state_list[l] if vec_number == l_number: new_count = min(vec_number + 1, l_count + vec_count) if forbidden_k_map[vec_number] == new_count: continue for r in range(state_count): new_vector[r] += (mat[l][r] * vector[vec_state]) % MOD new_vector[r] %= MOD else: if forbidden_k_map[vec_number] == vec_count: continue if forbidden_k_map[l_number] == l_count: continue for r in range(state_count): new_vector[r] += (mat[l][r] * vector[vec_state]) % MOD new_vector[r] %= MOD return new_vector # 1つ目の要素 matrix = [ [0 for _ in range(state_count)], [[0 for _ in range(state_count)] for _ in range(state_count)] ] for i in range(1, N + 1): matrix[0][state_map[(i, 1)]] = 1 vector = None while L > 0: if L % 2 == 1: if vector is None: new_vector = [0 for _ in range(state_count)] mat = matrix[0] for l in range(state_count): new_vector[l] += mat[l] new_vector[l] %= MOD mat = matrix[1] for l in range(state_count): l_number, l_count = state_list[l] if forbidden_k_map[l_number] != l_count: for r in range(state_count): new_vector[r] += mat[l][r] new_vector[r] %= MOD vector = new_vector else: vector = prod_vec(matrix, vector) matrix = prod(matrix, matrix) L //= 2 answer = 0 for l in range(state_count): l_number, l_count = state_list[l] if forbidden_k_map[l_number] == l_count: continue answer += vector[l] answer %= MOD ans = pow(N, L0, MOD) ans -= answer ans %= MOD print(ans) if __name__ == "__main__": main()