时间限制：1秒　　内存限制：256M

---

【题目描述】

　　在所有的 \(N\) 位数中，有多少个数中有偶数个数字 3？

【输入格式】

　　干组测试数据，每组测试数据占一行，包含一个整数 \(N\)。

【输出格式】

　　每次数据输出一行，含一个整数，表示 \(N\) 位数中含偶数个 3 的数的个数 \(mod\ 12345\)。

【输入输出样例】

　Input

1
2
3
4
5
6

　Output

9
73
674
6292
9956
9163

【数据限制】

　　对于 \(10\%\) 的数据，\(1≤N≤6\)
　　对于 \(50\%\) 的数据，\(1≤N≤3000\)
　　对于 \(100\%\) 的数据，\(1≤N≤1000000\)，每个测试点最多不超过5000组测试数据。

【来源】

　　Mr.he