Uolevi järjestää juhlan, johon tulee n osallistujaa. Juhlan aluksi on ohjelmanumero nimeltä onginta.

Jokainen osallistuja tuo juhliin pienen lahjan. Uolevi asettuu verhon taakse lahjojen kanssa, ja jokainen osallistuja saa onkia itselleen yhden lahjoista verhon yli.

Montako tapaa on jakaa lahjat niin, että kukaan ei saa omaa lahjaansa?

Syöte

Syötteen ainoalla rivillä on kokonaisluku n: osallistujien määrä.

Tuloste

Tulosta tapojen määrä modulo 10^9+7.

Esimerkki 1

Syöte:

3

Tuloste:

2

Esimerkki 2

Syöte:

8

Tuloste:

14833

Osatehtävä 1

• 2 \le n \le 10

Osatehtävä 2

• 2 \le n \le 1000

Osatehtävä 3

• 2 \le n \le 10^6