Permutacions alternades P45941


Statement
 

pdf   zip

thehtml

Diem que una permutació p1, …, pn de {1,…,n} és alternada si, per a tot i, 2 ≤ i ≤ n−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++