Khách sạn X chuẩn bị bữa tiệc tối nay với một bàn tròn lớn gồm ~n~ ghế đánh số từ ~1~ đến ~n~ theo chiều kim đồng hồ: ghế thứ ~i~ ~(\forall i = 1, \dots, n-1)~ kề với ghế thứ ~i+1~ và ghế thứ ~n~ kề với ghế thứ ~1~.

Để đảm bảo tính thẩm mĩ, các ghế sẽ được phủ bằng khăn phủ ghế làm bằng vải thượng hạng, mỗi khăn phủ ghế được nhuộm một loại màu duy nhất. Khách sạn có tổng cộng ~k~ loại màu khăn được đánh số từ ~1~ đến ~k~, mỗi loại có số lượng vô hạn.

Trước giờ khai tiệc, đã có ~m~ ~(m \le n)~ chiếc ghế được phủ khăn, ghế thứ ~p_j~ ~(\forall j = 1, \dots, m)~ được phủ khăn màu ~c_j~. Các ghế còn lại chưa được phủ khăn và Quản lý có thể tự do chọn màu khăn phủ cho chúng sao cho thỏa mãn: "toàn bộ ~n~ ghế đều phải được phủ khăn và không có hai ghế kề nhau nào được phủ màu giống nhau".

Hãy đếm số cách mà Quản lý có thể chọn phủ khăn sao cho thỏa mãn điều kiện trên. Hai cách được coi là khác nhau nếu tồn tại một chiếc ghế được phủ màu khác nhau trong hai cách đó. Do số cách có thể rất lớn nên hãy in ra kết quả sau khi chia lấy dư cho ~10^9+7~.

Trong bài này, bạn cần trả lời ~T~ truy vấn như vậy.

Input

• Dòng đầu chứa số nguyên ~T~ ~(1 \le T \le 10^5)~ là số truy vấn cần trả lời;

• Tiếp theo là ~T~ truy vấn, truy vấn thứ ~i~ gồm:

  • Dòng đầu tiên chứa ba số nguyên ~n, k, m~ ~(3 \le n \le 10^{18}; 1 \le k \le 10^9; 0 \le m \le n)~;

  • Tiếp theo là ~m~ dòng, mỗi dòng chứa hai số nguyên ~p_j, c_j~ ~(1 \le p_j \le n; 1 \le c_j \le k)~.

Các ~p_j~ trong cùng một truy vấn đôi một khác nhau và được cho theo thứ tự bất kỳ.

Dữ liệu bảo đảm tổng của các ~m~ trên toàn bộ ~T~ truy vấn không vượt quá ~2 \cdot 10^5~.

Output

Gồm ~T~ dòng, dòng thứ ~i~ ~(1 \le i \le T)~ là câu trả lời cho truy vấn thứ ~i~ (chia lấy dư cho ~10^9+7~).

Scoring

Sample Input 1

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

Sample Output 1

30
9
1

Notes

Truy vấn ~1~: tổng cộng ~30~ cách phủ khăn thỏa mãn.

Truy vấn ~2~: tổng cộng ~9~ cách phủ khăn thỏa mãn.

Truy vấn ~3~: chỉ có hai cách phủ khăn để không có hai ghế liền kề cùng màu. Trong đó chỉ có một cách mà ghế ~1~ được phủ khăn màu ~1~.