#2636. C++-递推算法-位数问题

C++-递推算法-位数问题

Background

Description

在所有的N位数(1<=N<=1000)中,有多少个数中有偶数个数字3(说明,0是偶数)

注:由于位数比较大的情况下,导致输出数据可能越界,因此,输出个数 % 12345 的结果

Format

Input

读入一个数N

Output

输出有多少个数中有偶数个数字3。

Samples

2
73
8
9577
1000
8452

Limitation

1s, 1024KiB for each test case.

Statistics

Related

In following contests:

递推算法

In following homework:

C++-递推算法