#include<iostream> 
#include<iomanip> 
#include<set>
#include<string> 
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e3 + 10;
int a[N] , b[N] , c = 9;
int main(){
	int n;
	cin >> n;
	a[1] = 8,b[1] = 1;
	for(int i = 2;i <= n;i++)
	{
		if(i == n) c = 8;
		a[i] = (a[i - 1] * 9 + b[i - 1] * 1) % 12345;
		b[i] = (a[i - 1] * 1 + b[i - 1] * 9) % 12345;
	}
	cout << a[n] << endl;
	return 0;
}