#include<bits/stdc++.h>  
using namespace std;  
int main() {  
	int a[1001][2], b, n; // 定义一个二维数组a用于存储计算结果，b用于临时存储，n为输入的数字  
	cin >> n; // 输入n的值  
	a[1][1] = 1; // 初始化a[1][1]为1  
	a[1][0] = 9; // 初始化a[1][0]为9  
	// 当n等于1时，执行以下逻辑  
	if (n == 1) {  
		for (int i = 2; i <= n; i++) { // 从2到n进行循环  
			b = a[1][0]; // 将a[1][0]的值赋给b  
			if (i == n) { // 如果i等于n  
				b--; // b减1  
			}  
			// 计算a[i][0]和a[i][1]的值  
			a[i][0] = (a[i - 1][0] * b + a[i - 1][1]) % 12345; // 更新a[i][0]  
			a[i][1] = (a[i - 1][1] * b + a[i - 1][0]) % 12345; // 更新a[i][1]  
		}  
		cout << a[n][0] - 1; // 输出a[n][0]减1的结果  
	}   
	// 当n不等于1时，执行以下逻辑  
	else if (n != 1) {  
		for (int i = 2; i <= n; i++) { // 从2到n进行循环  
			b = a[1][0]; // 将a[1][0]的值赋给b  
			if (i == n) { // 如果i等于n  
				b--; // b减1  
			}  
			// 计算a[i][0]和a[i][1]的值  
			a[i][0] = (a[i - 1][0] * b + a[i - 1][1]) % 12345; // 更新a[i][0]  
			a[i][1] = (a[i - 1][1] * b + a[i - 1][0]) % 12345; // 更新a[i][1]  
		}  
		cout << a[n][0]; // 输出a[n][0]的结果  
	}  
	return 0; // 程序结束  
}