2 2 1000000000

6 

别人的AC码：
 
#include <stdio.h>
typedef long long LL;
LL Mod;
LL multMod(LL a,LL b)
{
    LL res = 0,base = a;
    while(b)
    {
        if(b&1)
            (res += base) %= Mod;
        (base <<= 1) %= Mod;
        b >>= 1;
    }
    return res;
}

LL powerMod(LL a,LL n)
{
    LL res = 1 , base = a;
    while(n)
    {
        if(n&1)
            res = multMod(res,base);
        base = multMod(base,base);
        n >>= 1;
    }
    return res;
}

LL solve(LL a,LL n)
{
    if(n == 1)
        return a;
    LL halfsum = solve(a,n >>1);
    if(n&1)
    {
        LL half = powerMod(a,n+1 >>1);
        return (halfsum + half + multMod(half,halfsum)) % Mod;
    }
    else
    {
        LL half = powerMod(a,n >>1);
        return (halfsum + multMod(half,halfsum)) % Mod;
    }
}

int main()
{
    LL a,n;
    while(~scanf("%lld%lld%lld",&a,&n,&Mod)){
    a %= Mod;
    printf("%lld\n",solve(a,n));
    }
	return 0;
}