题目描述

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

输入格式

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

输出格式

一个整数，表示答案。

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

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

样例

input

2

output

73

## 限制与提示
时间限制：$1 \text {s}$

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