메탈은 인생

안녕하세요 여러분
와치아웃 레코드의 이강토입니다
메탈은 인생이에요
딴 거 들을 생각 하지도 마시죠??

이강토 (Watch Out Records)

강토는 늘 메탈은 인생이라고 외치고 다닌다. 어느 날 강토는 몹시 심심해졌다. 그래서 좋아하는 밴드 N개의 이름을 카드 한 장에 하나씩 적었다. 그리고 좋아하는 순서대로 카드를 쌓아 나나에게 건네주다가 기침을 해서 순서를 모두 흐트러뜨렸다.

나나는 강토가 좋아하는 순서대로 카드를 다시 정렬하려고 한다. 강토는 정보 M개만 알려주고 도망쳤으니, 나나가 쓸 수 있는 단서는 그 M개뿐이다.

강토가 좋아하는 순서대로 정렬한 카드를 A라고 한다. 첫 번째 카드는 $A_0$, 두 번째 카드는 $A_1$, 마지막 카드는 $A_{N-1}$이다. A는 밴드 이름 N개를 각각 한 번씩 모두 쓴 수열이다. 각 정보는 정수 두 개 u와 v로 이루어지고, $A_u$가 $A_v$의 접두사였다는 뜻이다. 문자열 x가 문자열 y의 접두사라는 말은 y가 x로 시작한다는 뜻이다.

가능한 A의 개수를 구하는 프로그램을 작성하시오. 강토가 준 정보에 거짓이 섞여 있을 수도 있어서, 가능한 A가 하나도 없을 수도 있다.

첫째 줄에 N과 M이 주어진다. ($2 \le N \le 50$, $0 \le M \le 8$)

둘째 줄에 강토가 좋아하는 밴드의 이름 N개가 공백으로 구분되어 주어진다. 이름은 알파벳 소문자로만 이루어지고, 길이는 50을 넘지 않는다. 이름은 서로 다르다. 주어지는 순서는 강토가 좋아하는 순서와 관계없다.

셋째 줄부터 M개의 줄에 강토가 준 정보 u와 v가 한 줄에 하나씩 주어진다. ($0 \le u, v \le N-1$, $u \ne v$) 같은 정보가 두 번 이상 주어지는 경우는 없다.

가능한 A의 개수를 1,000,000,007로 나눈 나머지를 출력한다.