Fie n un numar natural.
Numim sir 2-3-monoton de lungime n un sir s₁, s₂, ..., s_n, format din n elemente ale multimii {1, 2, ..., n} care verifica urmatoarele doua relatii:
1. s_i<s_i+2, pentru orice i din {1, 2, ..., n-2}
2. s_i<s_i+3, pentru orice i din {1, 2, ..., n-3}

Cerinta

Scrieti un program care sa determine numarul de siruri 2-3-monotone de lungime n.

Date de intrare

Fisierul de intrare sir23.in contine un singur numar, lungimea n.

Date de iesire

Fisierul de iesire sir23.out va contine pe prima linie ultimele 4 cifre din numarul de siruri 2-3-monotone de lungime n.

Restrictii

• n numar natural, 1 <= n <= 100
• In cazul în care ultimele 4 cifre din numarul de siruri 2-3-monotone încep cu zerouri, acestea nu vor fi afisate.

Exemple

prof. Emanuela Cerchez
Liceul de Informatica "Grigore Moisil" Iasi