Permutacions alternades P45941


Statement
 

pdf   zip

thehtml

Diem que una permutació p1, …, pn de {1,…,n} és alternada si, per a tot i, 2 ≤ in−1, es té pi−1 < pi > pi+1 o bé pi−1 > pi < pi+1. És a dir, quan un element és més gran que l’anterior, el següent és més petit, i viceversa.

Quantes permutacions de {1,…,n} són alternades?

Entrada

L’entrada consisteix en diversos enters n entre 1 i 1000.

Sortida

Per a cada n, escriviu el nombre de permutacions alternades de {1,…,n}. Com la resposta pot ser força gran, feu els càlculs mòdul 109 + 7.

Public test cases
  • Input

    1
    2
    3
    4
    14
    15
    1000
    

    Output

    1
    2
    4
    10
    398721962
    807514603
    238541541
    
  • Information
    Author
    Jordi Rodríguez
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++