Background

Description

在所有的N位数（1<=N<=8）中，有多少个数中有偶数个数字3（说明，0是偶数）

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

Format

Input

读入一个数N

Output

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

Samples

2

73

8

9577

Limitation

1s, 1024KiB for each test case.