找规律吧。可以快速幂模
#include <iostream>
#include <cstdio>
using namespace std;__int64 Power(__int64 a,__int64 b,__int64 k){
__int64 ans=1;
a%=k;
while(b){
if(b&1){
ans=ans*a%k;
}
b>>=1;
a=a*a%k;
}
return ans;
}int main(){
__int64 k;
while(scanf("%I64d",&k),k){
__int64 ans=Power(2,k-1,k);
printf("%I64d\n",(ans+1)%k);
}
return 0;
}