URI Online Judge | 1807 | [P2]

Triángulo Trinomial, la Venganza

Por M.C. Pinto, UNILA BR Brazil

Timelimit: 1

El triángulo trinomial es un triángulo numérico de coeficientes trinomiales. Este triángulo puede ser obtenido a partir de una fila que contiene un único "1", la siguiente fila contiene tres "1" y cada elemento de las filas siguientes se calcula sumando los elementos que están arriba a la izquierda, inmediatamente arriba y arriba a la derecha:

La primera fila del triángulo trinomial se numera con cero, la segunda fila es la número 1 y así sucesivamente.

Su tarea es, dado un número de fila R, escribir un programa que muestre la suma de sus elementos. Por ejemplo, la suma de los elementos de la fila 2 es 9 = 1 + 2 + 3 + 2 + 1.

Pero esta vez el número de línea R puede ser mucho más grande! Por lo tanto, la suma de los elementos de la línea R debe ser mostrada módulo (231 - 1). Por ejemplo, la suma de los elementos de la línea 20 es 3486784401 pero la respuesta debe ser dado 1339300754, que es congruente con el 3486784401 módulo (231 - 1).

Entrada

La entrada es el número de fila R (0 ≤ R ≤ 999999999).

Salida

La salida es la suma módulo (231 - 1) de todos los elementos de la fila R. No olvide el caracter de fin de línea luego de exhibir la suma.

Ejemplos de Entrada Ejemplos de Salida

0

1

2

9

20

1339300754