CrackContest | C - Al treilea Crack

Cerință

A apărut un superbet și în CrackLand. La acest superbet sunt $N$ aparate, un aparat de șmecherie $1$, un aparat de șmecherie $2$ ... un aparat de șmecherie $N$.

Noi suntem profesioniști dar am fost blestemați de către plug. Blestemul zice că dacă noi jucăm la timpul $i$ la aparatul de șmecherie $i$ vom pierde sigur, altfel vom câștiga la orice aparat (pentru că suntem profesioniști).

Luăm aparatele pe rând în ce ordine vrem, în câte moduri le putem lua la rând astfel încât câștigul să fie maxim?

Date de intrare

Pe prima linie se găsește $N$.

Date de ieșire

Numărul de moduri cerut modulo $10^9+7$.

Restricții și precizări

• $1 \leq N \leq 10^6$;
• Rezultatul se tripărește modulo $10^9+7$.

Exemplul 1

stdin

3

stdout

2

Explicație

Putem juca în felurile următoare:
$(1,2,3)$ - nu câștigăm deloc.
$(1,3,2)$ - câștigăm la al doilea și al treilea aparat.
$(2,1,3)$ - câștigăm la primul și al doilea aparat.
$(2,3,1)$ - câștigăm la toate aparatele.
$(3,1,2)$ - câștigăm la toate aparatele
$(3,2,1)$ - câștigăm la primul și al treilea aparat.

Putem câștiga la maxim $3$ aprate deodată, $2$ dintre aceste configurații au câștigul maxim.

Exemplul 2

stdin

11

stdout

14684570