G. Крош и снова подсчет массивов
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Крош называет массив длины $$$n$$$ интересным, если он состоит из $$$n$$$ чисел, каждое из которых принимает значение от $$$0$$$ до $$$9$$$ и их сумма делится на $$$3$$$. Помогите ему посчитать количество интересных массивов длины $$$n$$$.

Входные данные

Вам дано число $$$1 \le n \le 300000$$$ - длина массива.

Выходные данные

Выведите ответ на задачу.

Пример
Входные данные
1
Выходные данные
4