가게 주인은 손님을 끌기 위해 가게 앞에 놓을 특별한 네온사인을 주문하기로 했다. 이 네온사인은 여러 사다리 모양 부품으로 이루어진다. 각 부품은 정점 $2n$개, 간선 $3n-2$개인 평면 무방향 그래프인 사다리 그래프 $L_n$으로 나타낼 수 있다. 각 정점은 네온사인의 전구를, 각 간선은 두 전구를 잇는 전선을 나타낸다. 사다리 그래프는 두 경로 그래프의 데카르트 곱으로 얻을 수 있으며, 그중 하나는 간선이 하나뿐이다. 즉 $L_n=P_n\times P_2$이고 $P_n$은 정점 $n$개의 경로이다. 그림 1은 $L_6$을 보여 준다. $k$개 사다리 부품을 지탱하는 주 프레임은 정$k$각형이다.

그림 1: $L_6$.

정$k$각형의 각 변을 $L_n$의 맨 위 간선과 결합한다. 그림 2는 $k=3$, $n=4$인 경우를, 그림 3은 $k=4$, $n=3$인 경우를 보여 준다. 설명을 쉽게 하기 위해 네온사인을 전구(정점)와 전선(간선)으로 이루어진 그래프 $G=(V,E)$로 나타낸다. 네온 불빛을 더 눈부시게 만들기 위해,

그림 2: $k=3$, $n=4$인 예.

디자이너 Ray는 $G$의 전구(정점)에 색을 지정하는 방법을 생각해 냈다. Ray는 다음 조건을 만족하도록 전구에 색을 부여하고 싶다. $G$의 정점들에 색을 부여하여 인접한 정점 $u$, $v$의 색이 다르면 이를 올바른 색칠이라고 한다. $G=(V,E)$의 전구들은 구별되며, 즉 $v_1,v_2,\ldots,v_m$이라는 이름표가 있다. 따라서 최대 $\lambda$가지 색을 사용하는 $G$의 올바른 색칠은 정의역 $V$, 공역 $\{1,2,3,\ldots,\lambda\}$인 함수 $f$이며, 인접한 정점 $u,v\in V$에 대해 $f(u)\ne f(v)$이다. 두 색 부여 방식의 차이는 이 함수들의 차이와 같다. $\lambda$가지 색으로 $G$를 색칠하는 서로 다른 방법의 최대 수를 $G$의 임계 수라고 한다.

(1) $L_n$에 대한 $n$, (2) 정$k$각형에 대한 $k$, (3) 사용할 수 있는 색의 수 $\lambda$가 주어진다. $G$의 임계 수를 계산해야 한다. 결과가 $10^9+7$ 이상이면 $10^9+7$로 나눈 나머지, 즉 실제 값을 $10^9+7$로 나누어 얻는 나머지를 출력해야 한다.

그림 3: $k=4$, $n=3$인 예.

입력

입력 파일의 첫 번째 줄에는 테스트 케이스 수를 나타내는 정수 $L$($L\le20$)이 주어진다. 각 테스트 케이스의 첫 번째 줄에는 $n$, $k$, $\lambda$를 나타내는 세 정수가 공백으로 구분되어 주어진다.

제한

• $1\le n\le1000000000$.

• 각 테스트 케이스에서 $3\le k\le1000000000$.

• $0\le\lambda\le1000000000$.

출력

각 테스트 케이스에 대해 한 줄을 출력한다. 각 줄에는 $G$의 임계 수를 나타내는 음이 아닌 정수 하나를 출력한다. 결과가 $10^9+7$ 이상이면 $10^9+7$로 나눈 나머지, 즉 실제 값을 $10^9+7$로 나누어 얻는 나머지를 출력해야 한다.

예제

입력 1

1
2 3 3

출력 1

162