Machine Learning

An artificial intelligence lab developed a new machine learning method. Training uses $n$ iterations. In each iteration, the training program runs on one training set.

Training sets with complexity from 0 to $k$ are prepared. A training plan is an array $[a_1, a_2, \ldots, a_n]$, where $a_i$ is the complexity of the set used in iteration $i$. For every $i$ from 1 to $n$, it must hold that $0 \le a_i \le k$.

The effectiveness of a plan depends on the binary representations of the complexities. A plan is effective if, for any two indices $i$ and $j$ with $1 \le i < j \le n$, it holds that $(a_i \,\&\, a_j) = a_i$, where $\&$ is the bitwise AND. For example, $(14 \,\&\, 7) = (1110_2 \,\&\, 0111_2) = 110_2 = 6$.

Using sets of the same complexity over and over does not make progress. So there are $m$ requirements. Each requirement gives two numbers $l_i$ and $r_i$ and means $a_{l_i} \ne a_{r_i}$.

Count the effective plans that satisfy all requirements. Output the count modulo $10^9 + 7$.

The first line contains three integers $n$, $m$, and $k$ ($1 \le n \le 3 \cdot 10^5$, $0 \le m \le 3 \cdot 10^5$, $0 \le k \le 10^{18}$), the number of iterations, the number of requirements, and the maximum complexity.

Each of the next $m$ lines contains two integers $l_i$ and $r_i$ ($1 \le l_i < r_i \le n$). All requirements are distinct.

Print one integer, the number of effective plans that satisfy all requirements, modulo $10^9 + 7$.