#include<cstdio>
using namespace std;
int o[1000],e[1000],s;
int main(){   //0个三也是偶数个三！ 
	o[1]=1;
	e[1]=8;
	int n;
	cin>>n;
	for(int i=2;i<=n;i++){
		o[i]=e[i-1]+o[i-1]*9; //奇数=偶数【位-1】+3 和 奇数【位-1】+除三外九个数 
		o[i]%=12345;
		e[i]=e[i-1]*9+o[i-1]; //偶数也一样 
		e[i]%=12345;
	}
	cout<<e[n]; 
	return 0;

}

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
const int INF = 0x3f3f3f3f;

int n, even[N], odd[N], k; 

int main()
{
	cin >> n;
	even[1] = 9, odd[1] = 1, k = 9;
	if (n == 1)
	{
		cout << 9;
		return 0;
	}
	for (int i = 2; i <= n; i++)
	{
		if (i == n)
			k = 8;
		even[i] = (even[i - 1] * k + odd[i - 1]) % 12345;
		odd[i] = (even[i - 1] + odd[i - 1] * k) % 12345;
	}
	cout << even[n] % 12345;
	
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin
	>>n;
	long long j=1;
	long long o=8;
	for(int i=2;i<n+1;i++){
		long long j1=(o+(j*9)%12345)%12345;
		o=((o*9)%12345+j)%12345;
		j=j1;
	}
	cout<<o;
}

#include <bits/stdc++.h>
using namespace std;
int a[1005][2];
int main()
{
	int n;
	cin >> n;
	if(n <= 1)
	{//只有一位，只有一个数:3，为奇数个3,故直接返回10-1
		cout << 9;
		return 0;
	}//最高位不能为0
//只有第一位只有9个数，其为最高位，后面的都可以取0~9;a[1][0]=8;//9-1 
//只能从0-9中取除了0和3之外的8个数字a[1][1]=1;a[1][1]前1位取奇数个3，只能取3一个数字
	a[1][0] = 8;
	a[1][1] = 1;
 	for(int i=2; i<=n; i++)
	{
		a[i][0]=(a[i-1][0]*9+a[i-1][1]*1)%12345;//一直模12345大于12345就模掉
		a[i][1]=(a[i-1][0]*1+a[i-1][1]*9)%12345;//同理 
	}
	cout << a[n][0];
	return 0;
}
//#include<bits/stdc++.h>
//using namespace std;
//int main()
//{
//	int n;
//	cin>>n;
//	long long j=1;
//	long long o=8;
//	while(n)
//	{
//		long long j1=(o+(j*9)%12345)%12345;//一直模12345大于12345就模掉 
//		o=(j+(o*9)%12345)%12345;//同理 
//		j=j1;
//		n--;
//		if(n == 1)
//		{
//			break;
//		}
//	}
//	cout<<o;
//}

#include<bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; long long j=1,o=8; for(int i=2;i<n+1;i++){ long long j1=(o+(j9)%12345)%12345; o=((o9)%12345+j)%12345; j=j1; } cout<<o; }

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin
	>>n;
	long long j=1;
	long long o=8;
	for(int i=2;i<n+1;i++){
		long long j1=(o+(j*9)%12345)%12345;
		o=((o*9)%12345+j)%12345;
		j=j1;
	}
	cout<<o;
}

#include using namespace std; int a[100000000],b[10000000]; int main(){ int n; cin>>n; a[1]=8; b[1]=1; for(int i=2;i<=n;i++){ a[i]=(9a[i-1]+b[i-1])%12345; b[i]=(9b[i-1]+a[i-1])%12345; } out<<a[n]; }