Count Magical Strings

Given a positive integer N, count the number of Magical Strings of length N. A Magical string is defined as a string consisting of only the characters 'a' and 'b' and does not contain two consecutive 'a's.

The answer must be computed modulo (10^9+7).

For example, if N = 3, the valid Magical strings are: aba, abb, bab, bba, bbb, so the output is 5.

inputFormat

The input contains a single integer N (1 \leq N \leq 10^5), representing the length of the string.

outputFormat

Output a single integer, the number of Magical Strings of length N modulo (10^9+7).## sample

1

2