무한히 넓은 바닥에 무한히 많은 타일을 깔아야 합니다.
각 타일에는 $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
노트
다음 이미지는 $n = k = 2$일 때의 19가지 구성 방법을 보여줍니다(타일을 깐 효과를 더 잘 보여주기 위해 각 이미지는 $3 \times 3$ 형태로 배열된 9개의 타일을 보여주며, LED는 어두운 색과 밝은 색 두 가지로 표시됩니다). 처음 12가지 방법에서 어두운 색과 밝은 색을 서로 바꾸면 또 다른 12가지 방법을 얻을 수 있어, 총 31가지 방법이 됩니다.
