Migrated from Lutece 2655 HeRaNO 的魂火

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

孩子 ID 叫 HeRaNO

第三章：HeRaNO的魂火

陈家洛在休息室坐着，忽然一发冷箭袭来，设在陈家洛头顶的墙上，箭尾挂着一封信。 “到底是谋杀还是送信啊，俺红花会的人功夫也太拉了吧。”陈家洛小声嘀咕道。拆开信封，陈家洛目光微凝，随后战了起来，在房间里左右徘徊，似乎在做什么艰难的决定。 陈家洛站定身形，深吸一口长气，就跑到房间里易容成了另一幅摸样，然后飞身向红花会在京城的据点掠去。

“糖糖，没想到你终究是被我们逮到了吧！”ZXyang冲着Sugarii狂笑到。 Sugarii扫了眼ZXyang旁边的Vingying和HeRaNO，谈定的说道：“就算你们三个今天能找到这里，不会真以为能留下我吧。” “就算解决不了你，把你的手下全部关进码字狱也是不错的。”HeRaNO眼中闪过了一丝诡异。 “？你可真有信。。。”，Sugarii还没说完，就发现HeRaNO的脸变成了诡异的血红色（此处应该有图（hrdg 的血红头像.jpg）为了避免引起不适就不放了，详见无能力者娜娜 OP 最后特写），“你想干什么？” “自从那次给Vingying传功后我就知道我撑不了多久了！”HeRaNO说到，“不如这次，就用我的最后一点码力，来换石马国一个安宁罢！！”说完，HeRaNO便引爆了自己的码核，点燃了这片土地。 Sugarii看向身处火海的红花会基地，稍微有些烦躁。"谁还不是个习武之人，这点火能奈他们何？"Sugarii嘴上虽这么说，但实际上只会码力红花会的人根本没有习武经验，“可惜我要抵御ZXyang和Vingying，这火海就只能交给土豆了” “哈哈，你可看清楚了，这只是简单的火焰吗？HeRaNO的魂火可是能克制多种红花会的武功！”Vingying大笑说道。 此时陈家洛也赶到了现场，他看着这茫茫魂火，心中已经有了计策。

土豆给红花会传功抵御魂火，每个人的武功由一串由 $\texttt{a, b, c, d}$ 组成的序列构成，表示他们武功的动作连招。所有学过武功的人都会开始帮助扑灭魂火。

魂火持续时间长达 $n$ 天，每天学会武功的人都会参与扑灭魂火，疗养院的人则在床上睡大觉（既不会学武功，也不会扑灭魂火），假定有无数个人，并且没学过武功的人不会参与扑灭魂火。

土豆还要赶回去选拔，于是将自己的武功传给一个人，让他代为传功。

红花会每个人都具有创新精神，每天中午，每个学过武功的人会把他自己的武功传功给 $4$ 个不同的没有被传功的人，学习者都会根据自己的理解在学会的武功序列后分别加上 $\texttt{a, b, c, d}$。

但是红花会的成员也都有些健忘，每天晚上，他们在传功之后便会得意忘形，忘掉自己学会的武功的第一个动作（序列的第一个字符）。

HeRaNO 的魂火对于一些特定的武功序列有克制作用。如果一个人的武功序列包括被克制的连续子序列，那么他就会在当天被魂火烧焦，关进码字狱。同时，学过武功但是把武功忘完的也会被当做笨蛋送进疗养院。

请你统计在 $n$ 天魂火停止后，有多少人被送进疗养院，有多少人被关进码字狱（第一天，被土豆传授武功的人会开始传授武功，详见样例）。

Input

第一行输入一个字符串 $L\ (1 \le |L| \le 100)$，表示开始时土豆传授给第一个人的武功。 第二行包括两个整数 $m, n\ (1 \le m \le 100, 1 \le n \le 300)$，分别代表火海克制的武功序列的个数，和火海持续时间。 接下来是 $m$ 行，每行包括一个字符串 $s_i$，表示魂火克制的武功序列，保证 $1 \le |s_i| \le 15$。

Output

输出一行以空格隔开的两个整数，分别表示被送进疗养院的人数和被关进码字狱的人数。答案对 $10009$ 取模。

Samples

a
2 1
ab
ac

1 2

Resources

2021 UESTC ICPC Training for String and Search Algorithm