查数

Grade 0 Open Time Wednesday, 16 January 2013, 4:10 pm
Discount 0.8 Time Discount Wednesday, 16 January 2013, 4:10 pm
Allow late Yes Close Time Wednesday, 16 January 2013, 4:10 pm
Input file chashu.in Output file chashu.out
【问题描述】
    在所有的N位数中,有多少个数中有偶数个数字3?
 
【输入格式】
     文件只有一行为一个正整数n
 
【输出格式】
     输出文件只有一个整数,方案数(由于结果可能很大,你只需要输出这个答案mod 12345的值。)。
 
【输入输出样例】
 
输入:
chashu.in
2
输出:
chashu.out
73
 
数据规模:1<=N<=1000