A Counting Problem 3

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 1.0s
Memory limit: 128M

Problem types

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.

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


Sample Output


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):


There are no comments at the moment.