G. Krosh and count arrays problem 2
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Krosh calls an array of length $$$n$$$ interesting if it consists of numbers from $$$0$$$ to $$$9$$$ and sum of array is divisible by $$$3$$$. Help him to count number of interesting arrays of length $$$n$$$.

Input

You are given number $$$1 \le n \le 300000$$$.

Output

Output amount of interesting arrays of length $$$n$$$.

Example
Input
1
Output
4