import std.stdio, std.string, std.conv; import std.range, std.algorithm, std.array, std.typecons, std.container; import std.math, std.numeric, core.bitop; enum inf3 = 1_001_001_001; enum inf6 = 1_001_001_001_001_001_001L; enum mod = 1_000_000_007L; void main() { int n, m, k; scan(n, m, k); auto L = new int[](m); auto R = new int[](m); iota(m).each!(i => scan(L[i], R[i])); L[] -= 1; auto cur = new long[](n + 1); cur[1 .. $] = 1; foreach (i ; 0 .. k) { auto nex = new long[](n + 1); foreach (j ; 0 .. m) { auto a = rngsum(cur, L[j], R[j]); nex[L[j]] += a; nex[L[j]] %= mod; nex[R[j]] += mod - a; nex[R[j]] %= mod; } foreach (j ; 1 .. n + 1) { nex[j] += nex[j - 1]; nex[j] %= mod; } debug { writeln(nex); } cur = new long[](n + 1); foreach (j ; 1 .. n + 1) { cur[j] = cur[j - 1] + nex[j - 1]; cur[j] %= mod; } } auto ans = (cur[n] - cur[n - 1] + mod) % mod; writeln(ans); } long rngsum(long[] cur, int L, int R) { return (cur[R] - cur[L] + mod) % mod; } struct FenwickTree(T) { private { int _size; T[] _data; } this(int N) { _size = N; _data = new T[](_size + 1); } void add(int i, T x) { if (x < 0) { x += mod; } i++; while (i <= _size) { _data[i] += x; if (_data[i] >= mod) _data[i] -= mod; i += i & (-i); } } T psum(int r) { T res = 0; while (r > 0) { res += _data[r]; if (res >= mod) res -= mod; r -= r & (-r); } return res; } T sum(int l, int r) { return (psum(r) - psum(l) + mod) % mod; } } int[][] readGraph(int n, int m, bool isUndirected = true, bool is1indexed = true) { auto adj = new int[][](n, 0); foreach (i; 0 .. m) { int u, v; scan(u, v); if (is1indexed) { u--, v--; } adj[u] ~= v; if (isUndirected) { adj[v] ~= u; } } return adj; } alias Edge = Tuple!(int, "to", int, "cost"); Edge[][] readWeightedGraph(int n, int m, bool isUndirected = true, bool is1indexed = true) { auto adj = new Edge[][](n, 0); foreach (i; 0 .. m) { int u, v, c; scan(u, v, c); if (is1indexed) { u--, v--; } adj[u] ~= Edge(v, c); if (isUndirected) { adj[v] ~= Edge(u, c); } } return adj; } void yes(bool b) { writeln(b ? "Yes" : "No"); } void YES(bool b) { writeln(b ? "YES" : "NO"); } T[] readArr(T)() { return readln.split.to!(T[]); } T[] readArrByLines(T)(int n) { return iota(n).map!(i => readln.chomp.to!T).array; } void scan(T...)(ref T args) { import std.stdio : readln; import std.algorithm : splitter; import std.conv : to; import std.range.primitives; auto line = readln().splitter(); foreach (ref arg; args) { arg = line.front.to!(typeof(arg)); line.popFront(); } assert(line.empty); } void fillAll(R, T)(ref R arr, T value) { static if (is(typeof(arr[] = value))) { arr[] = value; } else { foreach (ref e; arr) { fillAll(e, value); } } } bool chmin(T, U...)(ref T x, U args) { bool isChanged; foreach (arg; args) { if (x > arg) { x = arg; isChanged = true; } } return isChanged; } bool chmax(T, U...)(ref T x, U args) { bool isChanged; foreach (arg; args) { if (x < arg) { x = arg; isChanged = true; } } return isChanged; }