Fişierul intrare/ieşire:permheap.in, permheap.outSursăPreOJI 2017
AutorMarius NicoliAdăugată demariusn01Marius Nicoli mariusn01
Timp execuţie pe test0.2 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Permheap

Numim heap un arbore binar în care fiecare nod are informaţia asociată mai mare decât informaţiile asociate 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 (nodurile de pe acelaşi nivel ni le imaginăm aşezate de la stânga la dreapta, în ordine crescătoare a poziţiilor lor). Toate nivelurile arborelui sunt complete (fiecare nod are exact 2 fii), eventual cu excepţia ultimului nivel, care este însă completat din stânga (adică întâi frunzele de pe poziţii mai mici).

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

Date de intrare

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

Date de ieşire

Fişierul permheap.out conţine pe primul rând un număr natural reprezentând valoarea cerută, modulo 666013.

Restricţii

  • 1 ≤ n ≤ 200000

Exemplu

permheap.inpermheap.out
4
3

Explicaţie

4 2 3 1, 4 3 1 2, 4 3 2 1

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?