P6740: 偶数个3

---

【题目描述】

题目描述

在所有的N位正整数（1位数不包含0）中，有多少个数中有偶数（0也是偶数）个数字3？

输入格式

读入一个数N。1<=N<=1000。

输出格式

一个整数，表示答案。
注意：0个3也是偶数个3，但是1位数里不包含0.
由于结果可能很大，你只需要输出这个答案mod 12345的值。

样例

input
2 output
73

数据范围与提示

时间限制：1s
空间限制：256MB

题目类型~

递推 

咻咻~

提交答案 状态 返回