Pujant i baixant P61152


Statement
 

pdf   zip

Feu un programa que compti el nombre de maneres d’anar des de (0,0)(0, 0) fins a (n,0)(n, 0) fent només passos unitaris cap a la dreta, ja siguin horitzontals, en diagonal cap amunt, o en diagonal cap avall. A més, en cap moment es pot passar per sota del nivell del terra.

Per exemple, per a n=3n = 3 hi ha quatre solucions:

(20,3) (0.5,0.5)(4.5,1) (5.5,0.5)(9.5,1) (10.5,0.5)(14.5,1) (15.5,0.5)(19.5,1) (1,1)(2,2) (2,2)(3,2) (3,2)(4,1) (1,1)0.1 (2,2)0.1 (3,2)0.1 (4,1)0.1 (6,1)(7,2) (7,2)(8,1) (8,1)(9,1) (6,1)0.1 (7,2)0.1 (8,1)0.1 (9,1)0.1 (11,1)(12,1) (12,1)(13,2) (13,2)(14,1) (11,1)0.1 (12,1)0.1 (13,2)0.1 (14,1)0.1 (16,1)(17,1) (17,1)(18,1) (18,1)(19,1) (16,1)0.1 (17,1)0.1 (18,1)0.1 (19,1)0.1

Entrada

L’entrada consisteix en diversos casos, cadascun amb una nn entre 0 i 2000.

Sortida

Per a cada cas, escriviu el nombre de camins vàlids mòdul 108+710^8 + 7.

Public test cases

  • Input

    0
1
2
3
4
5
21
2000

    Output

    1
1
2
4
9
21
42547552
61201932
    • Information
    Author
    Enric Rodríguez
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++