Non-Consecutive Ones in Binary Strings

Given an integer ( n ), determine the number of distinct binary strings of length ( n ) that do not contain two consecutive 1's. The answer should be computed modulo ( 10^9+7 ). This problem can be solved using dynamic programming. In particular, let ( dp0 ) denote the number of valid strings of a given length ending with 0 and ( dp1 ) the number ending with 1. Then, the recurrence relations are given by ( dp0_{new} = dp0 + dp1 ) (since you can append a 0 to any valid string) and ( dp1_{new} = dp0 ) (you can append a 1 only to strings ending with 0).

inputFormat

A single integer ( n ) (( 1 \leq n \leq 10^5 ), for example) provided via standard input.

outputFormat

A single integer representing the number of valid binary strings of length ( n ) modulo ( 10^9+7 ), printed to standard output.## sample

1

2