Problem 1796. -- 位数问题

1796: 位数问题

Time Limit: 1 Sec  Memory Limit: 128 MB   64bit IO Format: %lld
Submitted: 346  Accepted: 156
[Submit][Status][Web Board]

Description

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

Input

包含多组测试数据,每组测试数据包含一个整数n。

Output

每组测试数据输出占一行,包含一个整数,即有多少个数中有偶数个数字3。

Sample Input

2

Sample Output

73

Source

[Submit][Status][Web Board]