Background

Special for beginners, ^_^

Description

这是一个涂色问题。现在有一张网格，一共 3 行，每行 $n$ 个。你需要用 3 种颜色给网格上色，需要确保相邻格子颜色不同。请问一共有多少种上色方案？答案对 $10^9+7$ 取模。

Format

Input

一个正整数 $n(1\le n\le 10^9)$。

Output

一个整数，表示方案数。

Samples

1

12

2

54

Limitation

1s, 1024KiB for each test case.