Se consideră un număr natural k si n = 1+2+...+k = k*(k+1) div 2. Luând o permutare oarecare p=(p₁,p₂,...p_n) a multimii {1,2,...,n}, acestea se asază pe k linii astfel: pe prima linie se pune p₁, pe a doua linie p₂ si p₃, pe a treia linie p₄,p₅,p₆, ..., pe linia k se asază ultimele k numere din permutare. De exemplu, pentru k=3 (deci n=6) si permutarea (2,4,3,1,6,5) asezarea pe 3 linii este:
2
4 3
1 6 5

După asezarea numerelor se determină valorile m₁,m₂,...,m_k, unde, pentru i=1..k, unde m_i memorează valoarea maximă de pe linia i. În exemplul de mai sus m₁=2, m₂=4, m₃=6.

Cerinţă

Pentru un număr natural k dat, să se determine numărul permutărilor multimii {1,2,…,n} care au proprietatea că m₁<m₂<…<m_k. Pentru că acest număr poate fi foarte mare, se va calcula modulo 1000000007.

Date de intrare

Fişierul de intrare permtr.in conţine pe prima linie numărul natural k.

Date de ieşire

Fişierul de ieşire permtr.out va conţine pe prima linie un singur număr natural reprezentând numărul permutărilor care au proprietatea cerută, modulo 1000000007.

Restricţii

• 2 <= k <= 5000
• Pentru 50% din teste, k <= 50

Exemplu

permtr.in	permtr.out	Explicaţii
2	4	k=2, deci n=3. Cele 4 permutări ale multimii {1,2,3} sunt: 1,2,3 1,3,2 2,1,3 2,3,1

prof. Dan Pracsiu

Liceul "Stefan Procopiu" Vaslui

dpracsiu@yahoo.com