AC*19

WA*34

#include <bits/stdc++.h>
#define int long long
#define mkp(a, b) make_pair(a, b)
using namespace std;
using LL = long long;
using ULL = unsigned long long;
const int N = 4e5 + 10, M = 2e2 + 10, Mod = 998244353;
int n, m, k;
int h[N], e[N], ne[N], idx, nxt[N], id;
bool is[N];
int f[N][M], ans;
bool inq[N][M];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
void add_edge(int u, int v) {
    e[idx] = v, ne[idx] = h[u], h[u] = idx ++;
}
void add(int &x, int y) {
    x += y;
    if(x >= Mod) x -= Mod;
}
int calc(int u, int v) {
    if(u > v) return n - u + v;
    return v - u;
}
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    memset(h, -1, sizeof h);
    cin >> n >> m >> k;
    if(!m) return cout << "1\n", 0;
    for(int i = 1, u, v; i <= m; i ++) {
        cin >> u >> v;
        add_edge(u, v);
        is[u] = is[v] = true;
    }
    for(; id <= n && !is[id]; id ++);
    int i = id;
    for(int j = i + 1; i <= n;) {
        while(j <= n && !is[j]) j ++;
        if(j > n) break;
        for(; i < j; i ++) nxt[i] = j;
        i = j ++;
    }
    for(; i <= n; i ++) nxt[i] = id;
    for(i = 1; i < id; i ++) nxt[i] = id;
    q.push(mkp(0, 1)), inq[0][1] = true, f[0][1] = 1;
    while(q.size()) {
        auto [t, u] = q.top(); q.pop();
        // cout << "t = " << t << " u = " << u << " f[t][u] = " << f[t][u] << '\n';
        // 走环
        if(t == k) {
            add(ans, f[t][u]);
            continue;
        }
        if(t + calc(u, nxt[u]) >= k) {
            // cout << "ans changed when t = " << t << " , u = " << u << " and f[t][u] = " << f[t][u] << '\n';
            add(ans, f[t][u]);
            // continue;
        }
        else {
            // cout << "update from : " << u << " to : " << nxt[u] << '\n';
            add(f[t + calc(u, nxt[u])][nxt[u]], f[t][u]);
            if(!inq[t + calc(u, nxt[u])][nxt[u]]) {
                inq[t + calc(u, nxt[u])][nxt[u]] = true;
                q.push(mkp(t + calc(u, nxt[u]), nxt[u]));
            }
        }
        for(int i = h[u]; ~i; i = ne[i]) {
            int j = e[i];
            add(f[t + 1][j], f[t][u]);
            // cout << "circle from : " << u << " to : " << j << '\n';
            if(!inq[t + 1][j]) {
                inq[t + 1][j] = true;
                q.push(mkp(t + 1, j));
            }
        }
    }
    cout << ans << '\n';
    return 0;
}
/*

*/