1347. Count Strings Without Consecutive 1s

Count the binary strings of length n that contain no two consecutive 1s. Return the count modulo 1000000007.

Input: A JSON object {"n": <string length>}.

Output: Return the number of valid binary strings modulo 1000000007.

Examples

Example 1

Input: {"n":3}
Output: 5
Explanation: Five length-3 strings avoid consecutive 1s.

Example 2

Input: {"n":5}
Output: 13
Explanation: Thirteen length-5 strings avoid consecutive 1s.