Unique Binary Strings without Consecutive Ones

Given an integer N, count the number of unique binary strings of length N that do not contain consecutive 1s. Formally, we require that for any valid binary string s of length N, there should be no index i (1 ≤ i < N) such that s[i] = s[i+1] = 1.

The answer should be computed under modulo \(10^9+7\).

This problem can be solved using dynamic programming. Let \(dp0[i]\) denote the number of valid binary strings of length i that end with 0, and \(dp1[i]\) denote those ending with 1. The recurrence relations are:

• \(dp0[i] = dp0[i-1] + dp1[i-1]\)
• \(dp1[i] = dp0[i-1]\)

The final answer is \(dp0[N] + dp1[N]\), computed modulo \(10^9+7\>.

inputFormat

The input consists of a single integer N (1 ≤ N ≤ 10⁵ or more), which represents the length of the binary strings.

outputFormat

Output the number of unique binary strings of length N that do not contain consecutive 1s, modulo \(10^9+7\>.

3

5