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

8