Now given a positive integer N, get the sum S of all positive integer divisors of 2008^N.
Oh no, the result may be much larger than you can think. But it is OK
to determine the rest of the division of S by K. The result is kept as
M.

Pay attention! M is not the answer we want. If you can get 2008^M,
that will be wonderful. If it is larger than K, leave it modulo K to
the output. See the example for N = 1，K = 10000: The positive integer
divisors of 20081 are 1、2、4、8、251、502、1004、2008，S = 3780, M = 3780, 2008^M % K = 5776.

2.(a/b)%mod=a*b^(mod-2)%mod，mod为素数（可以通过逆元证明）（这个公式的话感觉如果mod为素数的话，直接用逆元也一样的，，可以参考我博客hdu1452）

然后这个题并不难，把2008分解成 251*2^3 然后求因子和用第一个公式去掉分母250,然后可以得到M，在用快速幂计算就好了。

#include <stdio.h>

#include <iostream>

using namespace std;

typedef long long LL;

LL pow_mod(LL a,LL n,LL mod){

    LL ans = ;

    while(n){

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

        a=a*a%mod;

        n=n>>;

    }

    return ans;

}

int main()

{

    LL N,K;

    while(scanf("%lld%lld",&N,&K)!=EOF,N&&K)

    {

        K = *K;

        LL M = ((pow_mod(,N+,K)-)*(pow_mod(,*N+,K)-))%K;

        M = M/;

        K/=;

        LL ans =pow_mod(,M,K);

        printf("%lld\n",ans);

    }

    return ;

}