On of Vance's favourite hero is Invoker, Kael. As many people knows Kael can control the elements and combine them to invoke a powerful skill. Vance like Kael very much so he changes the map to make Kael more powerful.

In his new map, Kael can control n kind of elements and he can put m elements equal-spacedly on a magic ring and combine them to invoke a new skill. But if a arrangement can change into another by rotate the magic ring or reverse the ring along the axis, they will invoke the same skill. Now give you n and m how many different skill can Kael invoke? As the number maybe too large, just output the answer mod 1000000007.

The first line contains a single positive integer T( T <= 500 ), indicates the number of test cases.
For each test case: give you two positive integers n and m. ( 1 <= n, m <= 10000 )

For each test case: output the case number as shown and then output the answer mod 1000000007 in a line. Look sample for more information.

2

3 4

1 2

Case #1: 21

Case #2: 1

For Case #1: we assume a,b,c are the 3 kinds of elements.
Here are the 21 different arrangements to invoke the skills
/ aaaa / aaab / aaac / aabb / aabc / aacc / abab / 
/ abac / abbb / abbc / abcb / abcc / acac / acbc /
/ accc / bbbb / bbbc / bbcc / bcbc / bccc / cccc /

2011 Multi-University Training Contest 9 - Host by BJTU

---

　　逆元的作用？让我们来看下面的例子:
　　12 / 4 mod 7 = ?  很显然结果是3
　　我们现在对于数对 (4,7), 可以知道 X = 2是 4 对7的乘法逆元即2*4=1（mod 7)
　　那么我们有(12 / 4) * (4 * 2 ) = (?) * (1) (mod 7)
　　除法被完美地转化为了乘法。

 

#include <iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

using namespace std;

int T;

const long long mod=;

long long res,n,m;

long long gcd(long long a,long long b)

{

    return b?gcd(b,a%b):a;

}

long long poww(long long a,long long b)

{

    long long ans=;

    while(b)

    {

        if (b%==) ans=(ans*a)%mod;

        a=(a*a)%mod;

        b/=;

    }

    return ans;

}

int main()

{

    scanf("%d",&T);

    for(int t=;t<=T;t++)

    {

        scanf("%lld%lld",&m,&n);

        res=;

        for(long long i=;i<n;i++)

          res=(res+poww(m,gcd(n,i)))%mod;

        if(n%==)

          res=(res+poww(m,(n+)/)*n)%mod;

        else

        {

           res=(res+poww(m,n/+)*(n/))%mod;

           res=(res+poww(m,n/)*(n/))%mod;

        }

        printf("Case #%d: ",t);

        printf("%lld\n",(res*poww(*n,mod-))%mod);

    }

    return ;

}

#include <iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

using namespace std;

int T;

const long long mod=;

long long res;

int m,n;

int gcd(int a,int b)

{

    return b?gcd(b,a%b):a;

}

long long poww(long long a,int b)

{

    long long ans=;

    while(b)

    {

        if (b&) ans=(ans*a)%mod;

        a=(a*a)%mod;

        b/=;

    }

    return ans;

}

//返回d=gcd(a,b);和对应于等式ax+by=d中的x,y

long long extend_gcd(long long a,long long b,long long &x,long long &y)

{

    if(a==&&b==) return -;//无最大公约数

    if(b==){x=;y=;return a;}

    long long d=extend_gcd(b,a%b,y,x);

    y-=a/b*x;

    return d;

}

//*********求逆元素*******************

//ax = 1(mod n)

long long mod_reverse(long long a,long long n)

{

    long long x,y;

    long long d=extend_gcd(a,n,x,y);

    if(d==) return (x%n+n)%n;

    else return -;

}

int main()

{

    scanf("%d",&T);

    for(int t=;t<=T;t++)

    {

        scanf("%d%d",&m,&n);

        res=;

        for(int i=;i<n;i++)

          res=(res+poww(m,gcd(n,i)))%mod;

        if(n%==)

          res=(res+poww(m,(n+)/)*n)%mod;

        else

        {

           res=(res+poww(m,n/+)*(n/))%mod;

           res=(res+poww(m,n/)*(n/))%mod;

        }

        printf("Case #%d: ",t);

        printf("%I64d\n",(res*mod_reverse(*n,mod))%mod);

    }

    return ;

}