ABC372F WA

#include <assert.h>
#include <bits/stdc++.h>
using namespace std;
#ifndef __DEBUG__
#define dbg(...) 42
#endif
template <class T>
using mpq = priority_queue<T, vector<T>, greater<T>>;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vi = vector<int>;

int main(int argc, char** argv)
{
    ll n, m, k;
    cin >> n >> m >> k;
    using a2l = array<ll, 2>;
    vl ns { 1 };
    vector<a2l> sc(m);
    for (auto& v : sc)
        cin >> v[0] >> v[1], ns.push_back(v[0]), ns.push_back(v[1]);

    sort(ns.begin(), ns.end());
    ns.erase(std::unique(ns.begin(), ns.end()), ns.end());
    ll sz = ns.size();
    if (sz == 1) {
        cout << 1 << '\n';
        return 0;
    }

    vector<vector<a2l>> g(sz);
    for (auto& short_cut : sc) {
        ll u = lower_bound(ns.begin(), ns.end(), short_cut[0]) - ns.begin(),
           v = lower_bound(ns.begin(), ns.end(), short_cut[1]) - ns.begin();
        // u -> v
        if (v - u != 1)
            g[u].push_back({ v, 1 });
    }
    for (ll i = 0; i < sz; ++i) {
        ll u = i, v = (i + 1) % sz;
        g[u].push_back({ v, (ns[v] - ns[u] + n) % n });
    }
    dbg(g);

    vector<vl> cache(sz, vl(k + 1, -1));

    constexpr ll mod = 998244353;
    auto search = [&](auto&& self, ll u, ll remk) {
        if (cache[u][remk] != -1)
            return cache[u][remk];

        ll ret = 0;
        for (auto [v, w] : g[u]) {
            if (w >= remk)
                ret = (ret + 1) % mod;
            else
                ret = (ret + self(self, v, remk - w)) % mod;
        }
        return cache[u][remk] = ret;
    };

    cout << search(search, 0, k) << '\n';
    ll ans = 0;
    vector<vl> cnt(sz, vl(k + 1));
    auto search2 = [&](ll u, ll remk) -> void {
        priority_queue<a2l> pq;
        pq.push({ remk, u });
        cnt[u][remk] += 1;
        while (!pq.empty()) {
            auto [rk, u] = pq.top();
            pq.pop();
            for (auto [v, w] : g[u]) {
                if (rk <= w) {
                    ans = (ans + cnt[u][rk]) % mod;
                } else {
                    if (cnt[v][rk - w] == 0)
                        pq.push({ rk - w, v });
                    cnt[v][rk - w] = (cnt[v][rk - w] + cnt[u][rk]) % mod;
                }
            }
        }
    };
    // search2(0, k);
    // cout << ans << '\n';
    return 0;
};