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 evts = cLRs.to_iter.fold([], |(l, r), evts|
            let sum = acm.@(r) - acm.@(l);
            evts.push_back((l, sum)).push_back((r, -sum))
        );
        let evts = evts.sort_by(|(a, b)| a.@0 < b.@0);
        let s = Array::fill(cN, zp(0));
        let (s, _, _) = range(0, cN).fold((s, 0, zp(0)), |n, (s, ei, v)|
            // ei の position <= n なものをすべて処理
            let (ei, v) = loop((ei, v), |(ei, v)|
                if ei >= evts.@size { (ei, v).break };
                let e = evts.@(ei);
                if !(e.@0 <= n) { (ei, v).break };
                let v = v + e.@1;
                let ei = ei + 1;
                (ei, v).continue
            );
            let s = s[n].iset(v);
            (s, ei, v)
        );
        s
    );
    let ans = t.@(cN-1);
    ans.@value.to_string.println
);