Problem R
Hola Íslenskra Fræða

A decision has finally been made regarding the hole which now bears the name Hola Íslenskra Fræða (e. The Pit of Icelandic Studies). It has been decided that the building will never be finished, but something has to be done since at this rate it will be declared a national monument. The solution to this amusing problem is to dig a deeper pit! Your job is to assist in the planning of pit-digging the next two days while the position is being filled. You are to be supervising $n$ employees which are to be digging $n$ smaller pits in the larger pit. You also have access to a number of pumps since, as per usual, it’s raining in Reykjavík. Since you didn’t show up until around lunch on your first day the employees had already lined themselves up in the pit and began digging $n$ smaller pits. Thus you now need to make two decisions. The first decision is to choose which holes to assign pumps to. You have more than enough pumps for all holes so you can put pumps on as many of the holes as you want, but not more than one pump on a single hole. The catch is that the pumps are so loud that no one wants to work two days in a row next to a pump. Thus when you assign people holes to dig in on the second day you have to make sure that no one is digging in a hole with a pump two days in a row. This perhaps isn’t a particularly complicated task but some people in Tæknigarður have begun taking interest in your work. They begin to speculate in how many different ways you could have solved this particular predicament. Can you answer this burning question? Since the number of holes might be enormous the answer has to be given modulo $10^9+7$.

Input

The only line in the input contains one integer $1 \leq n \leq 10^7$, the number of holes and employees.

Output

The only line in the output should contain the number of ways you can assign pumps and employees to holes, given modulo $10^9 + 7$.

3

18

100

725034763