Couples
By Francisco Elio Parente Arcos Filho, Universidade do Estado do Amazonas 
Brazil
By Francisco Elio Parente Arcos Filho, Universidade do Estado do Amazonas Brazil
A group entirely formed by couples went out for dinner. When they arived at the restaurant they chosse a rectangular table with the amount of seats exactly the same as the people in their group. They all sat one couple at time, so as to occupy only the larger pair of opposite sides.
Given the number of couples and knowing that each person sat in front of or beside their pair, calculate the number of different ways that this group may have occupied the table.
One way of occupying the table is considered different from the other if at least one person is in a position different from his previous one.
The input consists in a single line containing an integer N (1 ≤ N ≤ 106) representing the quantity of couples.
The output consists of a single line containing the number of ways the couples placed themselves on the table following the restrictions. Since this number can be very large, just print the number module 10 9+7.
| Input Samples | Output Samples |
|
1 |
2 |
|
2 |
16 |
|
3 |
144 |