Banana Tunnels and Convex Polygons

Rintaro owes Mayuri one banana. To keep Mayuri quiet, they made a wager: if Mayuri correctly solves the following problem, she may have as many bananas as she likes.

There are N secret tunnels. The i-th tunnel has length i. A mysterious mechanism selects a subset of these tunnels uniformly at random from the 2^N possible subsets (the empty set is also considered a valid selection). If the chosen tunnels can form a convex polygon, then the weight of this selection is defined as the number of tunnels selected; otherwise the weight is 0.

A set of segments can form a convex polygon if and only if the longest segment is less than the sum of the remaining segments. Note that at least 3 tunnels are required to form a polygon.

Your task is to compute, modulo 10⁹+7, the expected weight (i.e. the average weight) of the randomly chosen subnet of tunnels. Formally, if S is the set of all 2^N subsets and w(s) is the weight of subset s, you are to compute

\(E = \frac{\sum_{s \in S} w(s)}{2^N}\) mod \(10^9+7\). \(E\) is computed under modular arithmetic by multiplying \(\sum w(s)\) with the modular inverse of \(2^N\) modulo \(10^9+7\).

Input constraints: The input consists of a single integer N (1 ≤ N ≤ [small constraint]) representing the number of tunnels.

inputFormat

The input contains a single integer N, the number of secret tunnels.

outputFormat

Output the expected weight modulo 10⁹+7.

sample

4

937500007