TopCoder

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

100.0% (1/1)

Description

  世界上有各式各樣的罐子,像是哈密瓜汽水的罐子、葡萄汁的罐子或者是運動飲料的罐子。這些罐子其實都有神奇的分裂能力,會從一個罐子分裂成很多個。每個罐子都是由『罐子基因』來決定它是鐵罐還是鋁罐、罐子的高度及硬度等等特徵。罐子基因可以用一個由a到d這些小寫英文字母組成的序列來表示,當罐子進行分裂的時候,一個罐子會產生出四個罐子,這些罐子的罐子基因便是在原先罐子的罐子基因最後面分別附上a到d這些字母所形成的,而原先的罐子在經過分裂之後它的罐子基因就會變短(序列的第一個字母會消失),如果一個罐子的罐子基因序列長度變成零的話,那個罐子就會失去分裂能力然後死亡,接著被丟到資源回收場。罐子除了這個原因之外不會有其他的理由使它們死亡。

  然而有些罐子基因對罐子是有害的,如果存在一段有害的基因是一個罐子的罐子基因序列的子字串,那個罐子就會生病,失去分裂的能力然後被送到醫院接受治療。順道一提,罐子們一天會分裂一次。

  如果我告訴你最一開始的那一個的罐子的罐子基因序列、經過的天數跟有害的罐子基因,你能夠計算出最後有多少罐子被丟到資源回收場跟有多少罐子在醫院接受治療嗎?

Input Format

  第一行是一個非空的小寫英文字母序列,代表最一開始的罐子的罐子基因序列。接下來的兩行有兩個非負整數 p 跟 n 代表經過的天數跟有害基因的個數,最後 n 行每行都有個非空的序列代表一段有害基因。

  你可以放心的假設罐子們的罐子基因序列不管怎麼分裂長度永遠都會小於100,有害基因不會超過100種,每種的長度不會超過15,而 p 不會超過300。

Output Format

  輸出兩個數字分別代表在資源回收場跟在醫院的罐子數量,由於這兩個數字可能很大,只要輸出它們除以10007的餘數就行了。(也就是它們 Mod 10007的結果)

Sample Input

a
1
2
ab
ac

Sample Output

1 2

Hints

Problem Source

原TIOJ1473 / CSAPC'08 Problem Setter: Akira Nanase

Subtasks

For Testdata: 0 ~ 0, Score: 10
For Testdata: 1 ~ 1, Score: 10
For Testdata: 2 ~ 2, Score: 10
For Testdata: 3 ~ 3, Score: 10
For Testdata: 4 ~ 4, Score: 10
For Testdata: 5 ~ 5, Score: 10
For Testdata: 6 ~ 6, Score: 10
For Testdata: 7 ~ 7, Score: 10
For Testdata: 8 ~ 8, Score: 10
For Testdata: 9 ~ 9, Score: 10
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 10000 65536 262144
1 10000 65536 262144
2 10000 65536 262144
3 10000 65536 262144
4 10000 65536 262144
5 10000 65536 262144
6 10000 65536 262144
7 10000 65536 262144
8 10000 65536 262144
9 10000 65536 262144