You are given two types of people, type A and type B. You need to place n people of any type but the condition is that no two A type people is close to each other, means [A,A,B,A,B] not possible since two A type person are close to each other. You need to find all the possible arrangement. Print the answer modulo 1e9 + 7.

Constraints

1 <= n <= 100000

Input: 3 Output: 5

Explanation: if n = 3 then possible combinations are [B,B,B] [A,B,B] [B,A,B] [B,B,A] [A,B,A]

So the answer is 5.