P15225 [SWERC 2017] Kabobs

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$ 取模。

### 数据范围 输入满足 $1 \leq K \leq 500$ 且 $3 \leq |R| \leq 60$。 翻译由 DeepSeek 完成