Marcel s-a apucat recent de un nou hobby:~crearea grădinilor zen. Şi-a dezvoltat rapid propriul stil, care foloseşte $2N$ pietre drept decoraţiuni de grădină. Jumătate de pietre sunt verzi (sunt acoperite cu muşchi) şi sunt numerotate unic de la $1$ la $N$, în timp ce cealaltă jumătate sunt gri (nu creşte muşchi pe ele) şi sunt de asemenea numerotate unic de la $1$ la $N$. În vederea creării unei grădini, Marcel va lua pietrele şi le va plasa într-o anumită ordine în linie dreaptă, asigurându-se că distanţa dintre oricare două pietre consecutive este exact $1$ inch.

Când vine vorba de a judeca aspectul estetic al unei grădini, toate grădinile sunt considerate frumoase. Cu toate acestea, există o superstiţie pe care Marcel o are despre grădinile sale:~dacă distanţa dintre două pietre care au acelaşi număr scrie pe ele este egală cu un multiplu de $M$ inchi, atunci grădina este considerată $M-$*ghinionistă*, aducând mare ghinion şi abătând erori $Code::Blocks$ asupra celui care a creat grădina respectivă. Marcel nu va crea niciodată o astfel de grădină. În mod normal, restul grădinilor sunt considerate $M-$*norocoase*.

Când vine vorba de a judeca aspectul estetic al unei grădini, toate grădinile sunt considerate frumoase. Cu toate acestea, există o superstiţie pe care Marcel o are despre grădinile sale:~dacă distanţa dintre două pietre care au acelaşi număr scrie pe ele este egală cu un multiplu de $M$ inchi, atunci grădina este considerată $M-$ *ghinionistă*, aducând mare ghinion şi abătând erori $Code::Blocks$ asupra celui care a creat grădina respectivă. Marcel nu va crea niciodată o astfel de grădină. În mod normal, restul grădinilor sunt considerate $M-$ *norocoase*.

Ca parte din aventura lui de a dobândi înţelepciune, Marcel a decis să creeze toate grădinile $M-$*norocoase*posibile. În orice caz, fiind de asemenea şi un individ precaut şi organizat, Marcel şi-ar dori să afle câte grădini $M-$*norocoase* conţinând $2N$ pietre există înainte să plece în misiunea lui. Două grădini $A$ şi $B$ sunt considerate diferite dacă există un număr întreg $i$, $1 ≤ i ≤ 2N$, astfel încât:

Ca parte din aventura lui de a dobândi înţelepciune, Marcel a decis să creeze toate grădinile $M-$ *norocoase* posibile. În orice caz, fiind de asemenea şi un individ precaut şi organizat, Marcel şi-ar dori să afle câte grădini $M-$ *norocoase* conţinând $2N$ pietre există înainte să plece în misiunea lui. Două grădini $A$ şi $B$ sunt considerate diferite dacă există un număr întreg $i$, $1 ≤ i ≤ 2N$, astfel încât:

* culoarea celei de-a $i$-a pietre din grădina $A$ este diferită de culoarea celei de-a $i$-a pietre din grădina $B$, sau
* numărul scris pe a $i$-a piatră din grădina $A$ este diferit de numărul scris pe a $i$-a piatră din grădina $B$.

h2. Date de ieşire

În fişierul de ieşire $num.out$ se află o singură linie, afişaţi numărul de grădini $M-$*norocoase* care conţin $2N$ pietre, *modulo $10^9+7$*.

În fişierul de ieşire $num.out$ se află o singură linie, afişaţi numărul de grădini $M-$*norocoase* care conţin $2N$ pietre, *modulo $10^9^+7$*.

h2. Restricţii

h3. Explicaţie

În al doilea exemplu, pot fi create două grădini. Cu toate acestea, nicio grădină nu este $1$-*norocoasă*, întrucât pentru ambele grădini distanţa dintre pietrele numerotate cu $1$ este $1$ inch, care este un multiplu de $M = 1$ inchi.

În al doilea exemplu, pot fi create două grădini. Cu toate acestea, nicio grădină nu este $1-$*norocoasă*, întrucât pentru ambele grădini distanţa dintre pietrele numerotate cu $1$ este $1$ inch, care este un multiplu de $M = 1$ inchi.

== include(page="template/taskfooter" task_id="num") ==