import numpy as np

N,M,T = list(map(int,input().split()))
d = [[0] * N for _ in range(N)]
P = 998244353

for _ in range(M):
    s,t = list(map(int,input().split()))
    d[s][t] = 1
    d[t][s] = 1
M = np.matrix(d)
power = [0] * 9
power[0] = M
for i in range(1,9):
    power[i] = power[i-1] ** 2 % P
def calc(n):
    ans = None
    for i in range(9):
        if n & (1 << i):
            if ans == None:
                ans = power[i]
            else:
                ans = ans * power[i] % P
    return ans

print(calc(T)[0,0])