eolymp
bolt
Try our new interface for solving problems
Problems

Three ones

Three ones

Time limit 1 second
Memory limit 128 MiB

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