Background

Special for beginners, ^_^

Description

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

Format

Input

读入一个数$\,N\,(1\le N \le 1000)$。

Output

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

Samples

2

73

Hint

在所有的$\,2\,$位数字，包含$\,0\,$个$\,3\,$的数有$\,72\,$个，包含$\,2\,$个$\,3\,$的数有$\,1\,$个，共$\,73\,$个。

Limitation

1s, 1024KiB for each test case.