Consider the following DP (Dynamic Programming): \(\mathrm{dp}[i][j]=\) the number of ways to make \(i\) moves ending up at vertex \(j\).

Take the following case as an example: \(N=8,M=2,(X_1,Y_1)=(3,7)\), and \((X_2,Y_2)=(4,3)\). The transitions are illustrated as follows (where edges \(1\) through \(7\) are painted red, and \(8\) through \(10\) in blue):

Shift the lower row a bit to the left:

Now many vertices \(v\ (\geq 2)\) satisfy \(dp[i+1][v]=dp[i][v-1]\). That is, \(\mathrm{dp}[i]\) and \(\mathrm{dp}[i+1]\) are almost the same by applying left shift.

Using this property, one can reuse the DP array instead of creating for each \(i\) to reduce the complexity. \(\mathrm{dp}[i]\) and (left-shifted) \(\mathrm{dp}[i+1]\) differ only at \(O(M)\) points, so the complexity is \(O(N+MK)\).

The DP technique like this, where arrays are reused while only necessary elements are updated, is called inline DP.

In the following sample code, we first reserve memory of size \((N+K)\), corresponding \(\mathrm{dp}[i]\) with \((K-i)\)- through \((K-i+(N-1))\)-th elements.

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)