Garden Flower Arrangements

You are given n garden beds. Each bed can be planted with either Tulips or Roses. However, no two adjacent beds can have the same type of flower.

The valid arrangements follow a recurrence relation. Let \(f(n)\) be the number of valid arrangements for \(n\) beds. It is given that:

\(f(1)=2,\quad f(2)=2,\quad f(n)=f(n-1)+f(n-2)\) for \(n \ge 3\).

Since the numbers can become large, output the answer modulo \(10^9+7\). For example:

• For \(n=1\), there are 2 arrangements.
• For \(n=3\), there are 4 arrangements.
• For \(n=4\), there are 6 arrangements.
• For \(n=10\), there are 110 arrangements.

Your task is to compute \(f(n)\) for a given \(n\).

inputFormat

The input consists of a single integer \(n\) denoting the number of garden beds.

Input is provided via standard input (stdin).

outputFormat

Output a single integer: the number of valid arrangements modulo \(10^9+7\), printed to standard output (stdout).

## sample

1

2