CSES - Bit Strings | Xâu nhị phân

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
Flower_On_Stone , SPyofgame , Namlenam
Dạng bài
Điểm: 800 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Lần này bài tập bạn được giao là: hãy tính số lượng dãy bit có độ dài là \(n\).

Ví dụ: nếu \(n = 3\), thì câu trả lời đúng lẽ là \(8\), vì các dãy bit thoả mãn là 000, 001, 010, 011, 100, 101, 110, and 111.

Input

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

Output

  • In kết quả chia lấy dư cho \(10^9 + 7\).

Constraints

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

Example

Sample input

3

Sample output
8

Bình luận