Count Valid Paint Sequences

You are given a positive integer ( n ) representing the number of blocks. Each block must be painted using one of two colors. A sequence of painted blocks is considered valid if no two adjacent blocks are painted the same color. Your task is to compute the number of valid painting sequences modulo (10^9+7).

For ( n \ge 1 ), the total number of valid sequences is given by (2^{n-1}). For example, when ( n = 1 ), there are 2 valid sequences, and when ( n = 3 ), there are (2^{2} = 4) valid sequences.

Make sure your program reads the input from standard input (stdin) and writes the answer to standard output (stdout).

inputFormat

The input consists of a single integer ( n ) (( 1 \le n \le 10^9 )) provided via standard input.

outputFormat

Output a single integer representing the number of valid paint sequences modulo (10^9+7), printed to standard output.## sample

1

2