Ghoberscris

Manuscris

Din păcate, manuscrisele care s-au păstrat au fost deteriorate de timp și culorile de pe ele au ajuns indescifrabile, însă structura propoziției s-a păstrat.
Dându-se structura unei propoziții (sub formă de arbore) și numărul $k$ de cuvinte / culori distincte din limba ghoberiană, calculați numărul de înțelesuri distincte pe care le putea avea inițial propoziția.

Două înțelesuri se consideră ghober-diferite dacă nu există o reordonare a cuvintelor astfel încât să se obțină doi arbori colorați identic.

Două înțelesuri se consideră ghober-diferite dacă nu există o renumerotare a nodurilor astfel încât să se obțină doi arbori colorați identic.
 
Mai exact: Doi arbori $G(V, E, c: V -> C)$ și $G'(V, E', c': V -> C)$ se considera "la fel" (izomorfi) dacă există o funcție $f: V -> V'$ bijectivă a.î. $c'(f(v)) = c(v)$ oricare ar fi $v ∈ V$ si $E' = {(f(v), f(u)) | (v, u) ∈ E}$ unde $C = {1, 2 ... k}$ și $V = {1, 2 ... n}$.

h2. Date de intrare

h2. Date de ieşire

În fişierul de ieşire $manuscris.out$, pe prima linie, afișați numărul de înțelesuri posibile diferite ale propoziției date.

În fişierul de ieşire $manuscris.out$, pe prima linie, afișați numărul de înțelesuri posibile diferite ale propoziției date, modulo $10^9^ + 7$.

h2. Restricții