Xâu bit

Nguồn: CSES Problem Set

Đề bài

Nhiệm vụ của bạn là tính số lượng xâu bit có độ dài $n$.

Mỗi vị trí trong xâu bit có thể nhận một trong hai giá trị 0 hoặc 1.

Ví dụ, với $n=3$, có $8$ xâu bit khác nhau:

000, 001, 010, 011, 100, 101, 110 và 111.

Input

Dòng duy nhất chứa một số nguyên $n$ — độ dài của xâu bit.

Output

In ra số lượng xâu bit có độ dài $n$, lấy phần dư theo modulo $10^9+7$.

Subtask

• Subtask 1 — 20%: $1 \le n \le 20$.
• Subtask 2 — 30%: $1 \le n \le 10^6$.
• Subtask 3 — 50%: $1 \le n \le 10^{18}$.

Ví dụ

Input

3

Output

8

Giải thích

Với $n=3$, mỗi vị trí có thể là 0 hoặc 1.

Có tất cả $8$ xâu bit khác nhau:

000, 001, 010, 011, 100, 101, 110 và 111.

Vì vậy kết quả cần in ra là $8$.