Sân gạch đen trắng

Một sân hình chữ nhật gồm \(2\) hàng và \(n\) cột ô vuông. Mỗi ô được lát đúng một viên gạch, màu trắng hoặc màu đen. Để sân trông đẹp mắt, không được có hai ô gạch đen nào chung cạnh với nhau (hai ô chung cạnh là hai ô kề nhau theo hàng ngang hoặc hàng dọc).

Hãy đếm số cách tô màu các ô của sân thoả mãn điều kiện trên. Hai cách là khác nhau nếu tồn tại một ô mà ở cách này là trắng còn ở cách kia là đen. Vì kết quả có thể rất lớn, hãy in ra phần dư của nó khi chia cho \(1\,000\,000\,007\).

Input

Một số nguyên duy nhất \(n\).

Output

In ra số cách tô màu, lấy dư theo \(1\,000\,000\,007\).

Constraints

• \(1 \le n \le 1000\)

Sample Input 1

2

Sample Output 1

7

Sample Input 2

4

Sample Output 2

41

Sample Input 3

6

Sample Output 3

239

Explanation

Với \(n = 2\) có \(2^4 = 16\) cách tô, trong đó chỉ \(7\) cách không có hai ô đen kề nhau: tất cả trắng, bốn cách có đúng một ô đen và hai cách có hai ô đen nằm chéo nhau.