1 // 2018年全国多校算法寒假训练营练习比赛（第三场）
 2 // 不凡的夫夫
 3 #include <iostream>
 4 #include <cstdio>
 5 #include <cstring>
 6 #include <string>
 7 #include <utility>
 8 #include <algorithm>
 9 #include <vector>
10 #include <queue>
11 #include <stack>
12 #include <cmath>
13 using namespace std;
14 #define max(x,y) x>=y?x:y
15 #define lowbit(x) x&(-x)
16 #define M 1e-8
17 #define pi acos(-1.0)
18 #define e 2.718281828
19 typedef unsigned  long long ull;
20 typedef long long ll;
21  
22 int n,t;
23 int main()
24 {
25     scanf("%d",&t);
26     while(t--)
27     {
28      
29         scanf("%d",&n);
30         if(n==0)//特判
31         {
32             printf("1
");
33             continue;
34         }
35     long double ans= (log10(2*pi*n)*0.5+n*log10(n/e))/log10(8);  //换底公式,double
36         printf("%lld
",(ll)ans+1);//ll 
37     }
38     return 0;
39 }
40 //  Stirling公式）
  //林公式是是一条用来取n的阶乘的近似值的数学公式：n!≈sqrt(2*π*n)*((n/e)^n)
41 // https://www.cnblogs.com/zhangshu/archive/2011/08/12/2135855.html

1 1 // 素数定理 
2 2 // https://blog.****.net/kalilili/article/details/44835285
3 loge(x)==log(x)

 1 //中国剩余定理
 2 //poj  1006
 3 
 4 /*
 5 这里又有一个数学公式，如果a%b=c，那么(a+k*b)%b=c
 6 那么(a*k)%b=a%b+a%b+…+a%b=c+c+…+c=(k*c)%b(k>0),也就是说，如果一个除法的余数为c，
 7 那么被除数的k倍与除数相除的余数为(k*c)%b。展开式中已证明。
 8 X被a,b,c处分别余r1,r2,r3。表示为：
 9 
10 X%a = r1                     x%b = r2                     x%c = r3
11 
12 bc*k1 % a = 1     ac*k2 % b = 1     ab*k3 % c = 1
13 
14 所以
15 
16 x = bc * k1 * r1 + ac * k2 * r2 + ab * k3 * r3
17 */
18 //模数要互质。28.23.33.(条件)
19 //p+23k1==e+28k2==i+33k3=ans+d
20 #include <iostream>
21 #include <cstdio>
22 #include <cstring>
23 #include <string>
24 #include <utility>
25 #include <algorithm>
26 #include <vector>
27 #include <queue>
28 #include <stack>
29 using namespace std;
30 #define max(x,y) x>=y?x:y
31 #define lowbit(x) x&(-x)
32 #define ll long long
33 int p,e,i,d,r1,r2,r3,r;
34 void init()
35 {
36     r1=28*33,r2=23*33,r3=23*28;
37     int i=1,j=1,k=1;
38     for(;;i++)
39     {
40         if(r1*i%23==1)
41         {
42             break;
43         }
44     }
45     r1*=i;
46     for(;;j++)
47     {
48         if(r2*j%28==1)
49         {
50             break;
51         }
52     }
53     r2*=j;
54     for(;;k++)
55     {
56         if(r3*k%33==1)
57         {
58             break;
59         }
60     }
61     r3*=k;
62  r=23*28*33;
63 }
64 int main()
65 {    init();
66      int f=1;
67     while(~scanf("%d%d%d%d",&p,&e,&i,&d))
68     {
69         if(p==-1&&e==-1&&i==-1&&d==-1)
70         {
71             break;
72         }
73         int ans;
74         ans=(p*r1+e*r2+i*r3-d)%r;
75         ans=(ans+r-1)%r+1;//可能是负数或ans==0因此ans=(ans+r)%r是错的
76         printf("Case %d: the next triple peak occurs in %d days.
",f++,ans);
77     }
78     return 0;
79 }

/*
 char a[10000005];
 long long quickmod(long long  a, long long  b) 
 {     
 long long ans=1; 
 while(b)  
     {       
 if(b&1)     
     {         
 ans=(ans*a)%mod;  
 }       
 b=b/2;     
 a=(a*a)%mod; 
 }    
 return ans;
 } 
 int main()
 {     long long sum,len;  
 while(gets(a))  
     {       
 len=strlen(a);  
 sum=0;       
 for(int i=0;i<len;i++)  
     {        
 sum=(sum*10+a[i]-'0')%(mod-1);  
 }        
 if(sum==0)  
     cout<<quickmod(2,mod-2)<<endl;  
 else      
     {sum--;     
 cout<<quickmod(2,sum)<<endl;
 }   
 }  
 return 0;
 }
 
 */
 char  s[N];
 ll  poww(ll a,ll b)//不要写成pow
 {
     ll ans=1;
     while(b)
     {
         if(b&1)
         {
             ans=(ans*a)%mod;
         }
         b>>=1;
         a=(a*a)%mod;
     }
     return ans%mod;
 }
 /*
 3
 (3)
 (1,2),(2,1)
 (1,1,1)
 4 
 (4)
 (1,3),(2,2),(3,1)
 (1,1,2),(1,2,1)(2,1,1) 
 (1,1,1,1)
 其实就是2^(n-1)(%mod)
 费马小定理 ：2^((n-1)%(mod-1)(%mod)
 先利用大数取余得到  (n-1)%(mod-1)，注意0
 在用快速幂
 */
 int  main()
 {
     while(~scanf("%s",s)){
         int l=strlen(s);
         ll  sum=0;
         gep(i,0,l-1)
         {
             sum=(sum*10+s[i]-'0')%(mod-1);
         }
         if(!sum){//逆元
             printf("%lld
",poww(2,mod-2));
         }
         else{
             sum--;
             printf("%lld
",poww(2,sum));
         }
     }
     return 0;
 }