说明

Anna 想开一家神奇的餐厅“糖果山”，只提供糖果烤肉串：这是一种将各种食物块串在签子上的美食，从尖端吃到根部。

和其他烤肉串爱好者一样，当 Anna 在烤肉串中吃到连续食物类型的模式时，她期望在烤肉串的后续部分吃到另一个模式。例如，一旦她吃到一个苹果块后立即吃到一个香蕉块，她期望在剩余部分有薄荷叶后立即吃到巧克力块。如果她在剩余烤肉串块中的任意位置找到这个薄荷-巧克力模式，她就会感到满意。

以下是一个 Anna 喜欢的烤肉串示例：

苹果-香蕉-西瓜-李子-西瓜-李子-西瓜-薄荷-巧克力

或用图形表示：

:::align{center} :::

Anna 为新餐厅写下了她完美的烤肉串模式集，但她担心这些规则会产生太多可能的烤肉串类型。这个模式集被写为一个 规则集，其中每条规则的形式为“$b$ 隐含 $e$ 之后”，其中 $b$ 和 $e$ 是非空字符序列，代表食物块。形式为 $b > e$ 的规则，其中 $b = b_1 \ldots b_k$ 且 $e = e_1 \ldots 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。

使用这个规则集，烤肉串 SBSSB、REA、ABX、BA、ABXBA、RRA、TBTB 和 RTABX 是有效的；但 RAT、TAB 和 ABXAB 无效。

Anna 问你，有多少个给定大小的烤肉串与她的规则集兼容。

输入格式

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

输出格式

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

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

9

提示

数据范围

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

翻译由 DeepSeek 完成