Time limit exceeded Please help

general
,
1

import sys
import itertools

def hash(S):
result = S.count(‘A’)
if len(S)>1:
S1, S2 = S[:len(S)/2], S[len(S)/2:]
result = result + max(hash(S1), hash(S2))

return result

test_cases = input()

i = 0
ans = 0

for i in range(test_cases):

#accepting the input A E V
no_of_A,no_of_E,value_V = map(int,sys.stdin.readline().split())

#calculating size of the string
size = no_of_E + no_of_A

Str = ''
for _ in range(no_of_A):
	Str = Str + 'A'
for _ in range(no_of_E):
	Str = Str + 'E'



#generating combinations
perms = ["".join(x) for x in itertools.permutations(Str, size)]
combs = list(set(perms))



for S in combs:
	if hash(S) == value_V:
		ans = ans + 1
print ans%1000000007
ans = 0