Anna 想要开一家名为“糖果山”（Candy Mountain）的奇妙餐厅，只供应糖果烤串（kabobs）：将各种食物串在签子上，从尖端吃到基部。

和其他烤串爱好者一样，当 Anna 在烤串中吃到一段连续的食物组合时，她希望之后还能吃到另一段特定的组合。例如，一旦她吃了一块苹果紧接着一块香蕉，她就希望在烤串剩余的部分中能吃到一片薄荷紧接着一块巧克力。如果她在剩余的烤串中找到了这个“薄荷-巧克力”组合，她就会感到满意。

以下是 Anna 喜欢的一种烤串： Apple-Banana-Watermelon-Plum-Watermelon-Plum-Watermelon-Mint-Chocolate

或者用图形表示：

Anna 为这家新餐厅写下了一套完美的烤串模式，但她担心这些规则会导致潜在的烤串种类太多。这套模式被写成一个规则集（ruleset），其中每条规则的形式为“$b$ 蕴含后续的 $e$”，这里 $b$ 和 $e$ 是非空的食物字符序列。形式为 $b > e$ 的规则（其中 $b = b_1 \dots b_k$，$e = e_1 \dots e_l$）意味着，如果烤串中出现了模式 $b$，那么烤串在之后的某个位置也必须包含 $e$。每个 $b_{i+1}$ 必须紧跟在 $b_i$ 之后才能触发规则，同样每个 $e_{j+1}$ 也必须紧跟在 $e_j$ 之后才能满足规则，但 $b_k$ 和 $e_1$ 不需要连续。规则中任何食物字符不能出现超过一次（即不存在 $i, j$ 使得 $e_j = b_i$，且不存在 $i \neq j$ 使得 $b_i = b_j$ 或 $e_i = e_j$），但一个食物字符可以出现在多条规则中。

注意，如果烤串中多次出现单词 $b$，它们都需要被一个 $e$ 所跟随。这可以是一个单一的 $e$，只要这个 $e$ 出现在所有 $b$ 之后即可。

在规则集中，规则由 ‘|’ 分隔，形式为 $u > v$，意味着每个模式 $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 是无效的。

Anna 问你，给定长度的烤串中有多少个符合她的规则集。

输入格式

• 第一行包含一个整数 $K$，表示所有烤串的长度，后跟一个空格，以及一个由字母数字（‘A’ 到 ‘Z’，‘a’ 到 ‘z’ 和 ‘0’ 到 ‘9’）组成的非空字符串 $S$，代表烤串中可以使用的元素（$S$ 中没有字符重复出现）。
• 第二行包含一个非空字符串 $R$，不含空格，表示如上所述的规则集。$R$ 中的模式仅由 $S$ 中的字符组成。

输出格式

一个整数：满足 $R$ 中所有规则的长度为 $K$ 的烤串数量，对 $10\,000\,000$ 取模。

数据范围

输入满足 $1 \leqslant K \leqslant 500$ 且 $3 \leqslant |R| \leqslant 60$。

样例

输入 1

4 ABC
A>B|B>C|CB>A

输出 1

9