Light Arrangement

Given an integer \( n \), determine the number of ways to arrange lights on \( n \) lamp posts such that no two consecutive lamp posts are both lit. Each lamp post can either have a light installed or not.

This can be modeled using the recurrence relation:

\( dp[n] = dp[n-1] + dp[n-2] \)

with base cases \( dp[1] = 2 \) and \( dp[2] = 3 \). All results should be computed modulo \( 10^9+7 \), i.e. modulo \( 1000000007 \).

inputFormat

The input consists of a single integer \( n \) where \( 1 \le n \le 100000 \), representing the number of lamp posts.

outputFormat

Output a single integer – the number of valid arrangements of lights on the lamp posts, computed modulo \( 1000000007 \).

1

2