baraj

Comisia olimpiadei organizează selecția pentru lotul lărgit, etapă la care participă $N$ elevi. Pentru competiția finală, comisia dorește să formeze o echipă de dimensiune $K$, unde $K$ nu este fixat inițial, putând fi orice număr natural cuprins între $2$ și $N$ (inclusiv).

După ce se aleg cei $K$ membri ai echipei, structura internă a acesteia trebuie stabilită respectând următoarele reguli:

1. Trebuie desemnați un Căpitan și un Vice-căpitan (aceștia trebuie să fie doi elevi distincți din echipa selectată).
2. Restul de $K - 2$ membri rămași trebuie repartizați în două tabere de antrenament: Tabăra de Info și Tabăra de Mate. Fiecare dintre acești elevi trebuie să aleagă exact o tabără (este permis ca o tabără să rămână fără niciun membru).

Cerință

Cunoscând numărul total de elevi $N$, scrieți un program care să determine numărul total de moduri în care se poate forma și structura echipa, luând în calcul toate dimensiunile posibile $K \in [2, N]$. Deoarece acest număr poate fi astronomic, se cere rezultatul modulo $1 \ 000 \ 000 \ 007$ (restul împărțirii la $10^9 + 7$).

Date de intrare

Fișierul de intrare baraj.in conține pe prima linie un singur număr natural $N$, reprezentând numărul de elevi participanți la selecție.

Date de ieșire

Fișierul de ieșire baraj.out va conține pe o singură linie un număr natural, reprezentând numărul total de moduri în care se poate forma echipa, modulo $1 \ 000 \ 000 \ 007$.

Restricții și precizări

• $2 \le N \le 10^9$
• Pentru formarea echipei, ordinea alegerii membrilor de bază (exceptând căpitanul și vice-căpitanul) nu contează, ci doar identitatea lor și tabăra în care sunt repartizați.

Exemplul 1

baraj.in

3

baraj.out

18

Explicație

Avem $N = 3$ elevi. Dimensiunea echipei poate fi $K = 2$ sau $K = 3$.

Cazul $K = 2$:

• Se aleg 2 elevi din cei 3 disponibili ($\binom{3}{2} = 3$ moduri).
• Din cei 2 aleși, se desemnează căpitanul și vice-căpitanul ($2 \times 1 = 2$ moduri).
• Mai rămân $0$ membri de repartizat în tabere ($2^0 = 1$ mod).
  Număr moduri pentru $K = 2$: $3 \times 2 \times 1 = 6$ moduri.

Cazul $K = 3$:

• Se aleg 3 elevi din cei 3 disponibili ($\binom{3}{3} = 1$ mod).
• Din cei 3 aleși, se desemnează căpitanul și vice-căpitanul ($3 \times 2 = 6$ moduri).
• Mai rămâne exact $1$ membru, care trebuie să aleagă între Tabăra de Info și Tabăra de Mate ($2^1 = 2$ moduri).
  Număr moduri pentru $K = 3$: $1 \times 6 \times 2 = 12$ moduri.

Numărul total de moduri este $6 + 12 = 18$. Rezultatul se afișează modulo $10^9 + 7$, deci $18$.

Exemplul 2

baraj.in

4

baraj.out

108

Explicație

Pentru $N = 4$, luăm în calcul echipe de dimensiuni $K \in \{2, 3, 4\}$.

• $K = 2$: $\binom{4}{2} \times (2 \times 1) \times 2^0 = 6 \times 2 \times 1 = 12$ moduri
• $K = 3$: $\binom{4}{3} \times (3 \times 2) \times 2^1 = 4 \times 6 \times 2 = 48$ moduri
• $K = 4$: $\binom{4}{4} \times (4 \times 3) \times 2^2 = 1 \times 12 \times 4 = 48$ moduri

Total general: $12 + 48 + 48 = 108$ moduri.