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 ≤
Print the required number of sequences modulo 12345.
Input example #1
Output example #1
Input example #2
Output example #2