Cupa InfoAs, ediția 5 · Clasa a X-aCombinatoricăProbleme diverse de combinatorică
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
Exemple
2
6
1000000
975701239
Explicația exemplelor
Pentru primul exemplu: există 6 moduri de a pune șosete și pantofi pe cele 2 picioare: (s1 s2 p1 p2), (s1 s2 p2 p1), (s1 p1 s2 p2), (s2 s1 p2 p1), (s2 s1 p1 p2), (s2 p2 s1 p1).
Pentru al doilea exemplu: modulo 1.000.000.007, există 975701239 moduri de a pune șosete și pantofi pe 1000000 de picioare.
Problemă adăugată pe InfoAs de 
cout << "Suma este " << s;