COCI Problem Selection

In the COCI contest, the problem setters must choose exactly (N) problems for the next round, one per each difficulty level from (1) to (N). Each problem has a fixed difficulty. However, some problems are ambiguous: they can be considered as having one of two consecutive difficulties. For example, an ambiguous problem might be considered as having difficulty (3) or (4). Note that no problem may be used more than once. Two selection methods are considered different if there is at least one problem that is assigned a different difficulty in the two methods.

Formally, for each difficulty (d) ((1 \le d \le N)) there is a fixed problem available (which can only be used for difficulty (d)). In addition, for each (i) from (1) to (N-1) there is an ambiguous problem that can be used either for difficulty (i) or (i+1). A valid selection consists of choosing exactly one problem for each difficulty from (1) to (N) (using each problem at most once). It can be shown that the total number of valid selections (f(N)) satisfies

[ f(1) = 1, \quad f(2) = 3, \quad \text{and for } n \ge 3, \quad f(n) = 2,f(n-1) + 2,f(n-2) \quad (\bmod; 10^9+7). ]

Your task is to compute (f(N) \bmod (10^9+7)).

inputFormat

The input consists of a single integer (N) (1 (\le) N (\le) 10^9) representing the number of problems (and difficulty levels).

outputFormat

Output a single integer: the number of different ways to select the problems modulo (10^9+7).

sample

1

1