Xâu nhị phân là xâu chỉ chứa ~0~ và ~1~. Các xâu nhị phân có độ dài bằng ~n~ có ~2^n~ xâu nhị phân. Hãy đếm xem có bao nhiêu xâu nhị phân có độ dài ~n~.

Yêu cầu: Tính xem có bao nhiêu xâu nhị phân có độ dài ~n~.

Input

Nhập một số tự nhiên ~n~ (~n \leq 10^6~).

Output

Một đáp án - số lượng xâu nhị phân có độ dài ~n~ modulo ~10^9+7~.

Scoring

• Subtask ~1~ ~(20\%)~: ~(n \leq 20)~;
• Subtask ~2~ ~(80\%)~: ~(n \leq 10^6)~.

Example input 1

3

Example output 2

8

Note 1

• Có ~8~ xâu nhị phân có độ dài ~3~ là: ~000~, ~001~, ~010~, ~011~, ~100~, ~101~, ~110~, ~111~.