MOD = 998244353 def main(): import sys input = sys.stdin.read data = input().split() idx = 0 N = int(data[idx]); idx +=1 M = int(data[idx]); idx +=1 T = int(data[idx]); idx +=1 # Initialize adjacency matrix adj = [[0]*N for _ in range(N)] for _ in range(M): s = int(data[idx]); idx +=1 t = int(data[idx]); idx +=1 adj[s][t] += 1 adj[t][s] += 1 # Function to multiply two matrices with optimization def multiply(a, b): n = len(a) result = [[0]*n for _ in range(n)] bt = list(zip(*b)) # Transpose b for i in range(n): a_row = a[i] for j in range(n): total = 0 b_col = bt[j] for k in range(n): total += a_row[k] * b_col[k] result[i][j] = total % MOD return result # Function to compute matrix exponentiation using binary exponentiation def matrix_power(mat, power): n = len(mat) result = [[0]*n for _ in range(n)] for i in range(n): result[i][i] = 1 # Identity matrix current = mat while power > 0: if power % 2 == 1: result = multiply(result, current) current = multiply(current, current) power = power // 2 return result if T == 0: print(1 % MOD) return # Compute A^T mat_T = matrix_power(adj, T) # The result is the (0,0) entry of mat_T print(mat_T[0][0] % MOD) if __name__ == "__main__": main()