The problem can be solved by contracting the graph. By contracting vertices whose in- and out-degrees are \(1\), one can construct a directed graph with \(O(M)\) vertices and \(O(M)\) edges. On this graph, one can define a DP (Dynamic Programming) where \(\mathrm{dp}[i][j]=\) the number of ways to make \(i\) moves, ending up at vertex \(j\). The number of states is \(O(MK)\), small enough to complete within the time limit. Beware of cases where travel ends in the midst of an edge, the contracted graph does not contain vertex \(1\), or \(M = 0\).

n, m, k = map(int, input().split())
if m == 0:
    print(1)
    exit()
edges = []
s = set([0])
for i in range(m):
    x, y = map(lambda x: int(x) - 1, input().split())
    s.add(x)
    s.add(y)
    edges.append((x, y))

s = sorted(list(s))
d = {}
sz = len(s)
for i in range(sz):
    d[s[i]] = i
edge = [[] for i in range(sz)]
for i in range(sz):
    edge[i].append(((i + 1) % sz, (s[(i + 1) % sz] - s[i]) % n))
for x, y in edges:
    edge[d[x]].append((d[y], 1))

mod = 998244353
dp = [[0] * sz for i in range(k)]
dp[0][0] = 1
ans = 0
for i in range(k):
    for v in range(sz):
        for to, w in edge[v]:
            if i + w >= k:
                ans += dp[i][v]
                ans %= mod
            else:
                dp[i + w][to] += dp[i][v]
                dp[i + w][to] %= mod

print(ans)