#include<bits/stdc++.h> using namespace std; int jis[1001]; int ous[1001]; int main(){ int n; cin>>n; jis[1]=1; ous[1]=8; for(int i=2;i<=n;i++){ jis[i]=(jis[i-1]*9+ous[i-1])%12345; ous[i]=(ous[i-1]*9+jis[i-1])%12345; } cout<<ous[n]; return 0; }