Description

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

Input Format

Read in a number N.

Output Format

Output how many numbers have an even number of digit 3.

```input1 2 ``` ```output1 73 ``` ## Hint

【Data Scale】

1 ≤ N ≤ 1000

【Sample Explanation】

Among all 2-digit numbers, there are 72 numbers containing 0 instances of digit 3, and 1 number containing 2 instances of digit 3, totaling 73 numbers.

Source

CodesOnline