Competitions

# Three ones

Find the number of sequences of length n, consisting only of zeros and ones, that do not have three one's in a row.

#### Input

The length of the sequences n (1n105).

#### Output

Print the required number of sequences modulo 12345.

Time limit 1 second
Memory limit 128 MiB
Input example #1
1

Output example #1
2

Input example #2
4

Output example #2
13