John s-a apucat să numere în câte moduri poate să termine cutia.
Formal, se dă un vector circular v1, v2, . . . , vN . Vrem să scoatem din el câte un element până rămâne gol vectorul. În urma fiecărei scoateri, inclusiv înaintea primei scoateri, nu trebuie să existe 2 poziţii consecutive în vector cu aceeaşi valoare în ele.

ˆIn exemplul din dreapta, buc ̆at, ile de brˆanz ̆a de pe pozit, iile A s, i B au fost deja luate. Singurele buca ̆t, i pe care le-am putea scoate acum ar fi E sau G. Dac ̆a am scoate bucata C, atunci buc ̆at, ile D si H, ambele de tipul 2, ar deveni vecine. Daca ̆ l-am scoate pe D, C s, i E ar deveni vecine, des, i sunt ambele de tipul 1, etc.

În exemplul din dreapta, bucăţile de bânză de pe poziţiile A şi B au fost deja luate. Singurele bucăţi pe care le-am putea scoate acum ar fi E sau G. Dacă am scoate bucata C, atunci bucăţile D şi H, ambele de tipul 2, ar deveni vecine. Dacă l-am scoate pe D, C şi E ar deveni vecine, deşi sunt ambele de tipul 1, etc.
 
h2. Cerinţă
 
Să se numere în câte moduri putem goli vectorul respectând regulile din enunţ (modulo 1 000 000 007).
Un mod de a goli vectorul este definit de ordinea indicilor care părăsesc vectorul. De exemplu, pentru N = 4, sunt 4! = 24 de moduri diferite de a goli vectorul (dintre care nu toate respectă regulile din enunţ).

h2. Date de intrare