题目描述

请编程求出所有的 $n$ 位数中，有多少个数中有偶数个数字 $3$。结果模 $12345$。（$1 \leq n \leq 1000$）

输入格式

一行一个正整数 $n$，$0 < n < 1000$。

输出格式

一行一个正整数，表示 $n$ 位数中有多少个数有偶数个 $3$。

样例

输入

2

输出

73

数据范围与提示

无