A Game Of Cricket :
Difficulty Level : Easy
Submissions : 478
Asked In :
Marks :10
: 7 | : 1
In the game of cricket, players can score runs by hitting the ball delivered at them(by another player called bowler) and running between designated spots(wickets).
Suppose if a player is only allowed to score 1,2,4 and 6 runs in a ball. How many ways can the player score $$$N$$$ runs without hitting consecutive 4s?
Print the answer modulo $$$10^9+7$$$.
Input
The first line of input consists of a single integer $$$N$$$ - the number of runs to be scored. $$$(1 \leq N \leq 10^6)$$$
Output
The output consists of a single integer - the number of ways $$$N$$$ runs can be scored without hitting consecutive 4s. Print the answer modulo $$$10^9+7$$$
Example
Input
6
Output
19
