AB3. （聚合物）

你有一台聚合物合成机器。聚合物是一种由许多较小分子（单体）首尾相连形成的长分子链。机器最多会使用 $L$ 种不同的单体，单体用大写英文字母表示（即 A 到 Z）。例如，BCCN 就是一个长度为 $4$ 的聚合物。

机器接收一个由 $K$ 个单体构成的初始短聚合物，以及一个迭代次数 $N$，并按照给定规则构造目标聚合物。

为此，系统会给出若干条“插入规则”。每条规则由：

• 一个长度为 $2$ 的相邻单体对；
• 以及一个要插入到这两个单体之间的新单体

组成。

例如，规则 CC -> B 作用在聚合物 BCCN 上时，会得到结果 BCBCN。

在每一次迭代中，机器执行如下过程：

1. 扫描当前聚合物，考虑每一对相邻单体 αβ；
2. 如果存在规则 αβ -> γ，则在这两个单体之间插入 γ，从而把 αβ 变成 αγβ。

注意：本轮中新形成的相邻对 αγ 与 γβ 只会在下一轮迭代中再被处理。

你的任务是：给定初始聚合物、规则列表以及迭代次数 $N$，求最终聚合物中每一种单体出现了多少次。由于答案可能非常大，只需输出它们对 $10^9+7$ 取模后的结果。

输入格式

第一行输入初始聚合物（由大写英文字母组成），长度为 $K$。
第二行输入两个整数 $N,M$，分别表示迭代次数与规则条数。
接下来 $M$ 行，每行输入形如 αβ γ 的三字符信息，表示插入规则 αβ -> γ。
题目保证，机器可能用到的所有不同单体种类，包含了初始串中出现的单体以及所有规则中出现的单体。

输出格式

按照字母顺序 A 到 Z，依次输出每种单体在最终聚合物中的出现次数对 $10^9+7$ 取模后的结果。

数据范围

• $1 \le N \le 10^9$
• $1 \le M \le 128$
• $1 \le K \le 10^5$
• $1 \le L \le 26$
• 保证不存在两条规则拥有相同的有序二元组左部

子任务

通过某个子任务的所有测试点后，才能获得该子任务的全部分数。

样例

输入

NNCB
4 16
CH B
HH N
CB H
NH C
HB C
HC B
HN C
NN C
BH H
NC B
NB B
BN B
BB N
BC B
CC N
CN C

输出

A 0
B 23
C 10
D 0
E 0
F 0
G 0
H 5
I 0
J 0
K 0
L 0
M 0
N 11
O 0
...
Z 0

样例说明

样例输出中的 ... 表示：从 P 到 Y 的所有字母对应计数也都为 0。

初始聚合物 NNCB 在 4 次迭代中的变化过程为：

I   NCNBCHB
II  NBCCNBBBCBHCB
III NBBBCNCCNBBNBNBBCHBHHBCHB
IV  NBBNBNBBCCNBCNCCNBBNBBNBBBNBBNBBCBHCBHHNHCBBCBHCB

因此最终例如单体 H 一共出现了 $5$ 次。