http://acm.fzu.edu.cn/problem.php?pid=1905

         浙江理工邀请赛G题的进化版，AC大牛出的题，专门卡矩阵做法的，不用AC大牛的做法至今无人能过，比赛的时候想起来AC大牛的blog中有写过解法的，跑去AC大牛blog一看，已经被删除啦。。。唉，怪自己当初没有好好研究AC牛的解法，想会矩阵解法就万事大吉了。AC牛的解法效率相当高。。。
         这是AC大牛的解法传送门  http://hi.baidu.com/aekdycoin/blog/item/63f633ec11c822d8b21cb168.html  OrzOrz

         以下是我的代码，基本是模仿AC牛的代码写的，主要是因为之前phi函数写次了，TLE 好多次，就按照AC的代码在改，改到最后代码基本一样了，我还是TLE。。。后来发现是phi函数写次了。。。现在的代码基本跟AC的一样。。。我觉得AC大牛的那个sum函数写得很好

  1// AC大牛的博文 http://hi.baidu.com/aekdycoin/blog/item/63f633ec11c822d8b21cb168.html
  2// n - spos 不一定是 Slen 的整数倍,而我们需要的是
  3// (n - Spos) / Slen  的向下取整的结果(  完整周期数)
  4// (n - Spos) % Slen = C 表示最后剩余的那个不完整周期
  5
  6// 而由于周期数很大，因此我们只需要计算 周期数  mod P
  7// 那么可以这么转化
  8// ( n - Spos - C ) / Slen % P -> ( n - Spos - C ) % ( P * Slen ) / Slen
  9
 10#include <stdio.h>
 11#include <iostream>
 12using namespace std;
 13
 14typedef __int64 ll;
 15ll Spos, Slen;
 16ll X1, Y1, Y2, Z2;
 17ll HP, P, Q;
 18
 19template<class T> T MOD( T a, T b ){ a %= b; return a < 0 ? a + b : a; }
 20
 21ll phi( ll n )
 22{
 23    ll ret = n;
 24    int i, j;
 25    for( i = 2, j = 4; j <= n; i++, j += i + i - 1 )
 26    {
 27        if( !( n % i ) )
 28        {
 29            ret = ret / i * ( i - 1 );
 30            while( !( n % i ) ) n /= i;
 31        }
 32    }
 33    if( n > 1 ) ret = ret / n * ( n - 1 );
 34    return ret;
 35}
 36
 37ll pow_mod( ll a, ll b, ll c )
 38{
 39    ll ans = 1, d = a % c;
 40    while( b )
 41    {
 42        if( b & 1 ) ans = d * ans % c;
 43        d = d * d % c;
 44        b >>= 1;
 45    }
 46    return ans;
 47}
 48
 49ll mul_mod( ll a, ll b, ll c )
 50{
 51    ll ans = 0, d = a % c;
 52    while( b )
 53    {
 54        if( b & 1 )if( ( ans += d ) >= c ) ans -= c;
 55        if( ( d <<= 1 ) >= c ) d -= c;
 56        b >>= 1;
 57    }
 58    return ans ;
 59}
 60
 61ll Bpow_mod( ll a, ll b, ll c )
 62{
 63    ll ans = 1, d = a % c;
 64    while( b )
 65    {
 66        if( b & 1 ) ans = mul_mod( ans, d, c );
 67        d = mul_mod( d, d, c );
 68        b >>= 1;
 69    }
 70    return ans;
 71}
 72
 73// 计算 1 + Q + Q^2 + Q^3 +  + Q^n;
 74ll sum( ll n )
 75{
 76    ll S;
 77    if( n < 0 ) return 0;
 78    if( n == 0 ) return 1 % P;
 79    if( n == 1 ) return ( 1 + Q ) % P;
 80    if( n & 1 )
 81    {
 82        S = sum( n >> 1 );
 83        return ( S + S * pow_mod( Q, n / 2 + 1, P ) % P ) % P;
 84    }
 85    S = sum( n - 1 );
 86    return ( S + pow_mod( Q, n, P ) ) % P;
 87}
 88
 89void Read( )
 90{
 91    scanf("%I64d%I64d",&X1,&Y1);
 92    scanf("%I64d%I64d%I64d",&Y2,&Z2,&P);
 93}
 94
 95// ( n - Spos - C ) / Slen % P -> ( n - Spos - C ) % ( P * Slen ) / Slen
 96//  Spos总归会是一个比较小的数
 97ll cal( ll & res_seg )  // res_seg 为 C 
 98{
 99    ll mod_res = pow_mod( Y2, Z2, Slen );
100    res_seg = mod_res = MOD( mod_res - Spos, Slen );
101    ll ret = Bpow_mod( Y2, Z2, HP ) - Spos - mod_res;
102    ret = MOD( ret, HP ) / Slen;
103    return ret; // 返回周期数 mod P之后的余数
104}
105
106void solve( int k )
107{ 
108    int i;
109    ll ret, ss, v, limit, XX; 
110    Slen = phi( P );
111    HP = (ll)P * Slen;
112    Q = pow_mod( X1, Y1, P );
113    Q = MOD( -Q, P );
114    for( Spos = 0;  ; Spos++ )
115        if( pow_mod( Q, Spos, P ) == pow_mod( Q, Spos + Slen, P ) )break;
116    XX = 1;
117    for( i = 0; i < Y1; i++ )
118    {
119        XX *= X1;
120        if( XX > Spos )
121            break;
122    }
123    if( i == Y1 )
124    {
125        limit = XX;
126        for( ret = 0, v = 1 % P, i = 0; i < limit; v = v * Q % P, i++ )
127            ret = ( ret + v ) % P;
128        printf("Case #%d: %I64d\n",k, ret);
129        return ;
130    }
131    limit = Spos;
132    // 计算不再循环周期之内的数之和 mod P
133    for( ret = 0, v = 1 % P, i = 0; i < limit; v = v * Q % P, i++ )
134        ret = ( ret + v ) % P;
135    // 计算一个周期内的数之和 mod P
136    ll seg_sum = sum( Slen - 1 ) * pow_mod( Q, Spos, P ) % P;
137    ll res_seg;
138    ss = cal( res_seg );
139    ret = ( ret + seg_sum * ss % P ) % P;
140    ret = ( ret + sum( res_seg - 1 ) * pow_mod( Q, Spos, P ) % P ) % P;
141    printf("Case #%d: %I64d\n",k,ret);
142}
143
144int main( int argc, char *argv[] )
145{
146    int t, k = 1;
147    scanf("%d",&t);
148    while( t-- )
149    {
150        Read( );
151        solve( k );
152        k++;
153    }
154    return 0;
155}
156