CSES - Chuỗi Bit (Bit Strings)

Giới hạn thời gian: 1.00 s
Giới hạn bộ nhớ: 512 MB

Nhiệm vụ của bạn là đếm số lượng chuỗi bit có độ dài ~n~.

Ví dụ, nếu ~n = 3~, câu trả lời chính xác là 8, vì các chuỗi bit có thể là 000, 001, 010, 011, 100, 101, 110, và 111.

Đầu vào

Dòng đầu vào duy nhất có một số nguyên ~n~.

Đầu ra

In kết quả modulo ~10^9 + 7~.

Điều kiện

• ~1 ≤ n ≤ 10^6~

Ví dụ

Đầu vào:

3

Đầu ra:

8