Machine learning

In the laboratory of artificial intelligence one have developed a new method of machine learning. In the process of learning the program uses n iterations. Each iteration consists in the fact that the learning program is launched on some training set.

There were prepared training sets of difficulty from 0 to k. The learning plan is defined by an array of integers [a[1], a[2], ..., a[n]], where a[i] gives the complexity of the set used on the i-th learning iteration. For all i from 1 to n inequality 0 ≤ a[i] ≤ k must be fulfilled.

It turned out that the effectiveness of training plan depends on bit representations of the training sets complexity. In order for the plan to be effective, it is necessary that for any two values ​​i and j, where 1 ≤ i < j ≤ n, the equation (a[i] and a[j]) = a[i] takes place. Recall that the bitwise "and" (and) of two non-negative integers are arranged as follows: we write both numbers in the binary number system, i-th binary bit of the result equals to 1 in both arguments it is 1. For example, (14 and 7) = (1110[2] and 0111[2]) = 110[2] = 6. This operation is implemented in all modern programming languages, in C++, Java and Python languages ​​it is written as "&", in Pascal as "and".

However, the constant use of sets of the same complexity does not make progress in learning. To avoid this, the following m requirements must be satisfied for the training plan. Each requirement is given by two numbers l[i] and r[i] and means that a[li] ≠ a[ri]. Laboratory staff wants to find a number of effective plans that meet all the requirements. Since this number can be very large, you need to find the remainder of the division by 10^9 + 7.

Write a program that, by given integers n and k, as well as m requirements like l[i], r[i] determines the number of effective plans that satisfy all requirements, and prints the remainder of dividing this amount by the number 10^9 + 7.

Input

First line contains three integers n, m and k (1 ≤ n ≤ 3 * 10^5, 0 ≤ m ≤ 3 * 10^5, 0 ≤ k ≤ 10^18) - the number of training iterations, the number of requirements and the maximum complexity of the training set.

The following m lines describe the requirements, i-th line contains two integers l[i], r[i], which means that a[li] ≠ a[ ri] (1 ≤ l[i] < r[i] ≤ n). It is guaranteed that all requirements are different.

Output

Print a single integer - the remainder of dividing the number of effective plans satisfying all requirements, by the number 10^9 + 7.

Examples

Note

All possible plans for the first test: [0, 0], [0, 1], [0, 2], [0, 3], [1, 1], [1, 3], [2, 2], [2, 3], [3, 3].

For the second test case: [0, 1, 1], [0, 2, 2].