1365 - 位数问题

题目描述

在所有的 N 位数中,有多少个数中有偶数个数字 3 ?由于结果可能很大,你只需要输出这个答案对 12345 取余的值。

比如:在所有的 2 位数字,包含 03 的数有 72 个,包含 23 的数有 1个,共 73 个。(请注意:1 位数指 1 \sim 99 个数,不包含数字 0

输入

一个整数 N1 \le N \le 1000)。

输出

N 位数中含有偶数个数组 3 的个数。

样例

输入

2

输出

73
来源

递推

标签
题目参数
时间限制 1 秒
内存限制 16 MB
提交次数 522
通过人数 155
金币数量 2 枚
难度 基础


上一题 下一题