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.
Subtask 1 (5%)
~N \leq 6~
Subtask 2 (25%)
~N \leq 5 \cdot 10^5~
Subtask 3 (70%)
No further constraints.
A single integer, ~N~, the height of the full binary tree.
A single integer, the number of subtrees.
Since this number can be very large, output your number modulo ~10^9 + 7~.
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):