Xâu nhị phân (Bit Strings)

Nguồn: CSES

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho số nguyên $n$. Có đúng $2^n$ xâu nhị phân độ dài $n$ vì mỗi vị trí được chọn độc lập là 0 hoặc 1. Hãy tính $2^n\bmod 1000000007$. Không tạo hoặc in các xâu. Sau mỗi phép nhân với 2 phải lấy modulo để giữ giá trị trung gian trong miền an toàn. Bài này giữ đúng miền $n$ của CSES 1617.

Input

Một số nguyên $n$, với $1\le n\le 1000000$.

Output

In giá trị $2^n\bmod 1000000007$ và LF.

Subtask

• Subtask 1 (20%): $1\le n\le 20$.

• Subtask 2 (30%): $1\le n\le 1000$.

• Subtask 3 (50%): $1\le n\le 1000000$.

Ví dụ

Ví dụ 1

Input:

3

Output:

8

Giải thích:

Mỗi vị trí có 2 lựa chọn độc lập; nhân 2 và lấy modulo n lần. Input thực tế: "3\n"; Output thực tế: "8\n".

Ví dụ 2

Input:

1

Output:

2

Giải thích:

Mỗi vị trí có 2 lựa chọn độc lập; nhân 2 và lấy modulo n lần. Input thực tế: "1\n"; Output thực tế: "2\n".

Ví dụ 3

Input:

1000000

Output:

235042059

Giải thích:

Mỗi vị trí có 2 lựa chọn độc lập; nhân 2 và lấy modulo n lần. Input thực tế: "1000000\n"; Output thực tế: "235042059\n".