ID #123 · Colecția InfoAs · Operatori și expresii

Problema Aeres

Ca vânător de monștri, ești lăudat și apreciat de toți locuitorii orașului tău, Agopool, pentru actele tale de eroism. Cu toate acestea, te-ai plictisit de urmărit monștri obișnuiți. Știi deja cum să îi găsești și să îi capturezi, iar după un timp, te hotărăști să îți găsești o provocare mai aparte. De data aceasta ți-ai ales să te încumeți în vânarea lui Aeres, cel mai mare și înfricoșător monstru pe care l-ai văzut vreodată. Aeres este un monstru mai atipic, iar provocarea pe care ți-o dă este cu atât mai atipică: având `n` picioare, acesta îți promite că dacă îi poți răspunde corect la o întrebare pe care ți-o dă, acesta va părăsi de unul singur orașul Agopool, ferindu-i de tot pe locuitori de relele pe care le face. Poți salva orașul și de data aceasta? ## Cerință Întrebarea pe care o primești este următoarea. Știind că Aeres are câte o șosetă și un pantof, corespunzătoare pentru fiecare picior în parte, în câte moduri diferite poate acesta să își pună șosetele și pantofii, știind că pentru fiecare picior în parte, trebuie să pună mai întâi o șosetă înainte de a pune un pantof? Deoarece răspunsul poate fi foarte mare, Aeres se mulțumește cu răspunsul `modulo 1.000.000.007`. ## Date de intrare Fișierul de intrare `aeres.in` conține un singur număr natural `n`, reprezentând numărul de picioare ale lui Aeres. ## Date de ieșire Fișierul de ieșire `aeres.out` va conține un singur număr natural reprezentând numărul de moduri în care Aeres poate să își pună șosetele și pantofii în picioare. Răspunsul se va da `modulo 1.000.000.007`. ## Restricții și precizări * `1 ≤ n ≤ 1.000.000` ### Pentru 25 de puncte * `1 ≤ n ≤ 5`