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.

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
import itertools
import numpy as np
b = np.zeros(100001, dtype=np.int)

def power2(a):
	b[0] = 1
	if b[a] > 0:
		return b[a]
	else:
		for i in range(1, a + 1):
			b[i] = b[i - 1] * 2
			if b[i] > 10 ** 9 + 7:
				b[i] = b[i] % (10 ** 9 + 7)
		return b[a]

def __starting_point():
	t = eval(input())
	for i in range(t):
		s = input()
		n = eval(input())
		f_list = []
		count = 0
		for j in range(n):
			f_list.append(input())
		inp = ''
		bin_list = []
		for j in range(len(s)):
			if s[j] == 'w':
				inp = inp + '0'
			else:
				inp = inp + '1'
		a = np.zeros(1024, dtype=np.int)
		for j in range(n):
			s1 = ''
			for k in range(len(f_list[j])):
				if f_list[j][k] == '+':
					s1 = s1 + '1'
				else:
					s1 = s1 + '0'
			if n < 1024:
				bin_list.append(s1)
			p = int(s1, 2)
			if a[p] == 0:
				count = count + 1
			a[p] = a[p] + 1
		count_2 = 0
		if n < 1024:
			dp = np.zeros((n + 1, 1024), dtype=np.int64)
			dp[0, 0] = 1
			for j in range(1, n + 1):
				for k in range(1024):
					dp[j, k] = (dp[j - 1][k] + dp[j - 1][k ^ int(bin_list[j - 1], 2)]) % (10 ** 9 + 7)
			p = 1023 ^ int(inp, 2)
			print(dp[n, p] % (10 ** 9 + 7))
		else:
			dp = np.zeros((1025, 1024), dtype=np.int64)
			dp[0, 0] = 1
			for j in range(1, 1025):
				count_2 = count_2 + 1
				if a[j - 1] > 0:
					l = power2(a[j - 1] - 1)
				for k in range(1024):
					if a[j - 1] > 0:
						dp[j, k] = (dp[j - 1][k] + dp[j - 1][k ^ j - 1]) % (10 ** 9 + 7) * l % (10 ** 9 + 7)
					elif dp[j - 1][k] > 0:
						dp[j, k] = dp[j - 1][k]
				if count_2 == count:
					break
			p = 1023 ^ int(inp, 2)
			print(dp[j, p] % (10 ** 9 + 7))
__starting_point()


t = eval(input())
MOD = 1000000007
temp = [0] * 1025
for xx in range(0, t):
	inp = input()
	n = eval(input())
	ct = [0] * 1025
	ans = [0] * 1025
	while n:
		s = input()
		m = 0
		j = 9
		c = 1
		while j >= 0:
			if s[j] == '+':
				m |= c
			c <<= 1
			j -= 1
		ct[m] += 1
		n -= 1
	for i in range(0, 1024):
		m = i
		c = ct[i]
		while c:
			for j in range(0, 1024):
				temp[j] = ans[m ^ j]
			temp[m] += 1
			for j in range(0, 1024):
				ans[j] += temp[j]
				if ans[j] > 100000000000000000:
					ans[j] %= MOD
			c -= 1
	ans[0] += 1
	s = []
	for i in range(0, 10):
		if inp[i] == 'b':
			s.append('-')
		else:
			s.append('+')
	m = 0
	j = 9
	c = 1
	while j >= 0:
		if s[j] == '+':
			m |= c
		c <<= 1
		j -= 1
	print(ans[m] % MOD)


from collections import defaultdict
import operator
for i in range(int(input())):
	s = input()
	s = s.replace('b', '1')
	s = s.replace('w', '0')
	compare = int(s, 2)
	n = int(input())
	List = []
	for i in range(n):
		bin = input()
		bin = bin.replace('+', '1')
		bin = bin.replace('-', '0')
		num = int(bin, 2)
		List.append(num)
	length = int(2 ** n)
	count = int(0)
	i = j = int(0)
	for i in range(length):
		x = 0
		for j in range(0, n):
			if i & 1 << j > 0:
				x = operator.xor(x, List[j])
		if operator.xor(x, compare) == 1023:
			count += 1
	print(count)


import itertools
import numpy as np

def __starting_point():
	t = eval(input())
	for i in range(t):
		s = input()
		n = eval(input())
		f_list = []
		for j in range(n):
			f_list.append(input())
		inp = ''
		bin_list = []
		for j in range(len(s)):
			if s[j] == 'w':
				inp = inp + '0'
			else:
				inp = inp + '1'
		a = np.zeros(1024, dtype=np.int)
		for j in range(n):
			s1 = ''
			for k in range(len(f_list[j])):
				if f_list[j][k] == '+':
					s1 = s1 + '1'
				else:
					s1 = s1 + '0'
			bin_list.append(s1)
			p = int(s1, 2)
			a[p] = a[p] + 1
		if n < 1024:
			dp = np.zeros((n + 1, 1024), dtype=np.int)
			dp[0, 0] = 1
			for j in range(1, n + 1):
				for k in range(1024):
					dp[j, k] = (dp[j - 1][k] + dp[j - 1][k ^ int(bin_list[j - 1], 2)]) % (10 ** 9 + 7)
			p = 1023 ^ int(inp, 2)
			print(dp[n, p] % (10 ** 9 + 7))
		else:
			dp = np.zeros((1025, 1024), dtype=np.int)
			dp[0, 0] = 1
			for j in range(1, 1025):
				for k in range(1024):
					if a[j - 1] > 0:
						dp[j, k] = (dp[j - 1][k] + dp[j - 1][k ^ j - 1]) * 2 ** (a[j - 1] - 1) % (10 ** 9 + 7)
					else:
						dp[j, k] = dp[j - 1][k]
			p = 1023 ^ int(inp, 2)
			print(dp[1024, p] % (10 ** 9 + 7))
__starting_point()


def ct(string):
	i = 0
	num = 0
	while i < 10:
		num *= 2
		if string[i] == 'w':
			num += 1
		i += 1
	return num

def convert(string):
	i = 0
	num = 0
	while i < 10:
		num *= 2
		if string[i] == '+':
			num += 1
		i += 1
	return num
t = int(input())
while t > 0:
	pic = input()
	m = ct(pic)
	tab = {m: 1}
	n = int(input())
	while n > 0:
		filtr = input()
		num = convert(filtr)
		k = list(tab.keys())
		newtab = tab.copy()
		for i in k:
			value = tab[i]
			new = num ^ i
			z = tab.get(new, 0)
			if z > 10000000 or value > 10000000:
				newtab[new] = (z + value) % 1000000007
			else:
				newtab[new] = z + value
		n -= 1
		tab = newtab.copy()
	print(str(tab.get(0, 0)))
	t -= 1


def ct(string):
	i = 0
	l = len(string)
	num = 0
	while i < l:
		num *= 2
		if string[i] == 'w':
			num += 1
		i += 1
	return num

def convert(string):
	i = 0
	l = len(string)
	num = 0
	while i < l:
		num *= 2
		if string[i] == '+':
			num += 1
		i += 1
	return num
t = int(input())
while t > 0:
	pic = input()
	m = ct(pic)
	tab = {m: 1}
	n = int(input())
	while n > 0:
		filtr = input()
		num = convert(filtr)
		k = list(tab.keys())
		newtab = tab.copy()
		for i in k:
			value = tab[i]
			new = num ^ i
			newtab[new] = (tab.get(new, 0) + value) % 1000000007
		n -= 1
		tab = newtab.copy()
	print(str(tab.get(0, 0)))
	t -= 1


import itertools

def powerset(f, n):
	lst = []
	for i in range(1, n + 1):
		lst.append(list(itertools.combinations(f, i)))
	return lst

def read():
	return input()

def add(s, f):
	result = ''
	for i in range(len(s)):
		if s[i] == '+' and f[i] == '+':
			result += '-'
		elif s[i] == '+' or f[i] == '+':
			result += '+'
		else:
			result += '-'
	return result

def resultfilter(f):
	result = f[0]
	if len(f) == 1:
		return result
	for item in f[1:]:
		result = add(result, item)
	return result

def getRequired(s):
	f = ''
	for i in range(len(s)):
		if s[i] == 'b':
			f += '-'
		else:
			f += '+'
	return f
for t in range(int(read())):
	s = read()
	if 'w' in s:
		count = 0
	else:
		count = 1
	requiredF = getRequired(s)
	n = int(read())
	f = []
	for i in range(n):
		f.append(read())
	y = powerset(f, n)
	for item in y:
		for temp in item:
			output = resultfilter(temp)
			if output == requiredF:
				count += 1
	print(count % 1000000007)


import itertools
import numpy as np

def countBits(p1):
	count = 0
	p2 = p1
	while p2:
		p2 = p2 & p2 - 1
		count = count + 1
	p = '{0:b}'.format(p1)
	if count == len(p):
		return True
	else:
		return False

def __starting_point():
	t = eval(input())
	for i in range(t):
		s = input()
		n = eval(input())
		f_list = []
		for j in range(n):
			f_list.append(input())
		inp = ''
		bin_list = []
		for j in range(len(s)):
			if s[j] == 'w':
				inp = inp + '0'
			else:
				inp = inp + '1'
		for j in range(n):
			s1 = ''
			for k in range(len(f_list[j])):
				if f_list[j][k] == '+':
					s1 = s1 + '1'
				else:
					s1 = s1 + '0'
			bin_list.append(s1)
		lst = [list(k) for k in itertools.product([0, 1], repeat=n)]
		count = 0
		for j in range(len(lst)):
			p = '0' * n
			for k in range(len(lst[j])):
				if lst[j][k] == 1:
					p1 = int(p, 2) ^ int(bin_list[k], 2)
					p = '{0:b}'.format(p1)
			p2 = int(p, 2) ^ int(inp, 2)
			if p2 == 2 ** len(s) - 1:
				count = (count + 1) % (10 ** 9 + 7)
		print(count % (10 ** 9 + 7))
__starting_point()


def bw(s):
	t = []
	for i in s:
		if i == 'b':
			t.append('0')
		else:
			t.append('1')
	return int(''.join((str(i) for i in t)), 2)

def pm(s):
	t = []
	for i in s:
		if i == '-':
			t.append('0')
		else:
			t.append('1')
	return int(''.join((str(i) for i in t)), 2)

def inp(n):
	t = []
	for i in range(n):
		s = input()
		t.append(pm(s))
	return t

def f(n, k, s):
	dp = [[0 for i in range(1024)] for i in range(n + 1)]
	dp[0][0] = 1
	for i in range(1, n + 1):
		for j in range(1024):
			dp[i][j] = dp[i - 1][j] + dp[i - 1][j ^ s[i - 1]]
	return dp[n][k] % (10 ** 9 + 7)
t = int(input())
for i in range(t):
	k = bw(input())
	n = int(input())
	print(f(n, k, inp(n)))


import fractions
import sys
import pprint
f = sys.stdin
if len(sys.argv) > 1:
	f = open(sys.argv[1], 'rt')
MOD = 10 ** 9 + 7
IMG_SPACE = 2 ** 10

def str2num(s, one_char):
	n = 0
	for ch in s:
		n = n << 1
		if ch == one_char:
			n = n | 1
	return n

def img2num(img_str):
	return str2num(img_str, 'w')

def flt2num(flt_str):
	return str2num(flt_str, '+')

def calc(S, filters_str):
	N = len(filters_str)
	img_num = img2num(S)
	filters_num = [flt2num(flt) for flt in filters_str]
	counts = [[0] * IMG_SPACE for i in range(N)]
	row = counts[N - 1]
	for i in range(IMG_SPACE):
		n = 0
		if i == 0:
			n += 1
		if i ^ filters_num[N - 1] == 0:
			n += 1
		row[i] = n
	for j in range(N - 2, -1, -1):
		row = counts[j]
		next_row = counts[j + 1]
		for i in range(IMG_SPACE):
			row[i] = (next_row[i] + next_row[i ^ filters_num[j]]) % MOD
	return counts[0][img_num]
T = int(f.readline().strip())
for case_id in range(1, T + 1):
	S = f.readline().strip()
	N = int(f.readline().strip())
	filters = []
	for i in range(N):
		filters.append(f.readline().strip())
	r = calc(S, filters)
	print(r)


def evaluate(a, b):
	ans = ''
	for i in range(0, len(a)):
		if a[i] == b[i]:
			ans += '-'
		else:
			ans += '+'
	return ans

def dp(p_bar, n, s):
	mod = 10 ** 7 + 9
	if n == 0:
		return 0
	elif n == 1:
		k = 0
		if p_bar == s[0]:
			k += 1
		if p_bar == '----------':
			k += 1
		return k
	else:
		return (dp(p_bar, n - 1, s) % mod + dp(evaluate(p_bar, s[n - 1]), n - 1, s)) % mod
t = int(input())
for i in range(0, t):
	p = input()
	n = int(input())
	s = []
	for j in range(0, n):
		temp = input()
		s.append(temp)
	p_bar = ''
	for j in p:
		if j == 'w':
			p_bar += '+'
		else:
			p_bar += '-'
	print(dp(p_bar, n, s))


Author = 'Rahul_Arora'
Date = '8/12/15'
import sys
from math import factorial as f
t = eval(input())
Author = 'Rahul_Arora'
Date = '8/12/15'
MODULUS = 10 ** 9 + 7
variable = f(10)
for temp in range(t):
	Author = 'Rahul_Arora'
	Date = '8/12/15'
	s = input()
	st = ''
	for i in s:
		if i == 'w':
			st += '0'
		else:
			st += '1'
	var = int(st, 2)
	check = 10000
	variable = f(8)
	n = list(map(int, sys.stdin.readline().split()))
	n = n[0]
	asp = n
	li = []
	for k in range(n):
		check += k
		ss = list(map(str, sys.stdin.readline().split()))
		ss = ss[0]
		st = ''
		for i in ss:
			if i == '+':
				st += '1'
			else:
				st += '0'
		variable = f(7)
		li.append(int(st, 2))
	lii = set(li)
	lii = list(lii)
	my_list = lii[:]
	asp = len(lii)
	dp = [0] * 1024
	ANSWER = 0
	my_list = lii[:]
	for i in range(asp):
		vp = [0] * 1024
		check = check - i
		j = 0
		while j < 1024:
			vp[j ^ lii[i]] += dp[j]
			j += 1
		vp[lii[i]] += 1
		j = 0
		my_list = lii[:]
		while j < 1024:
			dp[j] += vp[j]
			j += 1
	my_list = lii[:]
	if var == 1023:
		ANSWER += 1
		my_list = lii[:]
	my_list = lii[:]
	for i in range(1024):
		if i ^ var == 1023:
			ANSWER += dp[i]
		i += 1
	variable = f(10)
	le = len(li) - len(set(li))
	variable = f(10)
	ANSWER = ANSWER % MODULUS * pow(2, le, MODULUS)
	variable = f(10)
	check = check * 10 / check
	variable = f(10)
	print(ANSWER % MODULUS)
author = 'rahulxxarora'


def filtera(p):
	p = p.replace('w', '1')
	p = p.replace('b', '0')
	return p

def filtern(q):
	q = q.replace('+', '1')
	q = q.replace('-', '0')
	return q
mod = 10 ** 9 + 7
from sys import stdin
inp = stdin.read().split()
x = 0
for _ in range(int(inp[x])):
	x += 1
	m = int(filtera(inp[x]), 2)
	x += 1
	n = int(inp[x])
	arr = []
	for _ in range(n):
		x += 1
		k = int(filtern(inp[x]), 2)
		arr.append(k)
	d = [[0] * 1025 for _ in range(2)]
	d[0][0] = 1
	for i in range(1, n + 1):
		for j in range(1024):
			d[i % 2][j] = (d[(i - 1) % 2][j] + d[(i - 1) % 2][j ^ arr[i - 1]]) % mod
	if n % 2:
		print(d[1][m] % mod)
	else:
		print(d[0][m] % mod)