P408033 - GYM102964 G Krosh and count arrays problem 2 - SSOJ

Memory Limit：256 MB Time Limit：2 S

Judge Style：Text Compare Creator：

Submit：0 Solved：0

上一题 Submit 下一题 Submit Record Statistics MD

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

Output

Krosh Kaliningrad Contest 1

408033: GYM102964 G Krosh and count arrays problem 2

Description

Source/Category

加入题单