#include <stdio.h>
#include <bits/stdc++.h>

using namespace std;

const int L = 64, N = 1e6 + 10;
const long long M = 1e9 + 7;

int n, m;
long long k;
int fr;
vector <pair <int, int> > req;
vector <long long> fact;
vector <pair <int, int> > near;
vector <int> var;
vector <int> cis;
vector <int> ciss;
int ans;

long long pw(long long a, long long n) {
    if (n == 0)
        return 1;
    if (n % 2 == 1)
        return (a * pw(a, n - 1)) % M;
    long long temp = pw(a, (n >> 1));
    return (temp * temp) % M;
}

long long C(long long n, long long k) {
    long long ans = fact[n];
    ans = (ans * pw(fact[k], M - 2)) % M;
    ans = (ans * pw(fact[n - k], M - 2)) % M;
    return ans;
}

void count_facts() {
    fact.assign(N, 1);
    for (int i = 1; i < N; i++)
        fact[i] = (fact[i - 1] * i) % M;
}

void req_norm() {
    sort(req.begin(), req.end(), [](pair <int, int> l, pair <int, int> r) {
            if (l.first != r.first)
                return l.first < r.first;
            return l.second > r.second;
         });


    auto _req = req;
    req.clear();
    vector <int> temp(m + 1, 1e9);

    for (int i = m - 1; i >= 0; i--)
        temp[i] = min(temp[i + 1], _req[i].second);

    for (int i = 0; i < m; i++)
        if (_req[i].second < temp[i + 1])
            req.push_back(_req[i]);

    m = req.size();
}

void count_near() {
    vector <pair <int, int> > rreq;
    for (auto e: req)
        rreq.push_back(make_pair(e.second, e.first));

    for (int i = 0; i < n - 1; i++) {
        near.push_back(make_pair(-1, -1));

        int from = upper_bound(rreq.begin(), rreq.end(), make_pair(i, (int)1e9))
            - rreq.begin();
        int to = upper_bound(req.begin(), req.end(), make_pair(i, (int)1e9)) -
            req.begin() - 1;

        if (from == -1 || to == -1 || from >= m || to >= m)
            continue;
        if (i < req[from].first || i >= req[from].second ||
            i < req[to].first || i >= req[to].second)
                continue;
        fr++;

        near[i] = make_pair(from, to);
    }
    fr = n - 1 - fr;
}

void dp() {
    vector <vector <int> > d(m + 1, vector <int>(L, 0));
    vector <vector <int> > psum(1, vector <int>(L, 0));

    for (int i = 0; i <= min(L - 1, fr); i++)
        d[0][i] = psum[0][i] = C(fr, i);

    for (int i = 0; i < n - 1; i++) {
        int from, to;
        tie(from, to) = near[i];

        if (from == -1)
            continue;

        if (to + 1 == (int)psum.size())
            psum.push_back(psum.back());

        for (int j = L - 1; j >= 1; j--) {
            int addo = psum[to + 1][j - 1];
            if (from > 0)
                addo = (addo + M - psum[from - 1][j - 1]) % M;
            d[to + 1][j] = (d[to + 1][j] + addo) % M;
            psum[to + 1][j] = (psum[to + 1][j] + addo) % M;
        }
    }

    /* for (auto x: d) {
        for (int y: x)
            cout << y << ' ';
        cout << endl;
    } */

    var = d[m];

    /* for (int x: var)
        cout << x << ' ';
    cout << '\n'; */
}

void dp1() {
    bitset <L> k2(k);
    vector <vector <vector <int> > > d;
    d.assign(2, vector <vector <int> >(L, vector <int>(L + 1, 0)));

    d[1][L - 1][0] = 1;

    for (int i = L - 2; i >= 0; i--) {

        for (int used = 0; used < L; used++) {
            if (k2[i]) {
                d[1][i][used + 1] = (d[1][i][used + 1] + d[1][i + 1][used]) % M;
                d[0][i][used] = (d[0][i][used] + d[1][i + 1][used]) % M;
            }
            else
                d[1][i][used] = (d[1][i][used] + d[1][i + 1][used]) % M;

            d[0][i][used] = (d[0][i][used] + d[0][i + 1][used]) % M;
            d[0][i][used + 1] = (d[0][i][used + 1] + d[0][i + 1][used]) % M;
        }

    }

    cis.assign(L, 0);
    for (int i = 0; i < L; i++)
        cis[i] = (d[1][0][i] + d[0][0][i]) % M;

    /* for (int x: cis)
        cout << x << ' ';
    cout << '\n'; */
}

void count_ciss() {
    ciss.assign(L, 0);
    for (int fi = 0; fi < L; fi++) {
        for (int st = 0; st <= fi; st++) {
            int cb = fi - st;

            long long v = cis[fi];
            v = (v * C(fi, cb)) % M;

            ciss[cb] = (ciss[cb] + v) % M;
        }
    }

    /* for (int x: ciss)
        cout << x << ' ';
    cout << '\n'; */
}

int dp2(int a, int b) {
    vector <vector <int> > d(a + 2, vector <int>(b + 2, 0));
    d[0][0] = 1;

    for (int i = 0; i <= a; i++) {
        for (int j = 0; j <= b; j++) {
            d[i + 1][j + 1] = (d[i + 1][j + 1] + d[i][j]) % M;
            if (j > 0)
                d[i + 1][j] = (1ll * d[i][j] * j + d[i + 1][j]) % M;
        }
    }

    return d[a][b];
}

int main() {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    ios_base::sync_with_stdio(false);

    count_facts();

    cin >> n >> m >> k;
    for (int i = 0; i < m; i++) {
        int from, to;
        cin >> from >> to;
        from--; to--;
        req.push_back(make_pair(from, to));
    }

    req_norm();
    count_near();
    dp();
    dp1();
    count_ciss();

    for (int cb = 0; cb < L; cb++) {
        for (int up = 0; up <= cb; up++) {
            long long v = dp2(cb, up);
            v = (v * fact[up]) % M;
            v = (v * ciss[cb]) % M;
            v = (v * var[up]) % M;

            ans = (ans + v) % M;
        }
    }

    cout << ans;

    return 0;
}