Salesforce OA-2 2023

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