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 ith position in a filter means that if Chef applies this filter to his photo, the ith pixel will be inverted: it becomes black if it was originally white, and vice versa. 
- A '-' at the ith position in a filter string means that if Chef applies this filter to his photo, the ith 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 Fi, each symbol of which is either '+' or '-'. This string is the ith Chefgram™ filter.

-----Output-----
- For each test case, output a single line containing a single integer — answer to Chef's question modulo 109+7.

-----Constraints-----
- 1 ≤ T ≤ 5
- |S| = 10
- 1 ≤ N ≤ 10^5
- |Fi| = 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

-----Example-----
Input:
3
wwwwwwwwww
3
+-+-+-+-+-
----------
+---------
wbwbwbwbwb
3
+-+-+-+-+-
+-+-------
----+-+-+-
bbbbbbbbbb
2
----------
----------

Output:
0
2
4

-----Explanation-----
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.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'def evaluate(a, b):\n\tans = \'\'\n\tfor i in range(0, len(a)):\n\t\tif a[i] == b[i]:\n\t\t\tans += \'-\'\n\t\telse:\n\t\t\tans += \'+\'\n\treturn ans\n\ndef dp(p_bar, n, s):\n\tmod = 10**7 + 9\n\tif n == 0:\n\t\treturn 0\n\telif n == 1:\n\t\tk = 0\n\t\tif p_bar == s[0]:\n\t\t\tk += 1\n\t\tif p_bar == "----------":\n\t\t\tk += 1\n\t\treturn k\n\telse:\n\t\treturn (dp(p_bar, n-1, s)%mod + dp(evaluate(p_bar, s[n-1]), n-1, s))%mod\n\n\nt = int(input())\n\nfor i in range(0, t):\n\tp = input()\n\tn = int(input())\n\ts = []\n\tfor j in range(0, n):\n\t\ttemp = input()\n\t\ts.append(temp)\n\tp_bar = \'\'\n\tfor j in p:\n\t\tif j == \'w\':\n\t\t\tp_bar += \'+\'\n\t\telse:\n\t\t\tp_bar += \'-\'\n\tprint(dp(p_bar, n, s))'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13369