Migrated from Lutece 1501 H

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

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\le$ 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$ ($1\le T\le 100$), which indicates the number of test cases.

Every test case begins with three integers $N$, $K$ and $L$ ($0\le N\le 2000,1\le K\le 10^9,\max(1,N)\le L\le 10^9$), 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$ ($0 \leq p_i < p_{i+1} <L,0\le v_i<K$), means the position and value of $i$-th known character.

For $90\%$ of the use cases, $N\le 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$.

Samples

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

Resources

第二届中国大学生程序设计竞赛 杭州站（CCPC 2016 Hangzhou Site）