Có một khoảng sân hình chữ nhật kích thước \(2 \times N\) \((1 \le N \le 10^3)\) ô vuông, gồm \(2\) hàng và \(N\) cột. Đánh số hàng từ \(1\) đến \(2\) theo thứ tự từ trên xuống dưới, đánh số cột từ \(1\) đến \(N\) theo thứ tự từ trái qua phải. Người ta muốn lát sân bằng gạch màu trắng và điểm xuyết một số ô gạch màu đen, mỗi ô vuông được lát bởi một viên gạch, sao cho không có hai viên gạch màu đen nào chung cạnh với nhau.

Hỏi có tất cả bao nhiêu cách khác nhau để lát khoảng sân trên (hai cách lát sân được gọi là khác nhau nếu tồn tại tối thiểu một ô ở dòng \(i\) cột \(j\) được lát gạch màu trắng ở cách này và lát gạch màu đen ở cách kia).

Ví dụ \(n=2\) ta có \(7\) cách lát sân sau đây:

Dữ liệu vào

• Là một số nguyên \(N\)

Dữ liệu ra

• Là số cách lát gạch khoảng sân theo yêu cầu trên. Số lượng này có thể rất lớn nên chỉ cần in lấy dư cho \(10^9+7\).

Input 1

1

Output 1

3

Input 2

3

Output 2

17

Input 3

5

Output 3

99