824. Count Strings Without 3 Consecutive Same Characters (Modulo 10^9+7)

Count binary strings of length n with no 3 consecutive identical characters, mod 10^9+7. f(0)=1, f(1)=2, f(2)=4.

Input: A non-negative integer n.

Output: Integer mod 10^9+7.

Examples

Example 1

Input: 3
Output: 6
Explanation: All 8 except 000, 111 -> 6.

Example 2

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

Example 3

Input: 0
Output: 1
Explanation: Empty string.