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

Hint

liuyiding

Source

2016年中国大学生程序设计竞赛(杭州)

提交代码