#include<bits/stdc++.h> using namespace std; int f(int n,int m){ if(n==1){ if(m==1){ return 1; } else{ return 0; } } if(m==0){ int T=1; for(int i=1;i<n;i++){ T*=9; } return 8*T; } else{ return (8*f(n-1,m)+f(n-1,m-1)%12345); } } int main() { int n; cin>>n; int S=0; for(int i=0;i<=n;i+=2){ S+=f(n,i); } cout<<S; }