408033: GYM102964 G Krosh and count arrays problem 2

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

G. Krosh and count arrays problem 2time limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard 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$$$.

ExampleInput
1
Output
4

加入题单

上一题 下一题 算法标签: