Metal Is Life

Hello everyone
This is Kangto Lee of Watch Out Records
Metal is life
Do not even think about listening to anything else??

Kangto Lee (Watch Out Records)

Kangto goes around shouting that metal is life. One day he got very bored, so he wrote the names of his N favorite bands on cards, one name per card. He stacked the cards in the order he likes the bands and was handing the stack to Nana when he coughed, and the order got completely scrambled.

Nana wants to sort the cards back into Kangto's order of preference. Kangto told her only M facts before running off, so those M facts are the only clues she has.

Call the stack sorted in Kangto's order of preference A. The first card is $A_0$, the second card is $A_1$, and the last card is $A_{N-1}$. A uses each of the N band names exactly once. Each fact consists of two integers u and v, and it means that $A_u$ was a prefix of $A_v$. A string x is a prefix of a string y when y starts with x.

Write a program that counts the possible sequences A. Some of the facts Kangto gave may be false, so there may be no possible A at all.

The first line contains N and M. ($2 \le N \le 50$, $0 \le M \le 8$)

The second line contains the N band names Kangto likes, separated by spaces. Each name consists of lowercase letters only and its length is at most 50. The names are distinct. The order in which they are given has nothing to do with Kangto's order of preference.

Each of the next M lines contains one fact Kangto gave, u and v. ($0 \le u, v \le N-1$, $u \ne v$) The same fact is never given more than once.

Print the number of possible sequences A modulo 1,000,000,007.