Problem Statement

Penguinman runs a market.

For this market, the following $4$ things have been decided at this point.

• $N$ customers will come.
• $M$ items will be sold. Each item has a fixed price and value: the price of the $i$-th item is $A_i$ yen and its value is $B_i$. It is guaranteed that $B_i≠B_j$ if $i≠j$.
• Every customer brings an amount of money of their choice (an integer) between $0$ yen and $K$ yen, inclusive, with equal probability.
• A customer buys exactly $1$ item: the one with the highest value among those affordable with the money they brought. A purchased item disappears from the market at that moment. If there is nothing they can buy, the customer gives up on shopping and goes home. Under the constraints of this problem, the item to buy is uniquely determined.

Your job, as Penguinman's subordinate, is to find the expected value of the sum of the values of the items bought by the customers.

It is guaranteed that this expected value can be expressed as $P/Q$ using $2$ positive integers $P,Q$. Find and print the integer $R$ between $0$ and $10^9+6$, inclusive, such that $R×Q≡P(\bmod 10^9+7)$.

Input

$N\ M\ K$
$A_1\ B_1$
$A_2\ B_2$
$︙$
$A_M\ B_M$

• $1≤N,M≤40$
• $1≤K≤10^9$
• $1≤A_i≤K$
• $1≤B_i≤10^9$
• $B_i≠B_j$ if $i≠j$
• All input values are integers.

Output

Print a newline at the end.

Sample

2 1 2
1 1

888888896

10 3 100
2 4
5 100
1 101

974312872

40 6 1000000
400 100
20 1
1030 11
593 103
194029 103948
20 9183

621015348