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 [a1, a2, ..., an], where ai gives the complexity of the set used on the i-th learning iteration. For all i from 1 to n inequality 0 ≤ ai ≤ 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 (ai and aj) = ai 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) = (11102 and 01112) = 1102 = 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 li and ri and means that ali ≠ ari. 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 109 + 7.

Write a program that, by given integers n and k, as well as m requirements like li, ri determines the number of effective plans that satisfy all requirements, and prints the remainder of dividing this amount by the number 109 + 7.

Input

First line contains three integers n, m and k (1 ≤ n ≤ 3 * 105, 0 ≤ m ≤ 3 * 105, 0 ≤ k ≤ 1018) - 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 li, ri, which means that ali ≠ ari (1 ≤ li < ri ≤ 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 109 + 7.

Explanation

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].