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