780. Count Binary Strings Without Consecutive 1s (Modulo 10^9+7)

Given a non-negative integer n, return the number of binary strings of length n that do NOT contain two consecutive '1' characters, taken modulo 10^9 + 7. If n == 0, return 1 (the empty string counts). Implement with recursion + memoization.

Input: A single non-negative integer n.

Output: Return an integer count mod 10^9 + 7.

Examples

Input: 3
Output: 5
Explanation: 000, 001, 010, 100, 101.

Input: 1
Output: 2
Explanation: 0, 1.

Input: 0
Output: 1
Explanation: Empty string.

Constraints

• 0 <= n <= 1000

Asked by