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, và 111.

Input

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

Output

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

Example

3

8