Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.

Nobody outside the cooking community knows that Chef is a big fan of Chefgram™ — a social network where chefs and cooks upload their secret kitchen photos.
Recently Chef clicked a beautiful photo, which is represented using 10 pixels in a single row. Respecting Chefgram™'s boolean roots, every pixel is either white or black.

Chefgram™ has N filters. Every filter is a string containing 10 symbols. Every symbol is either '+' or '-'.

A '+' at the i^{th} position in a filter means that if Chef applies this filter to his photo, the i^{th} pixel will be inverted: it becomes black if it was originally white, and vice versa.
A '-' at the i^{th} position in a filter string means that if Chef applies this filter to his photo, the i^{th} pixel will remain unchanged.

Chef can apply as many filters as he wants from a list. He can pick any subset of filters and consequently apply them to a photo.

For example:

Imagine that Chef has a photo "bbwwbbwwbb" (where 'b' stands for black and 'w' stands for white).
He applies filters "++--++--++", "-+-+-+-+-+".
Applying the first filter will transform his picture to "wwwwwwwwww".
Applying the second filter on the transformed picture will give Chef the picture "wbwbwbwbwb".

Even if Chefgram™ has two or more identical filters, they are still considered different!

Chef is extremely interested in knowing how many different subsets of all the Chefgram™ filters can he apply to transform his photo into 10 black pixels?

------ Input ------

The first line of input contains a single integer T — the number of test cases.
First line of each test case contains a string S. Each symbol is either 'b' or 'w'. This is Chef's photo.
Second line of each test case contains a single integer N — the number of Chefgram™ filters.
Each of the next N lines contains a single string F_{i}, each symbol of which is either '+' or '-'. This string is the i_{th} Chefgram™ filter.

------ Output ------

For each test case, output a single line containing a single integer — answer to Chef's question modulo 10^{9}+7.

------ Constraints ------

$1 ≤ T ≤ 5$
$|S| = 10$
$1 ≤ N ≤ 10^{5}$
$|F_{i}| = 10$

------ Subtasks ------

$Subtask 1: T ≤ 5; N ≤ 20; Points: 20$
$Subtask 2: T ≤ 5; N ≤ 10^{3}; Points: 30$
$Subtask 3: T ≤ 5; N ≤ 10^{5}; Points: 50$

----- Sample Input 1 ------
3

wwwwwwwwww

3

+-+-+-+-+-

+---------

wbwbwbwbwb

3

+-+-+-+-+-

+-+-------

----+-+-+-

bbbbbbbbbb

2

----- Sample Output 1 ------
0

2

4
----- explanation 1 ------
Example case 1. There is no filter or combination of filters transforming the picture to whole black.
Example case 2. Chef can either apply the first filter (and invert all whites) or apply the second and third filters in any order.
Example case 3. Picture is already fully black, and we have two different identity filters. Chef can either apply the empty subset of filters, the first filter only, the second filter only, or both.

见题面

见题面