Lantern Sparks

Pondo has strung $n$ lanterns together with $m$ wires. Lantern $i$ independently chooses an integer brightness uniformly at random from the inclusive interval $[l_i, r_i]$.

A wire connecting lanterns $u$ and $v$ produces a spark if at least one of the two brightnesses is divisible by a fixed integer $p$. Let $X$ be the number of wires that spark.

Output the expected value of $X$.

It can be shown that the answer can be expressed as a rational number $P/Q$ in lowest terms with $Q$ coprime to $10^9 + 7$. Output $P \cdot Q^{-1} \bmod (10^9 + 7)$.

Input

The first line contains three integers $n$, $m$, and $p$.

Each of the next $n$ lines contains two integers $l_i$ and $r_i$.

Each of the next $m$ lines contains two integers $u$ and $v$, describing a wire between lanterns $u$ and $v$.

Lanterns are numbered $1$ through $n$. The wires form an undirected graph. There are no self-loops, but multiple wires between the same pair of lanterns are allowed; each wire is counted separately.

Output

Print a single integer: the expected number of sparks modulo $10^9 + 7$.

Constraints

• $1 \le n \le 10^5$
• $0 \le m \le 10^5$
• $1 \le p \le 10^9$
• $1 \le l_i \le r_i \le 10^9$
• $1 \le u, v \le n$
• $u \ne v$

Example 1

3 3 2
1 2
3 4
5 6
1 2
2 3
3 1

250000004

Explanation

Each lantern has brightness even with probability $1/2$. A wire sparks unless both endpoints are odd, which happens with probability $1/4$, so each wire sparks with probability $3/4$. The three wires contribute $9/4$ in expectation, and $9 \cdot 4^{-1} \equiv 250000004 \pmod{10^9 + 7}$.

The three spark events are dependent because they share lanterns, but the expectation of the sum is still the sum of the expectations.

Example 2

2 1 3
1 3
1 2
1 2

333333336

Explanation

Lantern $1$ fails to be divisible by $3$ with probability $2/3$, and lantern $2$ never chooses a multiple of $3$. The single wire therefore sparks with probability $1/3$.

Example 3

1 0 1
1 1

0

Explanation

There are no wires, so the expected number of sparks is $0$.