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

Input

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

Output

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

Input

2 1 3
1 3
1 2
1 2

Output

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

Input

1 0 1
1 1

Output

0

Explanation

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