Alien Creature Numbering

Time limit1sMemory limit256 MB

Summary

Count the labelings of a complete binary tree of height H with 1..2^(H+1)-1 where every parent's label is smaller than its children's labels, modulo 1e9+7.

Level: Medium6 of 10
Topics: Combinatorics, Tree, Dynamic programming
Solved: No attempts yet

Problem

Gimun found one unusual alien creature. It was newborn when he found it. One day after birth the creature produces exactly two offspring, and after that single birth it never produces any more. The two offspring of one parent are distinguished as the first child and the second child.

So on day 0 after the discovery there is 1 creature, on day 1 there are $1 + 2 = 3$ , and on day 2 there are $1 + 2 + 4 = 7$ . In general, on day $H$ there are $2^{H+1} - 1$ creatures.

Gimun wants to number the creatures on day $H$ . He uses each of the numbers $1$ through $2^{H+1} - 1$ exactly once, and the number of a parent must always be smaller than the number of each of its children. Count the numberings.

Input

The first line contains an integer $H$ ( $0 \le H \le 10$ ), meaning that $H$ days have passed since the discovery.

Output

Print the number of valid numberings modulo 1,000,000,007 on one line.

Hint

For $H = 1$ there are 3 creatures, one parent and two children. The parent's number must be smaller than both children's numbers, so the parent takes 1, and the remaining numbers 2 and 3 go to the first and second child in either order. The answer is 2.

Examples2

Example 1
Input
```
1
```
Expected output
```
2
```
Example 2
Input
```
2
```
Expected output
```
80
```