캔디 꼬치

안나는 캔디만 파는 식당 "캔디 마운틴"을 열려고 한다. 이 식당이 내놓는 음식은 캔디 꼬치 하나뿐이다. 꼬치에는 여러 종류의 음식 조각이 꽂혀 있고, 손님은 끝에서 밑동 쪽으로 차례대로 먹는다.

안나는 꼬치를 먹다가 연속한 조각이 어떤 패턴을 이루면 아직 먹지 않은 부분에서 다른 패턴을 또 만나기를 기대한다. 사과 조각을 먹은 바로 다음에 바나나 조각을 먹었다면, 남은 부분 어딘가에서 민트 잎을 먹은 바로 다음에 초콜릿을 먹기를 기대한다. 남은 조각 중 어느 위치에서든 민트 바로 뒤에 초콜릿이 나오면 안나는 만족한다.

안나가 좋아하는 꼬치의 예는 다음과 같다.

Apple-Banana-Watermelon-Plum-Watermelon-Plum-Watermelon-Mint-Chocolate

그림으로 그리면 다음과 같다.

안나는 새 식당에서 쓸 규칙을 모두 적어 두었지만, 이 규칙으로 만들 수 있는 꼬치가 너무 많을까 걱정한다. 규칙 하나는 "b가 나오면 그 뒤에 e가 나온다" 형태이고, b와 e는 음식 조각을 나타내는 문자를 이어 붙인 비어 있지 않은 문자열이다. 규칙 b>e는 꼬치에 패턴 b가 나타나면 그보다 뒤 어딘가에 e도 나타나야 한다는 뜻이다. 규칙이 발동하려면 b의 문자가 모두 연속해서 나와야 하고, 규칙을 만족하려면 e의 문자도 모두 연속해서 나와야 한다. 다만 b의 마지막 문자와 e의 첫 문자는 붙어 있지 않아도 되며, e의 첫 문자가 b의 마지막 문자보다 뒤에 있기만 하면 된다. 한 규칙 안에 같은 음식 조각은 두 번 나오지 않는다. 즉 b와 e는 공통 문자가 없고 b 안에서도, e 안에서도 문자가 겹치지 않는다. 반면 한 음식 조각이 여러 규칙에 나오는 것은 가능하다.

꼬치 안에 b가 여러 번 나타나면 그 하나하나마다 뒤에 e가 있어야 한다. 모든 b보다 뒤에 e가 하나만 있어도 조건을 만족한다.

규칙 집합에서는 규칙을 |로 구분하고 각 규칙을 u>v 꼴로 쓴다. u와 v는 영문자와 숫자로 이루어진 문자열이고, 한 규칙 안에 같은 문자가 두 번 나오지 않는다. 예를 들어 규칙 집합 AB>X|R>A|T>B는 규칙 세 개를 나타낸다.

• AB가 나올 때마다 그 뒤에 X가 있어야 한다.
• R가 나올 때마다 그 뒤에 A가 있어야 한다.
• T가 나올 때마다 그 뒤에 B가 있어야 한다.

이 규칙 집합에서 꼬치 SBSB, REA, ABX, BA, ABXBA, RRA, TBTB, RTABX는 올바르지만 RAT, TAB, ABXAB는 올바르지 않다.

길이가 $K$인 꼬치 중 규칙을 모두 만족하는 것이 몇 개인지 세어라. 꼬치의 각 자리에는 $S$의 조각 하나를 놓으며, 같은 조각을 여러 자리에 놓아도 된다.

첫째 줄에 꼬치의 길이 $K$와 공백, 그리고 꼬치에 쓸 수 있는 조각을 나타내는 비어 있지 않은 문자열 $S$가 주어진다. $S$는 영문자와 숫자('A'부터 'Z', 'a'부터 'z', '0'부터 '9')로 이루어지고 같은 문자가 두 번 나오지 않는다.

둘째 줄에 규칙 집합을 나타내는 비어 있지 않은 문자열 $R$이 주어진다. $R$에는 공백이 없고, $R$에 나오는 패턴은 $S$의 문자로만 이루어진다.

$1 \le K \le 500$, $3 \le |R| \le 60$이다.

길이가 $K$이고 $R$의 규칙을 모두 만족하는 꼬치의 개수를 10000000으로 나눈 나머지를 한 줄에 출력한다.