Description

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

Input Format

Read in a number N.

Output Format

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

2

73