题目描述

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

输入格式

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

样例数据

input

2

output

73

数据规模与约定

时间限制：$1 \text {s}$

空间限制：$256 \text {MB}$

注：

0个3也是偶数个3，但是1位数里不包含0.

由于结果可能很大，你只需要输出这个答案mod 12345的值。