Competitions

# January 19,20. One-dimentional Dynamic Programming

# 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

The length of the sequences **n** (**1** ≤ **n** ≤ `10`

).^{5}

#### Output

Print the required number of sequences modulo **12345**.

Input example #1

1

Output example #1

2

Input example #2

4

Output example #2

13