Poj Solution 3012

http://poj.org/problem?id=3012

#include <stdio.h>


int main( ) {
    int n, k, m, t, i;
    __int64 a[32], ans, temp;
    
    scanf( "%d", &t );

    while( t-- ) {
        scanf( "%d%d%d", &n, &k, &m );

        a[0] = 10%m;
        ans = 1;
        temp = 1;
        for( i=1; i<32; i++ )
            a[i] = (a[i-1]*a[i-1])%m;
        
        for( i=0; (1<<i)<=k; i++ )
            if( k & (1<<i) )
                temp = (temp*a[i])%m;
        
        a[0] = (temp+1)%m;
        for( i=1; i<32; i++ )
            a[i] = (a[i-1]*a[i-1])%m;

        for( i=0; (1<<i)<=n; i++ )
            if( n & (1<<i) )
                ans = (ans*a[i])%m;

        printf( "%dn", ans );
    }
    return 0;
}