URI Online Judge | 1807 | [P2]

Triângulo Trinomial, a Vingança

Por M.C. Pinto, UNILA BR Brazil

Timelimit: 1

O triângulo trinomial é um triângulo numérico de coeficientes trinomiais. Ele pode ser obtido com uma linha contendo um único "1", a próxima linha contendo três 1 e cada elemento das linhas seguintes sendo calculado como a soma do elemento acima à esquerda, imediatamente acima e acima à direita:

A primeira linha do triângulo trinomial é numerada com zero, a segunda linha é a de número 1 e assim sucessivamente.

Sua tarefa é, dado um número de linha R, escrever um programa que exiba a soma de seus elementos. Por exemplo, a soma dos elementos da linha 2 é 9 = 1 + 2 + 3 + 2 + 1.

Mas desta vez o número de linha R pode ser muito maior! Sendo assim, a soma dos elementos da linha R deve ser mostrada módulo (231 - 1). Por exemplo, a soma dos elementos da linha 20 é 3486784401 mas a resposta a ser dada é 1339300754, que é congruente a 3486784401 módulo (231 - 1).

Entrada

A entrada é o número de linha R (0 ≤ R ≤ 999999999).

Saída

A saída é a soma módulo (231 - 1) de todos os elementos da linha R. Não esqueça do caractere de fim-de-linha após exibir a soma.

Exemplos de Entrada Exemplos de Saída

0

1

2

9

20

1339300754