ACM-ICPC 2018 徐州赛区网络预赛 A. Hard to prepare

262144K

After Incident, a feast is usually held in Hakurei Shrine. This time Reimu asked Kokoro to deliver a Nogaku show during the feast. To enjoy the show, every audience has to wear a Nogaku mask, and seat around as a circle.j) and every number has

You may have seen 《A Summer Day's dream》, a doujin Animation of Touhou Project. Things go like the anime, Suika activated her ability, and the feast will loop for infinite times. This really troubles Reimu: to not make her customers feel bored, she must prepare enough numbers of different Nogaku scenes. Reimu find that each time the same guest will seat on the same seat, and She just have to prepare a new scene for a specific mask distribution. Two distribution plans are considered different, if any guest wears different masks.

In order to save faiths for Shrine, Reimu have to calculate that to make guests not bored, how many different Nogaku scenes does Reimu and Kokoro have to prepare. Due to the number may be too large, Reimu only want to get the answer modules

Input

First line one number

Output

For each testcase output one line with a single number of scenes Reimu and Kokoro have to prepare, the answer modules

样例输入

2
3 1
4 2

样例输出

2
84

题目来源

ACM-ICPC 2018 徐州赛区网络预赛

/*
n个人作成一个环，2^k个面具，[0,2^k-1]
每个人一个面具，面具的编号可以相同，相邻的人的面具的编号
异或结果>0,(1^1==1,0^0==0,0^1==0,和正常的不一样)问共有几种排列方式。
*/
/*
分析 :按照题目给的异或，两个数只有每一位都是不同的，那么异或的
结果才是0,也就是说，两者的和为2^k-1,因为(every number has k bits.)
如  ：k==2,对于0 :0,1,2都是可以的，只有一个3不行
那么第一个位置2^k,第二个位置2^k-1，一直到第n-1个位置都是2^k-1
但是第n个位置，要分情况讨论了
1：第一个位置和第n-1个位置不同，那么第n个位置的选择数目为2^k-2
2：第一个位置和第n-1个位置相同，就不好说了
举个例子：
n==4,k==2
我们可以先让整体为2^k*poww(2^k-1,n-2),那么在poww(2^k-1,n-2)中
包含上面的1，2两种情况，针对2,少的数目为第一个位置和第N-1个位置
一样的情况数，因为两者一样，可以把两者看成一个整体，因为2^k-1-(2^k-2)==1
,因此第n个位置是固定的，不需要考虑了，那么就还剩下n-2个
*/
#define  ull unsigned  long  long 
#define ll  long  long 
const  int N=1e6+4;
const  ll mod=1e9+7;
int t;
ll n,k;
ll f[N];
void  init()
{
    f[0]=1;
    for(int i=1;i<N;i++)
    {
        f[i]=(2ll*f[i-1])%mod;
    }
}
ll poww(ll   a,ll   b)
{
    ll ans=1;
    while(b)
    {
        if(b&1) {
            ans=ans*a%mod;
        }
        b>>=1;
        a=a*a%mod;
    }
    return  ans%mod;
}
ll dfs(int n,int k)
{
    if(n==1) return f[k]%mod;
    else  if(n==2)  return  (f[k]*(f[k]-1))%mod;
    ll ans=0;
    ans=(  (f[k]*poww(f[k]-1,n-2)%mod)*(f[k]-2ll)   )%mod;
    ans=(ans+dfs(n-2,k))%mod;
    return  ans;
}
int main()
{
    
    scanf("%d",&t);
    init();
    while(t--)
    {
        scanf("%lld%lld",&n,&k);
        printf("%lld
",dfs(n,k));
    }
    return 0;
}