グラフを縮約することで解くことができます．入次数および出次数が \(1\) である頂点を縮約することで，\(O(M)\) 頂点 \(O(M)\) 辺の重み付き有向グラフを作ります．このグラフ上で，「\(\mathrm{dp}[i][j]=\) \(i\) 回の移動で頂点 \(j\) にいる移動方法の数」という dp を考えると，状態数が \(O(MK)\) となって間に合います．縮約辺の途中で移動が終わる場合や，縮約したグラフに頂点 \(1\) が含まれない場合，\(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)