记录编号	339981	评测结果	AAAAAAAAAA
题目名称	查数	最终得分	100
用户昵称	Smile	是否通过	通过
代码语言	C++	运行时间	0.197 s
提交时间	2016-11-06 08:35:01	内存使用	4.20 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

#define LL long long 

const int maxn=1000+10;
const int MOD=12345;

int c[maxn][maxn];
int n, ans;

/*int pow(int a, int b, int c) {
	if(!b) return 1;
	int x=pow(a, b/2, c);
	LL ans=(x*x)%c;
	if(b%2==1) ans=(ans*a)%c;
	return (int) ans;
}快速幂 */

int pow(int x,int ci, int c)
{
	int re=1;
	while(ci>0)
	{
		if(ci&1)
		{
			re=(re*x)%c;
		}
		ci>>=1;
		x=(x*x)%c;
	}
	return re;
}

void Getc(int n) {
	for(int i=0; i<=n; i++) c[i][0]=1;
	
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=i; j++) c[i][j]=(c[i-1][j-1]+c[i-1][j])%MOD;
	}
}//利用公式c[n][k]=c[n-1][k]+c[n-1][k-1] 求所有c[i][j]; 

int main() {
	freopen("chashu.in","r",stdin);
	freopen("chashu.out","w",stdout);
	cin>>n;
	Getc(n);
	//i枚举的是3的个数； 
	for(int i=2; i<=n; i+=2) {
		for(int j=1; n-j>=i-1; j++) {
			int tmp=c[n-j][i-1];
			if(j==1) {
				ans=(ans+tmp*pow(9, n-i, MOD))%MOD;
			}
			else {
				ans=(ans+tmp*pow(9, n-i-1, MOD)*8)%MOD;
			}
		}
		// j枚举的是第一个3的位置，然后就是从n-j个数中选i-1个数作为3(c[n-j][i-1]);
		//由于首位不能为0， 所以j==1要特判（这就是j存在的意义）； 
	}
	ans=(ans+8*pow(9, n-1, MOD))%MOD;   //加上0个3的情况； 
	cout<<ans;
	return 0;
}