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.

This question was asked in Infosys test (2022).

Wael has a sequence S. He found that the sub-sequences of S that are derived from S after deleting exactly two letters are considered as beautiful subsequences.

Given string S, your task is to find the number of different beautiful subsequences of S. Since the answer can be very large return it modulo 10^9 + 7.

Input Format:

The first line contains a string S, denoting the given sequence.

Constraints:

1 <= len(S) <= 10^6

Sample Input:

1. aa --> 1 (The only beautiful sub-sequence is empty sequence)

2. bccb --> 4 (we can get {bc,cb,cc,bb} so answer is 4)

3. bbbbbb --> 1 (the only possible sub-sequence is bbbb, so answer is 1)