บนพื้นที่กว้างใหญ่เป็นอนันต์ คุณต้องปูกระเบื้องจำนวนอนันต์แผ่น
กระเบื้องแต่ละแผ่นมีลวดลายเป็นตารางสี่เหลี่ยมจัตุรัสขนาด $n \times n$ โดยแต่ละช่องตารางของกระเบื้องจะมีแถบไฟ LED ติดตั้งอยู่ตามขอบด้านล่างและขอบด้านซ้าย ซึ่งมีสีสันต่างกันทำให้เกิดลวดลายที่สวยงาม
ลวดลายบนกระเบื้องแต่ละแผ่นจะเหมือนกันทุกประการ เมื่อปูกระเบื้อง เราจะวางกระเบื้องจำนวนอนันต์แผ่นเรียงต่อกันแบบไร้รอยต่อ เกิดเป็นลวดลายแถบไฟขนาดอนันต์
มีสีที่แตกต่างกันทั้งหมด $k$ สีให้เลือกใช้ และคุณต้องเลือกสีให้กับแถบไฟทั้งหมด $2n^2$ เส้นบนกระเบื้องหนึ่งแผ่น หลังจากนั้นกระเบื้องแผ่นอื่นๆ จะคัดลอกรูปแบบการลงสีนี้โดยอัตโนมัติ เมื่อปูกระเบื้อง กระเบื้องทุกแผ่นจะถูกวางในทิศทางเดียวกัน ซึ่งหมายความว่าสามารถมองเป็นการเลื่อนขนานกระเบื้องแผ่นเดียวแล้วนำมาต่อกันโดยไม่มีการหมุน
ในขณะที่คุณเดินอยู่บนพื้น คุณต้องการทราบว่ามีรูปแบบการลงสีกระเบื้องที่แตกต่างกันโดยเนื้อแท้ทั้งหมดกี่แบบ เนื่องจากพื้นมีขนาดเป็นอนันต์ และผู้ที่สังเกตกระเบื้องอาจหันหน้าไปในทิศทางต่างๆ (เหนือ, ใต้, ตะวันออก, ตะวันตก) ดังนั้นสองรูปแบบจะถูกนิยามว่าเหมือนกันโดยเนื้อแท้ก็ต่อเมื่อ:
เมื่อสังเกตระนาบพื้นขนาดอนันต์ที่สร้างขึ้นจากทั้งสองรูปแบบ หากมีลำดับของการเลื่อนขนานหรือการหมุน (ไม่รวมการสะท้อน) ที่สามารถทำให้สีของแถบไฟในทุกตำแหน่งบนพื้นเหมือนกันทุกประการ รูปแบบทั้งสองนี้จะถือว่าเหมือนกันโดยเนื้อแท้
ข้อมูลนำเข้า
มีข้อมูลทดสอบหลายชุดในไฟล์เดียว บรรทัดแรกของข้อมูลนำเข้าประกอบด้วยจำนวนเต็มบวก $T$ ($1 \le T \le 10$) แทนจำนวนชุดข้อมูลทดสอบ
สำหรับแต่ละชุดข้อมูลทดสอบ:
- บรรทัดแรกประกอบด้วยจำนวนเต็มสองจำนวนคือ $n$ และ $k$ ($1 \le n \le 10^9$, $1 \le k \le 10^9$) แทนขนาดของลวดลายและจำนวนสีตามลำดับ
ข้อมูลส่งออก
สำหรับแต่ละชุดข้อมูลทดสอบ ให้แสดงผลหนึ่งบรรทัดประกอบด้วยจำนวนเต็มหนึ่งจำนวน แทนจำนวนรูปแบบที่แตกต่างกันโดยเนื้อแท้ มอดูโล $10^9 + 7$
ตัวอย่าง
ข้อมูลนำเข้า 1
3 1 2 2 2 114514 5201314
ข้อมูลส่งออก 1
3 31 377726028
หมายเหตุ
ภาพต่อไปนี้แสดงรูปแบบการสร้าง 19 แบบสำหรับ $n = k = 2$ (เพื่อให้เห็นผลลัพธ์ของการปูกระเบื้องได้ชัดเจนขึ้น แต่ละภาพจะแสดงกระเบื้อง 9 แผ่นที่จัดเรียงในรูปแบบ $3 \times 3$ โดยมีไฟ LED สีเข้มและสีอ่อน) การสลับสีเข้มและสีอ่อนของ 12 รูปแบบแรกจะทำให้ได้อีก 12 รูปแบบ รวมเป็นทั้งหมด 31 รูปแบบ
