module Main;

import BinaryHeap;
import BoolArray;
import CPLib.Arithmetic;
import CPLib.DSegtree;
import CPLib.Graph;
import CPLib.IO;
import CPLib.LSegtree;
import CPLib.Monoid;
import CPLib.UnionFind;
import CPLib.ZP;
import HashMap;
import HashSet;

type Z = ZP P1000000007;

// type Event = union {
//     enter : (I64, Z),
//     leave : (I64, Z)
// };
// 
// pos : Event -> I64 = |e| match e {
//     enter(i) => i,
//     leave(i) => i
// };

main : IO () = (
    let cN = *read_i; // 回数
    let cM = *read_i; // エレベータの数
    let cK = *read_i; // 移動回数
    let cLRs = *range(0, cM).fold_m([], |_, cLRs|
        let l = *read_i;
        let r = *read_i;
        let l = l - 1;
        cLRs.push_back((l, r)).pure
    );
    let t = Array::fill(cN, zp(0) : Z);
    let t = t[0].iset(zp(1));
    let t = range(0, cK).fold(t, |k, t|
        let acm = range(0, cN).fold([zp(0)], |n, acm|
            let v = acm.@(acm.@size - 1);
            acm.push_back(v + t.@(n))
        );
        let s = Array::fill(cN, zp(0));
        let s = cLRs.to_iter.fold(s, |(l, r), s|
            let sum = acm.@(r) - acm.@(l);
            let s = if 0 <= l && l < s.@size { s[l].imod(add(sum)) } else { s };
            let s = if 0 <= r && r < s.@size { s[r].imod(add(-sum)) } else { s };
            s
        );
        let s = range(1, cN).fold(s, |n, s|
            let v = s[n-1].iget;
            s[n].imod(add(v))
        );
        s
    );
    let ans = t.@(cN-1);
    ans.@value.to_string.println
);