Count number of strings of length N with following properties:

A. Consists of char ‘A’ and ‘B’ only.

B. There is atleast one occurrence of 3 consecutive Bs.

Input: Only line having integer N.

Output: Number of string with given properties. As then number can be very large print it with modulo 10^9+7.

Sample Input 1:

3

Sample Input 2:

1

Explanation: Only possible string “BBB”