URI Online Judge | 1807 | [P2]

Trinomial Triangle, the Revenge

By M.C. Pinto, UNILA BR Brazil

Timelimit: 1

The trinomial triangle is a number triangle of trinomial coefficients. It can be obtained by starting with a row containing a single "1" and the next row containing three 1s and then letting subsequent row elements be computed by summing the elements above to the left, directly above, and above to the right:

The first row of the trinomial triangle is numbered as zero, the second row is numbered as one and so on.

Given the row number R, you are asked to write a program that prints the sum of its elements. For instance, the sum of elements at row 2 is 9 = 1 + 2 + 3 + 2 + 1.

But this time the row number R can be much bigger! Thereby the sum of elements at row R must be printed modulo (231 - 1). For instance, the sum of elements at row 20 is 3486784401 but the expected answer is 1339300754, which is congruent to 3486784401 modulo (231 - 1).

Input

The input is the row number R (0 ≤ R ≤ 999999999).

Output

The output is the sum modulo (231 - 1) of all elements at row R. Don't forget the end-of-line character after printing the sum.

Input Samples Output Samples

0

1

2

9

20

1339300754