The Digit Problem

Problem Background

Special for beginners, ^_^

Problem Description

Among all $N$-digit numbers, how many have an even number of digit $3$? Since the result may be very large, you only need to output this answer modulo $12345$.

Input Format

Read a number $N$ ($1\le N \le 1000$).

Output Format

Output how many numbers contain an even number of digit $3$.

Sample Input 1

2

Sample Output 1

73

Hint

Among all $2$-digit numbers, $72$ have $0$ digit $3$ and $1$ has $2$ digits $3$, for a total of $73$.

Constraints

1s, 1024KiB for each test case.