58 lines
995 B
C++
58 lines
995 B
C++
#include <cstdio>
|
|
#include <cmath>
|
|
#include <iostream>
|
|
#include <algorithm>
|
|
#define mod 10007
|
|
int Pow(int a,int b)
|
|
{
|
|
int ans=1;
|
|
while(b)
|
|
{
|
|
if(b&1)
|
|
{
|
|
b--;
|
|
ans*=a;
|
|
ans%=(3*mod);
|
|
}
|
|
else
|
|
{
|
|
b/=2;
|
|
a*=a;
|
|
a%=(3*mod);
|
|
}
|
|
}
|
|
return ans;
|
|
}
|
|
int solve(int n)
|
|
{
|
|
if(n&1)
|
|
{
|
|
n++;
|
|
n/=2;
|
|
int ans=Pow(4,n-1);
|
|
ans+=5;
|
|
ans/=3;
|
|
return ans%mod;
|
|
}
|
|
else
|
|
{
|
|
n/=2;
|
|
int ans=2*Pow(4,n-1);
|
|
ans+=4;
|
|
ans/=3;
|
|
return ans%mod;
|
|
}
|
|
}
|
|
int main()
|
|
{
|
|
int t;
|
|
scanf("%d",&t);
|
|
for(int i=1;i<=t;i++)
|
|
{
|
|
int n;
|
|
scanf("%d",&n);
|
|
printf("Case #%d: %d\n",i,solve(n));
|
|
}
|
|
return 0;
|
|
}
|