Find the number of sequences of length n, consisting only of zeros and ones, that do not have three one's in a row.
The length of the sequences n (1≤n≤105).
Print the required number of sequences modulo 12345.