Bit Strings

Source: CSES

Version: Phuoc Hung OJ Extended

Problem Statement

Given n, count binary strings of length n. Each position independently offers 0 or 1, so compute 2^n modulo 1000000007. Do not construct or print any strings. The original CSES 1617 n range is preserved.

Input

One integer n with 1<=n<=1000000.

Output

Print 2^n modulo 1000000007 followed by LF.

Subtasks

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

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

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

Examples

Example 1

Input:

3

Output:

8

Explanation:

Two independent choices per position; double and reduce modulo n times. Exact input: "3\n"; exact output: "8\n".

Example 2

Input:

1

Output:

2

Explanation:

Two independent choices per position; double and reduce modulo n times. Exact input: "1\n"; exact output: "2\n".

Example 3

Input:

1000000

Output:

235042059

Explanation:

Two independent choices per position; double and reduce modulo n times. Exact input: "1000000\n"; exact output: "235042059\n".