class LazyPropSegTree:
    def __init__(self, op, e, mapping, composition, id_, v=[]):
        assert (len(v) >= 0)
        self.n = len(v)
        self.log = (self.n - 1).bit_length()
        self.size = 1 << self.log
        self.d = [e for _ in range(2*self.size)]
        self.lz = [id_ for _ in range(self.size)]
        self.op = op
        self.e = e
        self.mapping = mapping
        self.composition = composition
        self.id_ = id_

        for i in range(self.n):
            self.d[self.size + i] = v[i]
        for i in range(self.size - 1, 0, -1):
            self.update(i)

    def update(self, k):
        self.d[k] = self.op(self.d[2*k], self.d[2*k+1])
    
    def all_apply(self, k, f):
        self.d[k] = self.mapping(f, self.d[k])
        if k < self.size:
            self.lz[k] = self.composition(f, self.lz[k])

    def push(self, k):
        self.all_apply(2*k, self.lz[k])
        self.all_apply(2*k+1, self.lz[k])
        self.lz[k] = self.id_

    def set(self, p, x):
        assert (0 <= p) and (p < self.n)
        p += self.size
        for i in range(self.log, 0, -1):
            self.push(p >> i)
        self.d[p] = x
        for i in range(1, self.log + 1):
            self.update(p >> i)

    def get(self, p):
        assert (0 <= p) and (p < self.n)
        p += self.size
        for i in range(self.log, 0, -1):
            self.push(p >> i)
        return self.d[p]

    def prod(self, left, right):
        assert 0<=left and left<=right and right<=self.n
        if left == right:
            return self.e
        left += self.size
        right += self.size
        for i in range(self.log, 0, -1):
            if (((left >> i) << i) != left):
                self.push(left >> i)
            if (((right >> i) << i) != right):
                self.push(right >> i)
        sml, smr = self.e, self.e
        while left < right:
            if left & 1:
                sml = self.op(sml, self.d[left])
                left += 1
            if right & 1:
                right -= 1
                smr = self.op(self.d[right], smr)
            left >>= 1
            right >>= 1
        return self.op(sml, smr)

    def all_prod(self):
        return self.d[1]

    def apply(self, p, f):
        assert (0 <= p) and (p < self.n)
        p += self.size
        for i in range(self.log, 0, -1):
            self.push(p >> i)
        self.d[p] = self.mapping(f, self.d[p])
        for i in range(1, self.log+1):
            self.update(p >> i)

    def apply_lr(self, left, right, f):
        assert 0<=left and left<=right and right<=self.n
        if left == right:
            return
        left += self.size
        right += self.size
        for i in range(self.log, 0, -1):
            if (((left >> i) << i) != left):
                self.push(left >> i)
            if (((right >> i) << i) != right):
                self.push((right - 1) >> i)
        l2, r2 = left, right
        while left < right:
            if left & 1:
                self.all_apply(left, f)
                left += 1
            if right & 1:
                right -= 1
                self.all_apply(right, f)
            left >>= 1
            right >>= 1
        left, right = l2, r2
        for i in range(1,self.log+1):
            if (((left >> i) << i) != left):
                self.update(left >> i)
            if (((right >> i) << i) != right):
                self.update((right-1) >> i)
    
    def max_right(self, left, g):
        assert (0 <= left) and (left <= self.n)
        assert g(self.e)
        if left == self.n:
            return self.n
        left += self.size
        for i in range(self.log, 0, -1):
            self.push(left >> i)
        sm = self.e
        while True:
            while(left % 2 == 0):
                left >>= 1
            if not g(self.op(sm, self.d[left])):
                while left < self.size:
                    self.push(left)
                    left <<= 1
                    if g(self.op(sm, self.d[left])):
                        sm = self.op(sm, self.d[left])
                        left += 1
                return left - self.size
            sm = self.op(sm, self.d[left])
            left += 1
            if(left & -left) == left:
                break
        return self.n

    def min_left(self, right, g):
        assert (0 <= right) and (right <= self.n)
        assert g(self.e)
        if right == 0:
            return 0
        right += self.size
        for i in range(self.log, 0, -1):
            self.push((right-1) >> i)
        sm = self.e
        while True:
            right -= 1
            while(right > 1) and (right % 2):
                right >>= 1
            if not g(self.op(self.d[right], sm)):
                while right < self.size:
                    self.push(right)
                    right = 2 * right + 1
                    if g(self.op(self.d[right], sm)):
                        sm = self.op(self.d[right], sm)
                        right -= 1
                return right + 1 - self.size
            sm = self.op(self.d[right], sm)
            if(right & -right) == right:
                break
        return 0


N, M, K = map(int, input().split())
data = [list(map(int, input().split())) for _ in range(M)]

MOD = 10**9 + 7
e = 0
def composition(p, q):
    if p is None:
        return q
    else:
        if q is None:
            return p
        else:
            return (p + q) % MOD

id_ = None
BASE = 1 << 20
def op(x, y):
    x0, x1 = divmod(x, BASE)
    y0, y1 = divmod(y, BASE)
    s0 = (x0 + y0) % MOD
    s1 = x1 + y1
    return s0*BASE + s1


def mapping(p, x):
    if p is None:
        return x
    x0, x1 = divmod(x, BASE)
    x0 = (x0 + p*x1) % MOD
    return x0*BASE + x1

v = [1] * N
v[0] += BASE
st = LazyPropSegTree(
    op=op, e=e, mapping=mapping, composition=composition, id_=id_, v=v)

for _ in range(K):
    nex = LazyPropSegTree(
        op=op, e=e, mapping=mapping, composition=composition, id_=id_,
        v=[1]*N)

    for li, ri in data:
        v = st.prod(li-1, ri)
        s, _ = divmod(v, BASE)
        nex.apply_lr(li-1, ri, s)
    
    st = nex

v = st.get(N-1)
ans, _ = divmod(v, BASE)
print(ans)