Hazy String

Archaeologists find an ancient string on a monument, but some characters have become hazy with the passage of time, and we only know the remain characters.

Now archaeologists want to re-build the string, and know two rules:

- there is no palindrome substring in the original string. Note that a single character is not regarded as a palindrome string here.
- the character set size of the original string is $K$.
- $0 \leq$ the character of the original string $< K$

Please calculate the number of original string which satisfy above rules.

First line contains an integer T, which indicates the number of test cases.

Every test case begins with three integers $N$, $K$ and $L$, which is the number of known characters, the character set size of the original string and the length of the original string.

Then $N$ lines follow, the $i^{th}$ line contains two integers $p_i$ and $v_i$, means the position and value of $i^{th}$ known character.

Limits
$1 \leq T \leq 100$.
$0 \leq N \leq 2000$.
$1 \leq K \leq 10^9$.
$max(1, N) \leq L \leq 10^9$.
$0 \leq p_i < p_{i+1} <L$.
$0 \leq v_i < K$
For 90\% of the use cases, $N \leq 10$ holds.

For every test case, you should output 'Case #x: y', where x indicates the case number and counts from 1 and y is the result.

Because y could be very large, just mod it with $10^9 + 7$.

3
0 3 4
1 4 4
1 1
2 5 5
1 1
3 2

Case #1: 6
Case #2: 12
Case #3: 27