Define a full binary tree as a binary tree where all nodes, except the leaves, in the tree have ~2~ children (the leaves have ~0~). All nodes in levels except the bottom must have ~2~ children. The height is defined as the number of nodes in the path from the root to a leaf, including the root.

You are given a full binary tree with a height of ~N~ (~0 \leq N \leq 10^7~). Can you count the number of subtrees in the graph? Unlike the usual definition of subtree, a subtree is defined as being a subset of nodes (at least ~1~) and edges of the original tree that forms another valid tree.

Subtasks

Subtask 1 (5%)

~N \leq 6~

Subtask 2 (25%)

~N \leq 5 \cdot 10^5~

Subtask 3 (70%)

No further constraints.

Input Specification

A single integer, ~N~, the height of the full binary tree.

Output Specification

A single integer, the number of subtrees.

Since this number can be very large, output your number modulo ~10^9 + 7~.

Sample Input

2

Sample Output

6

Explanation for Sample

The sample asks for the number of subtrees in a full binary tree of height 2. The valid subtrees are as follows (where the original full binary tree is the rightmost):