== include(page="template/taskheader" task_id="permheap") ==

Numim heap un arbore binar în care fiecare nod are informaţia asociată mai mare decât informaţiile afociate fiecăruia dintre fii săi. Astfel, putem reprezenta un heap printr-un vector în care elementele sunt memorate începând cu poziţia 1 iar fiii nodului de pe poziţia i sunt nodurile de pe poziţiile 2*i şi 2*i+1. Toate nivelurile arborelui sunt complete (fiecare nod are exact 2 fii), eventual cu excepţia ultimului nivel, care este însă completat din stânga.

Numim heap un arbore binar în care fiecare nod are informaţia asociată mai mare decât informaţiile afociate fiecăruia dintre fii săi. Astfel, putem reprezenta un heap printr-un vector în care elementele sunt memorate începând cu poziţia $1$ iar fiii nodului de pe poziţia $i$ sunt nodurile de pe poziţiile $2*i$ şi $2*i+1$. Toate nivelurile arborelui sunt complete (fiecare nod are exact $2$ fii), eventual cu excepţia ultimului nivel, care este însă completat din stânga.

Să se determine câte permutări ale mulţimii {1, 2, ... n} au structură de heap.

Să se determine câte permutări ale mulţimii ${1, 2, ... n}$ au structură de heap.

h2. Date de intrare

Fişierul $permheap.in$ conţine pe prima linie numărul natural n.

Fişierul $permheap.in$ conţine pe prima linie numărul natural $n$.

h2. Date de ieşire