시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB61150.000%

문제

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

이강토 (Watch Out Records)

강토는 항상 메탈은 인생이라고 외치고 다닌다. 어느 날 강토는 매우 심심해졌다. 강토는 자신이 좋아하는 밴드 N개의 이름을 한 장에 하나씩 카드에 적었다. 그 다음, 카드를 밴드를 좋아하는 순서로 섞은 다음에 나나에게 전달해줬다. 하지만, 나나에게 전달해주는 순간 기침을 해버리는 바람에 순서가 모두 섞여버리고 말았다.

이제, 나나는 강토가 좋아하는 순서대로 카드를 정렬해보려고 한다. 강토는 나나에게 M개의 정보만을 알려주고 도망가버렸기 때문에, 나나는 M개의 정보만을 이용해서 카드를 정렬해야 한다. 

강토가 좋아하는 순서대로 정렬한 카드를 A라고 한다. 첫 번째 카드는 A0, 두 번째 카드는 A1, ... 마지막 카드는 AN-1이다. 각각의 정보는 정수 두 개 u와 v로 이루어져 있으며, Au가 Av의 접두어(Prefix)였다는 의미이다.

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

입력

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

둘째 줄에는 강토가 좋아하는 밴드의 이름이 주어진다. 밴드의 이름을 알파벳 소문자로만 이루어져 있으며, 길이는 50을 넘지 않는다.

셋째 줄부터 M개의 줄에 강토가 준 정보 u와 v가 주어진다. (0 ≤ u, v ≤ n-1, u ≠ v) 같은 정보가 두 번 이상 주어지는 경우는 없다.

출력

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

예제 입력 1

3 1
kangto kangtoro kang
0 1

예제 출력 1

3

예제 입력 2

4 2
kangto kangho kangdo kang
0 1
0 2

예제 출력 2

6

예제 입력 3

3 2
kangto nana watchoutrecords
0 1
1 0

예제 출력 3

0

예제 입력 4

7 4
kang watch na kangto watchout nana watchoutrecords
0 1
1 2
3 4
5 6

예제 출력 4

2

예제 입력 5

3 0
remnantsofthefallen eighteenapril satellights

예제 출력 5

6

힌트

예제 1의 경우 가능한 순서는 아래와 같다.

  • kang kangto kangtoro
  • kang kangtoro kangto
  • kangto kangtoro kang

예제 4의 경우는 다음과 같은 두 가지가 가능하다.

  • watch watchout watchoutrecords kang kangto na nana
  • watch watchout watchoutrecords na nana kang kangto