SPOJ in Armenian

Պասկալի եռանկյունը թվերից կազմված անվերջ եռանկյուն է, որն ունի այսպիսի տեսք.

1

1  1

 1  2  1

  1  3  3  1

  1  4  6  4  1

  1  5 10 10  5  1

  1  6 15 20 15  6  1

  1  7 21 35 35 21  7  1

  ... ... ... ... ... ... ... ... ...

Պասկալի եռանկյան տողերը համարակալվում են զրոյից սկսած, յուրաքանչյուր տողում թվերը նույնպես համարակալվում են զրոյից սկսած։ Զրո համարի տողը պարունակում է մի թիվ՝ մեկ, իսկ յուրաքանչյուր հաջորդ տող պարունակում է նախորդից մեկ թիվ ավել։ Յուրաքանչյուր տողում առաջին և վերջին թվերը 1 են, իսկ մնացած թվերից յուրաքանչյուրը հավասար է նախորդ տողում այդ թվի վերևում գրված երկու թվերի գումարին։

Այսպիսով, i-րդ տողը պարունակում է i+1 թիվ։ Եթե i-րդ տողի j-րդ տարրը նշանակենք ai,j, ապա ստույգ է հետևյալ հավասարությունը. a_i,j = a_i-1,j-1 + a_i-1,j ։

Ձեր խնդիրն է պարզել, թե Պասկալի եռանկյան n-րդ տողում քանի կենտ թիվ կա։

Մուտքը

Մուտքում տրված է մի n բնական թիվ (0<= n<= 2 ·10⁹):

Ելքը

Ելքում հարկավոր է արտածել մեկ թիվ՝ Պասկալի եռանկյան n-րդ տողում կենտ թվերի քանակը։

Օրինակներ

Մուտքը.
0

Ելքը.
1

Մուտքը
5

Ելքը
4

Մուտքը
7

Ելքը
8