本题没有可用的提交语言。

Description

Hilbert is lucid dreaming. In his dream, he attempts to use one drop of batter to fry a pancake that fills his entire square pan. Fortunately, he is rational enough to believe there is insufficient batter to do this, so instead he decides to cast a magic spell. The spell consists of $n$ iterations, where on each iteration the current shape of the pancake will be copied into the four equal regions of the pan, and the bottom two will be rotated 90 degrees inwards. After connecting the four regions together, the resulting transformation can be seen stretching the pancake into progressively smaller segments until it fills up the whole pan. Hilbert is interested in figuring out how many segments there are on the $nth$ iteration, mod 1000000007.

Input

The input contains one integer $1 \leq n\leq 10^5$, the number of iterations.

Output

Please print one integer, the number of segments that the pancake contains after iteration $n$, in mod 1000000007.

2

32

13

665875208

Note

In the first sample, the pancake starts out like this:

On the first iteration, the pancake fills cells (1,1) to (2,2). We connect cells (2,2) to (2,3) and (2,1) to (3,1) and (4,2) to (4,3). Coordinate (1, 1) here is in the top left, and the coordinates are written in row-column order.

On the second iteration, we again make four copies, and connect cells (4,4) to (4,5) and (4,1) to (5,1) and (4,8) to (5,8).

There are 3 and 13 segments (mod 1e9+7) on the first and second iteration respectively.