题目wa了好多回悲催…不能直接求逆元来计算，还是要用到数论中的小技巧啊…
贴神牛的题解吧
// 这题主要求S
// 结论： S = （251^（n+1）-1） * （2^（3n+1）-1） / 250
// 是两个等比数列和相乘
//
// 推理：
// 2008 = 2^3 * 251
// 所以 2008^N 有 3N 个 2 和 N 个251
// 所有仅由2组成的因子有
// 2^0 2^1 2^2 … 2^（3N）
// 设集合 C = {2^0, 2^1, 2^2 …，2^（3N）};
// SUM（C） = 2^（3n+1）-1
// 跟251组合产生的因子有
// 251^0 * C
// 251^1 * C
// …
// 251^N * C
// 所有因子和为：
// S = （251^（n+1）-1））/250 * （2^（3n+1）-1）
// 计算S%K:
// S 很大， 不能保存在普通的数据类型中， 需要直接计算S%K
// 因为S有个分母250, 设 S = X/250
// 则 S%K = （X/250）%K = （X%（250*K））/250
// 变成先求余数再除法的形式
知道了数论中的技巧，不能用你逆元来求哇，因为不满足gcd（250,k ）或者gcd（2,k）不一定是互质的， 代码就不是再是问题了，
#include<stdio.h>
int mult（int a1,int n,int k）{
if（n==0） return 1;
__int64 b=1,a = a1;
while（n>1）{
if（n%2==0） {
a=a*a%k;
n/=2;
}
else {
b=b*a%k;
n--;
}
}
return a*b%k;
}
int main（）{
int n,k;
while（scanf（"%d%d",&n,&k），n&&k）{
__int64 a=mult（2,3*n+1,250*k）；
__int64 b=mult（251,n+1,250*k）；
a-- , b--;
a = （ a*b ）%（250*k）；
a /= 250;
printf（"%d\n",mult（2008,a,k））；
}
}