Salesforce OA 2023 - A Game Of Cricket

Problem Description

In the game of cricket, players can score runs by hitting the ball delivered by another player (the bowler) and running between designated spots (wickets).

Suppose a player is only allowed to score 1, 2, 4, or 6 runs on any ball. How many ways can the player score N runs without hitting consecutive 4s?

Print the result modulo (10^9 + 7).

Input Format

• The input consists of a single integer N — the number of runs to be scored.
  (1 <= N <= 10^6)

Output Format

• Output a single integer — the number of ways to score N runs without hitting consecutive 4s, modulo (10^9 + 7).

Constraints

• No consecutive 4s are allowed in the sequence of runs scored.

Sample Input

6

Sample Output

19