#include <iostream>
#include <cstdio>

using namespace std;

typedef long long LL;

const int N = 305, MOD = 1000000007;

int n, m, k, diff[N][N];

struct Matrix {
    int v[N][N];
    Matrix operator*(Matrix o) {
        Matrix ret = {};
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                for (int l = 1; l <= n; ++l) {
                    ret.v[i][l] = (ret.v[i][l] + 1LL * v[i][j] * o.v[j][l]) % MOD;
                }
            }
        }
        return ret;
    }
    Matrix operator*=(Matrix o) {
        *this = *this * o;
        return *this;
    }
};
Matrix a;

Matrix QMI(Matrix base, int p) {
    Matrix ret = {};
    for (int i = 1; i <= n; ++i) ret.v[i][i] = 1;
    while (p) {
        if (p & 1) ret *= base;
        base *= base;
        p >>= 1;
    }
    return ret;
}

int main() {
    scanf("%d%d%d", &n, &m, &k);

    for (int i = 1, l, r; i <= m; ++i) {
        scanf("%d%d", &l, &r);
        diff[l][l]++;
        diff[l][r + 1]--;
        diff[r + 1][l]--;
        diff[r + 1][r + 1]++;
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            diff[i][j] += diff[i][j - 1];
        }
    }
    for (int j = 1; j <= n; ++j) {
        for (int i = 1; i <= n; ++i) {
            diff[i][j] += diff[i - 1][j];
        }
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            a.v[i][j] = diff[i][j];
        }
    }

    a = QMI(a, k);
    printf("%d\n", a.v[n][1]);

    return 0;
}