Problems
Three ones
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.
\InputFile
The length of the sequences $n~(1 \le n \le 10^5)$.
\OutputFile
Print the required number of sequences modulo $12345$.
Input example #1
1
Output example #1
2
Input example #2
4
Output example #2
13