# Hazy String

Time Limit: 6000/3000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

## Description

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.

## Input

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.

## Output

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

## Sample Input

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

## Sample Output

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

liuyiding

## Source

2016年中国大学生程序设计竞赛（杭州）