1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<cstdio>
template<typename T>
T pow_any_type(T x,unsigned int n){
    for(T tmp(1);;x*=x){
        if(n&1)tmp*=x;
        if((n>>=1)==0)return tmp;
    }
}
#define MOD 12357
struct Fib_Matrix{
    int d00,d01,d10,d11;
    Fib_Matrix(int x0=1,int x1=0,int x2=0,int x3=1):d00(x0),d01(x1),d10(x2),d11(x3){}
    void operator*=(Fib_Matrix &_m){
        int td00,td01,td10,td11;
        td00=(d00*_m.d00+d01*_m.d10)%MOD;
        td01=(d00*_m.d01+d01*_m.d11)%MOD;
        td10=(d10*_m.d00+d11*_m.d10)%MOD;
        td11=(d10*_m.d01+d11*_m.d11)%MOD;
        d00=td00;d10=td10;d01=td01;d11=td11;
    }
};
int main(){
    int i;
    scanf("%d",&i);
    if(i&1){
        printf("0\n");
    }else{
        i>>=1;
        Fib_Matrix fib(0,-1+MOD,1,4);
        fib=pow_any_type(fib,i);
        printf("%d\n",(fib.d00+3*fib.d10)%MOD);
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX