#P18075. Tiling the Floor

Tiling the Floor

Tiling the Floor

题目描述

一块瓷砖由 n×nn\times n 个方格组成。每个方格的下边和左边各有一条灯带,因此一块瓷砖共有 2n22n^2 条灯带。每条灯带可以独立选择 kk 种颜色之一。

把这块瓷砖的图案无限复制,所有瓷砖保持相同朝向,通过平移无缝铺满整个无限平面。

若两个无限图案经过平移和旋转后,所有对应位置的灯带颜色都相同,则认为它们是同一种方案。旋转可改变观察的东、南、西、北方向;不允许镜像反射。颜色的名字固定,不允许把不同颜色统一重命名来判等。

求本质不同的染色方案数,对 109+710^9+7 取模。比较的是无限平面图案,因此平移不必是整块瓷砖的整数倍,可以是任意整数个方格。

输入格式

第一行整数 TT。每组数据一行两个整数 n,kn,k。

1≤T≤101\le T\le10,1≤n,k≤1091\le n,k\le10^9。

输出格式

每组输出一行一个整数,表示答案对 109+710^9+7 取模的结果。

样例 1

输入

3
1 2
2 2
114514 5201314

输出

3
31
377726028

当 n=k=2n=k=2 时,答案为 3131。旋转和平移视为相同,镜像不在允许的等价变换中。