Agència de viatges P91924

Statement

Una agència de viatges ven rutes. En particular, disposa d’ $m$ parells de ciutats connectades amb vols directes en ambdós sentits. Una ruta és una seqüència de ciutats tal que es pot volar directament des de cada ciutat a la següent, amb dues condicions:

Cal fer almenys un vol.
Les ciutats de la ruta han d’aparèixer en ordre alfabètic.

L’agència vol calcular quantes rutes pot oferir als seus clients. La podeu ajudar?

Per exemple, si tenim vols directes entre Barcelona i París, entre Barcelona i Londres, i entre París i Londres, llavors hi ha exactament quatre rutes possibles: Barcelona $\to$ París, Barcelona $\to$ Londres, Barcelona $\to$ Londres $\to$ París, i Londres $\to$ París.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb el nombre de vols entre ciutats $m$ . Segueixen els $m$ vols amb el format que podeu veure als exemples. Els noms de ciutats estan compostos només per entre 1 i 10 lletres minúscules. No hi ha vols entre una ciutat i ella mateixa, ni vols repetits. Si anomenem $n$ al nombre de ciutats diferents d’un cas, podeu suposar $2 \le n \le 10^4$ , i $m \le 5n$ .

Sortida

Per a cada cas, escriviu el nombre de rutes possibles. Com que aquest nombre pot ser molt gros, feu els càlculs mòdul $10^8 + 7$ .

Public test cases

Input

3
barcelona <-> paris
paris <-> londres
londres <-> barcelona
4
a <-> aa
aaa <-> a
b <-> c
d <-> c

Output

4
5

Information

Author: Salvador Roura
Language: Catalan
Official solutions: C++
User solutions: C++