Dino Game

Dohyeon, cramming in a hurry at the High-Tech Hall for an exam, runs into the no-internet-connection window again today!

Press the spacebar in that window to play the Dino Game. The rules of the Dino Game are as follows: the dinosaur keeps moving forward. Cacti appear randomly on the map as obstacles, and pressing the spacebar at the right time makes the dinosaur jump over a cactus. If you do not press the spacebar at the right time, the dinosaur hits a cactus and the game ends. In that case you get a score proportional to the game time. Dohyeon, whose motivation has dropped sharply, pressed the spacebar and played the Dino Game anyway, but the game was so easy in front of the physical ability he had built up by solving countless problems that the game simply would not end! Since the original Dino Game can in theory be played forever if you jump well, Dohyeon got bored, changed the rules as follows, and decided to count the number of maps he can clear.

• The length of the map is given as N. The map consists of N points, and each point is either the ground or a cactus (obstacle) of height 1 or 2. The starting point is 1, and the number denoting a point increases as the dinosaur moves forward.
• The dinosaur can jump over at most 2 adjacent cacti, and if the sum of the heights of two adjacent cacti is 4 or more, it cannot jump over them.
• Stepping on an obstacle right at the start means you cannot survive, so the starting point is always ground.
• If no cactus of height 2 appears on the map, it is too boring. Therefore at least one cactus of height 2 must appear.
• A map is defined as clearable if all of the above conditions hold and the dinosaur arrives at the virtual point N+1, whose state is fixed to ground, without hitting a cactus.
• If adjacent cacti exist, they must be jumped over all at once.

An example of a map that cannot be cleared. Cacti of height 2 appear consecutively at points 2 and 3, so the dinosaur hits a cactus.

Find the number of clearable maps and ease Dohyeon's boredom.

The length of the map $N$ (1 ≤ $N$ ≤ 1000) is given.

Print the number of maps that Dohyeon can clear while satisfying all of the above conditions.

The number can be very large, so print it modulo 1,000,000,007.

You can play the Dino Game when the internet connection is down in the Chrome browser, or by typing chrome://dino in the address bar.