Chuỗi bit

Trong một buổi gặp gỡ đặc biệt với Thủ tướng, FullHouse Dev được đưa ra một bài toán thú vị để kiểm tra khả năng tư duy logic của họ. Bài toán liên quan đến việc tính toán số lượng chuỗi bit có độ dài nhất định. Với tinh thần ham học hỏi và mong muốn gây ấn tượng với Thủ tướng, FullHouse Dev đã bắt đầu phân tích và giải quyết vấn đề này.

Bài toán

Nhiệm vụ của FullHouse Dev là tính toán số lượng chuỗi bit có độ dài \(n\).

INPUT FORMAT:

• Dòng duy nhất chứa một số nguyên \(n\).

OUTPUT FORMAT:

• In ra kết quả theo modulo \(10^9 + 7\).

Ràng buộc:

• \(1 \leq n \leq 10^6\)

Ví dụ

INPUT

3

OUTPUT

8

Giải thích

Với \(n = 3\), có 8 chuỗi bit khác nhau có thể tạo ra: 000, 001, 010, 011, 100, 101, 110, 111. Vì vậy, kết quả là 8.