C - Al treilea Crack

Time limit: 0.2s Memory limit: 64MB Input: Output:

Cerință

A apărut un superbet și în CrackLand. La acest superbet sunt NN aparate, un aparat de șmecherie 11, un aparat de șmecherie 22 ... un aparat de șmecherie NN.

Noi suntem profesioniști dar am fost blestemați de către plug. Blestemul zice că dacă noi jucăm la timpul ii la aparatul de șmecherie ii 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 NN.

Date de ieșire

Numărul de moduri cerut modulo 109+710^9+7.

Restricții și precizări

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

Exemplul 1

stdin

3

stdout

2

Explicație

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

Putem câștiga la maxim 33 aprate deodată, 22 dintre aceste configurații au câștigul maxim.

Exemplul 2

stdin

11

stdout

14684570

Log in or sign up to be able to send submissions!