import java.io.BufferedReader; import java.io.IOException; import java.io.InputStream; import java.io.InputStreamReader; import java.io.OutputStream; import java.io.PrintWriter; import java.math.BigDecimal; import java.text.DecimalFormat; import java.util.AbstractMap; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Arrays; import java.util.Comparator; import java.util.Deque; import java.util.HashMap; import java.util.HashSet; import java.util.List; import java.util.Map; import java.util.Queue; import java.util.Set; import java.util.TreeMap; import java.util.TreeSet; import static java.util.Comparator.*; public class Main { public static void main(String[] args) { InputStream inputStream = System.in; OutputStream outputStream = System.out; MyInput in = new MyInput(inputStream); PrintWriter out = new PrintWriter(outputStream); Solver solver = new Solver(); solver.solve(1, in, out); out.close(); } // ====================================================================== // 1階からN階まで、エレベータを使って、K回で移動する 通りの数を計算する // 配るDP(普通 → これでは間に合わない) static class Solver { int MOD = 1000000007; long[][] dp; public void solve(int testNumber, MyInput in, PrintWriter out) { int N = in.nextInt(); // 最上階(ゴール) int M = in.nextInt(); // エレベータの数 int K = in.nextInt(); // 移動回数 int[] L = new int[M]; // エレベータの止まる階 ここから int[] R = new int[M]; // エレベータの止まる階 ここまで for(int i=0; i < M; i++) { L[i] = in.nextInt(); R[i] = in.nextInt(); } dp = new long[K+1][N+1]; // 移動数、現在の階数 → スタートからここまでの通りの数 long wk, wk2; long[] wa = new long[N+1]; // 累積和の計算用 dp[0][1] = 1; // 初期値(移動回数0の1階は 1) for(int i=0; i < K; i++) { // 移動回数 // 止まる階数の通りの数の 累積和を計算する Arrays.fill(wa, 0); for(int x=1; x < N+1; x++) { wa[x] += wa[x-1] + dp[i][x]; // wa[x] %= MOD; // out.println(" wa[" + x + "] = " + wa[x] + " <-- dp[" + i + "][" + x + "] = " + dp[i][x]); } for(int j=0; j < M; j++) { // エレベータ数 // wk2 = 0; // for(int k=L[j]; k <= R[j]; k++) { // エレベータの止まる階数分 // wk2 += dp[i][k]; // 一台分のスタートからここまでの通りの数の合計 // wk2 %= MOD; // } wk = wa[R[j]] - wa[L[j]-1]; wk %= MOD; // if(wk2 != wk) // out.println(" 不一致 元 = " + wk2 + " 累積和 = " + wk + " L[" + j + "] = " + L[j] + " R[" + j + "] = " + R[j]); for(int k=L[j]; k <= R[j]; k++) { // エレベータの止まる階数分 dp[i+1][k] += wk; // 通りの数の合計を 止まる階 全部に足す dp[i+1][k] %= MOD; } } } out.println(dp[K][N]); // K回移動して、N階につく スタートからの通りの数 } } static class PPP { public int key, val; public PPP(int key, int val) { this.key = key; this.val = val; } public int getKey() { return key; } public void setKey(int key) { this.key = key; } public int getVal() { return val; } public void setVal(int val) { this.val = val; } } // ====================================================================== static class Pair extends AbstractMap.SimpleEntry { /** serialVersionUID. */ private static final long serialVersionUID = 6411527075103472113L; public Pair(final K key, final V value) { super(key, value); } } static class MyInput { private final BufferedReader in; private static int pos; private static int readLen; private static final char[] buffer = new char[1024 * 8]; private static char[] str = new char[500 * 8 * 2]; private static boolean[] isDigit = new boolean[256]; private static boolean[] isSpace = new boolean[256]; private static boolean[] isLineSep = new boolean[256]; static { for (int i = 0; i < 10; i++) { isDigit['0' + i] = true; } isDigit['-'] = true; isSpace[' '] = isSpace['\r'] = isSpace['\n'] = isSpace['\t'] = true; isLineSep['\r'] = isLineSep['\n'] = true; } public MyInput(InputStream is) { in = new BufferedReader(new InputStreamReader(is)); } public int read() { if (pos >= readLen) { pos = 0; try { readLen = in.read(buffer); } catch (IOException e) { throw new RuntimeException(); } if (readLen <= 0) { throw new MyInput.EndOfFileRuntimeException(); } } return buffer[pos++]; } public int nextInt() { int len = 0; str[len++] = nextChar(); len = reads(len, isSpace); int i = 0; int ret = 0; if (str[0] == '-') { i = 1; } for (; i < len; i++) ret = ret * 10 + str[i] - '0'; if (str[0] == '-') { ret = -ret; } return ret; } public long nextLong() { int len = 0; str[len++] = nextChar(); len = reads(len, isSpace); int i = 0; long ret = 0L; if (str[0] == '-') { i = 1; } for (; i < len; i++) ret = ret * 10 + str[i] - '0'; if (str[0] == '-') { ret = -ret; } return ret; } public String nextString() { String ret = new String(nextDChar()).trim(); return ret; } public char[] nextDChar() { int len = 0; len = reads(len, isSpace); char[] ret = new char[len + 1]; for (int i=0; i < len; i++) ret[i] = str[i]; ret[len] = 0x00; return ret; } public char nextChar() { while (true) { final int c = read(); if (!isSpace[c]) { return (char) c; } } } int reads(int len, boolean[] accept) { try { while (true) { final int c = read(); if (accept[c]) { break; } if (str.length == len) { char[] rep = new char[str.length * 3 / 2]; System.arraycopy(str, 0, rep, 0, str.length); str = rep; } str[len++] = (char) c; } } catch (MyInput.EndOfFileRuntimeException e) { } return len; } static class EndOfFileRuntimeException extends RuntimeException { } } }