「\(\mathrm{dp}[i][j]=\) \(i\) 回の移動で頂点 \(j\) にいる移動方法の数」という dp を考えます．

ここで，\(N=8,M=2,(X_1,Y_1)=(3,7),(X_2,Y_2)=(4,3)\) の場合の遷移の様子を図示してみます．（辺 \(1\) から \(7\) は赤色，辺 \(8\) から \(10\) は青色で塗っています．）

下の段を左に少しずらしてみます．

こうしてみると，多くの頂点 \(v\ (\geq 2)\) では \(\mathrm{dp}[i+1][v]=\mathrm{dp}[i][v-1]\) が成り立っています．すなわち \(\mathrm{dp}[i]\) と \(\mathrm{dp}[i+1]\) の列は，\(1\) つ左シフトすることでほとんど同じになります．

このことを利用して，dp の配列を各 \(i\) ごとに作るのではなく配列を使いまわすことで計算量を削減することができます．\(\mathrm{dp}[i]\) と（左シフトした） \(\mathrm{dp}[i+1]\) では \(O(M)\) 箇所しか違わないため，計算量は \(O(N+MK)\) になります．

このように，必要なところだけ配列を更新して使いまわす dp は inline dp と呼ばれています．

以下の実装例では，最初に \(N+K\) のメモリを確保しておき，\(\mathrm{dp}[i]\) を \(K-i\) から \(K-i+(N-1)\) 番目の要素に対応させています．

n, m, k = map(int, input().split())
xy = []
for i in range(m):
    x, y = map(lambda x: int(x) - 1, input().split())
    xy.append((x, y))

mod = 998244353
dp = [0] * (n + k)
left = k
dp[k] = 1
for _ in range(k):
    add = []
    for x, y in xy:
        add.append((y, dp[left + x]))
    left -= 1
    dp[left] = dp[left + n]
    for y, val in add:
        dp[y + left] += val
        dp[y + left] %= mod

print(sum(dp[:n]) % mod)