5. Password
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Vasya has forgotten his password. All he remembers is that the password had a length of $$$n$$$ and consisted only of digits, with the condition that any two adjacent digits differed by no more than one.

Determine how many possible passwords Vasya would have to try to log into the system, assuming the correct password is the very last one he checks.

Input

A single integer $$$n$$$ ($$$2 \le n \le 25$$$) is provided, representing the length of the password.

Output

Output a single integer — the number of possible passwords of length $$$n$$$.

Scoring

Subtask 1 (up to 40 points): $$$n \le 10$$$

Subtask 2 (up to 60 points): $$$n \le 25$$$

Example
Input
2
Output
28