Question
Prefix Glow
Alice is given N binary strings (composed of 0s and 1s), each assigned a beauty value. She must answer Q queries, each providing a string S. For each query, compute the sum of beauty values of all strings where S is a prefix, returning the sum modulo 109 + 7.
Input
The first line of the input contains N, number of strings and Q, the number of Queries.
The next N lines contain string A and its beauty value denoted by p.
The next Q lines contain string S.
The next N lines contain string A and its beauty value denoted by p.
The next Q lines contain string S.
Output
Print the sum of beauty values of all those strings of which string S is a prefix.
Example
Sample Input
5 4
101 5
000 3
001 5
010 1
111 9
00
1
0
011
Sample Output
8
14
9
0
5 4
101 5
000 3
001 5
010 1
111 9
00
1
0
011
Sample Output
8
14
9
0