You are given strings of lowercase Latin letters. You are also given a string .
Define a function , where is an integer, as the following.
It can be proven that exists and can be written as a rational number . Find .
The first line contains the string () consisting of lowercase Latin letters.
The second line contains an integer (.
Each of the next lines contains () consisting of lowercase Latin letters.
The sum of does not exceed .
Output the limit .
ab 2 a b
748683265
ab 4 aaa abab baba bbb
1
It can be shown that .
