Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

HS11BULH - Building allowance

Last week a new street in Bitland was constructed. You, as the city's building manager, are now responsible for a very important task. You have to decide on which plots along the street it is allowed to build new buildings. In order to this, you want to calculate first the number of possible ways of assigning free plots to buildings with the restriction that no 2 consecutive plots exist on which it is allowed to build - you want to give the inhabitants the feeling that they have more free room. The street is divided into N sections. Each section corresponds to 2 plots, one on each side of the street. Find the number of possible assignments subject to the given restriction modulo 1,000,000,007. 

Input

In the first line you're given N  ( N ≤ 231 - 1 ).

Output

In the first and only line output the result modulo 1,000,000,007.

Example

Input:
3

Output:
25

Example explanation:

If we just look at the one street side and mark B as a plot where building is allowed and F as a free plot, we have: BFB, FBF, FFB, BFF, FFF.

Since the same number exists on the other side, we have 5*5 = 25 combinations.

Scoring

By solving this problem you score 10 points.


Added by:Damir Ferizovic
Date:2011-10-14
Time limit:0.306s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: CLOJURE ICK PERL6
Resource:High School Programming League 2011/12

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.