Given a boolean expression S of length N with following symbols.
Symbols
    'T' ---> true
    'F' ---> false
and following operators filled between symbols
Operators
    &   ---> boolean AND
    |   ---> boolean OR
    ^   ---> boolean XOR
Count the number of ways we can parenthesize the expression so that the value of expression evaluates to true.
 
Example 1:
Input: N = 7
S = T|T&F^T
Output: 4
Explaination: The expression evaluates 
to true in 4 ways ((T|T)&(F^T)), 
(T|(T&(F^T))), (((T|T)&F)^T) and (T|((T&F)^T)).
Example 2:
Input: N = 5
S = T^F|F
Output: 2
Explaination: ((T^F)|F) and (T^(F|F)) are the 
only ways.
 
Your Task:
You do not need to read input or print anything. Your task is to complete the function countWays() which takes N and S as input parameters and returns number of possible ways modulo 1003.
 
Expected Time Complexity: O(N^{3})
Expected Auxiliary Space: O(N^{2})
 
Constraints:
1 ≤ N ≤ 200

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Starter code: #User function Template for python3



class Solution:

    def countWays(self, N, S):

        # code here

Solutions:
class Solution:

	def countWays(self, N, S):
		mod = 10 ** 3 + 3
		dic = {}

		def solve(s, i, j, x):
			if i > j:
				return 0
			if i == j:
				if s[i] == x:
					return 1
				else:
					return 0
			temp = str(i) + ' ' + str(j) + ' ' + str(x)
			if temp in dic.keys():
				return dic[temp]
			k = i + 1
			ans = [0]
			while k < j:
				LT = solve(s, i, k - 1, 'T')
				LF = solve(s, i, k - 1, 'F')
				RT = solve(s, k + 1, j, 'T')
				RF = solve(s, k + 1, j, 'F')
				if s[k] == '&':
					if x == 'T':
						ans[0] = (ans[0] + LT * RT % mod) % mod
					else:
						ans[0] = (ans[0] + LT * RF % mod + LF * RT % mod + LF * RF % mod) % mod
				elif s[k] == '|':
					if x == 'T':
						ans[0] = (ans[0] + LT * RT % mod + LT * RF % mod + LF * RT % mod) % mod
					else:
						ans[0] = (ans[0] + LF * RF % mod) % mod
				elif s[k] == '^':
					if x == 'T':
						ans[0] = (ans[0] + LT * RF % mod + LF * RT % mod) % mod
					else:
						ans[0] = (ans[0] + LT * RT % mod + LF * RF % mod) % mod
				k += 2
			dic[temp] = ans[0] % mod
			return ans[0] % mod
		return solve(S, 0, N - 1, 'T')


class Solution:

	def countWays(self, N, S):
		mod = 1003
		dp = [[[0 for i in range(2)] for i in range(N + 2)] for i in range(N + 2)]
		if N == 1:
			if S[0] == 'T':
				return 1
			else:
				return 0
		for i in range(N):
			dp[i][i][1] = S[i] == 'T'
			dp[i][i][0] = S[i] == 'F'
		for i in range(N, -1, -1):
			for j in range(1, N + 1):
				if i > j:
					continue
				for k in range(i + 1, j, 2):
					lt = dp[i][k - 1][1]
					lf = dp[i][k - 1][0]
					rt = dp[k + 1][j][1]
					rf = dp[k + 1][j][0]
					if S[k] == '|':
						dp[i][j][1] = (dp[i][j][1] + lt * rt + lt * rf + lf * rt) % mod
						dp[i][j][0] = (dp[i][j][0] + lf * rf) % mod
					elif S[k] == '&':
						dp[i][j][1] = (dp[i][j][1] + lt * rt) % mod
						dp[i][j][0] = (dp[i][j][0] + lt * rf + lf * rt + lf * rf) % mod
					else:
						dp[i][j][1] = (dp[i][j][1] + lt * rf + lf * rt) % mod
						dp[i][j][0] = (dp[i][j][0] + lt * rt + lf * rf) % mod
		return dp[0][N - 1][1]


import numpy as np

class Solution:

	def dp_sol(self, N, S):
		num = (N + 1) // 2
		dp = np.array([[[0] * num] * num] * 2)
		for i in range(num):
			if S[2 * i] == 'T':
				dp[1][i][i] = 1
				dp[0][i][i] = 0
			else:
				dp[1][i][i] = 0
				dp[0][i][i] = 1
		for i in range(1, num):
			for j in range(i - 1, -1, -1):
				for k in range(j, i):
					temp1 = 0
					temp2 = 0
					if S[2 * k + 1] == '|':
						temp2 = dp[1][j][k] * dp[1][k + 1][i] + dp[0][j][k] * dp[1][k + 1][i] + dp[1][j][k] * dp[0][k + 1][i]
						temp1 = dp[0][j][k] * dp[0][k + 1][i]
					if S[2 * k + 1] == '&':
						temp2 = dp[1][j][k] * dp[1][k + 1][i]
						temp1 = dp[0][j][k] * dp[0][k + 1][i] + dp[0][j][k] * dp[1][k + 1][i] + dp[1][j][k] * dp[0][k + 1][i]
					if S[2 * k + 1] == '^':
						temp2 = dp[0][j][k] * dp[1][k + 1][i] + dp[1][j][k] * dp[0][k + 1][i]
						temp1 = dp[0][j][k] * dp[0][k + 1][i] + dp[1][j][k] * dp[1][k + 1][i]
					dp[1][j][i] = dp[1][j][i] + temp2 % 1003
					dp[0][j][i] = dp[0][j][i] + temp1 % 1003
		return dp[1][0][num - 1] % 1003

	def countWays(self, N, S):
		return self.dp_sol(N, S)


class Solution:

	def countWays(self, N, S):
		dp = dict()
		return self.f(S, 0, N - 1, True, dp) % 1003

	def f(self, s, i, j, isTrue, dp):
		if i > j:
			return False
		if i == j:
			if isTrue == True:
				return int(s[i] == 'T')
			else:
				return int(s[i] == 'F')
		key = (i, j, isTrue)
		if key in dp:
			return dp[key]
		ans = 0
		for k in range(i + 1, j, 2):
			lf = self.f(s, i, k - 1, False, dp)
			lt = self.f(s, i, k - 1, True, dp)
			rf = self.f(s, k + 1, j, False, dp)
			rt = self.f(s, k + 1, j, True, dp)
			if s[k] == '&':
				if isTrue:
					ans += lt * rt
				else:
					ans += lt * rf + lf * rt + lf * rf
			elif s[k] == '|':
				if isTrue:
					ans += lt * rf + lf * rt + lt * rt
				else:
					ans += lf * rf
			elif s[k] == '^':
				if isTrue:
					ans += lf * rt + lt * rf
				else:
					ans += lf * rf + lt * rt
		dp[key] = ans % 1003
		return ans % 1003


class Solution:

	def countWays(self, N, S):

		def boole(start, end, boolmark, mod):
			if start == end:
				if boolmark == 1:
					if S[start] == 'T':
						return 1
					return 0
				else:
					if S[start] == 'F':
						return 1
					return 0
			if memo[start][end][boolmark] != -1:
				return memo[start][end][boolmark]
			tempAns = 0
			for i in range(start + 1, end, 2):
				leftFalse = boole(start, i - 1, 0, mod)
				rightTrue = boole(i + 1, end, 1, mod)
				leftTrue = boole(start, i - 1, 1, mod)
				rightFalse = boole(i + 1, end, 0, mod)
				if S[i] == '|':
					if boolmark == 1:
						tempAns += leftFalse * rightTrue + leftTrue * rightFalse + leftTrue * rightTrue
					else:
						tempAns += leftFalse * rightFalse
				elif S[i] == '&':
					if boolmark == 1:
						tempAns += leftTrue * rightTrue
					else:
						tempAns += leftTrue * rightFalse + leftFalse * rightTrue + leftFalse * rightFalse
				elif S[i] == '^':
					if boolmark == 1:
						tempAns += leftTrue * rightFalse + rightTrue * leftFalse
					else:
						tempAns += leftTrue * rightTrue + leftFalse * rightFalse
			memo[start][end][boolmark] = tempAns % mod
			return tempAns % mod
		memo = [[[-1, -1] for j in range(N)] for i in range(N)]
		return boole(0, N - 1, 1, 1003)


class Solution:

	def countWays(self, N, S):
		dp = [[[-1 for i in range(2)] for j in range(N)] for k in range(N)]
		return self.f(0, N - 1, S, dp, 1)

	def f(self, i, j, S, dp, isTrue):
		if i > j:
			return 0
		if i == j:
			if isTrue == 1:
				if S[i] == 'T':
					return 1
				else:
					return 0
			elif S[i] == 'F':
				return 1
			else:
				return 0
		if dp[i][j][isTrue] != -1:
			return dp[i][j][isTrue]
		count = 0
		for k in range(i + 1, j, 2):
			lt = self.f(i, k - 1, S, dp, 1)
			lf = self.f(i, k - 1, S, dp, 0)
			rt = self.f(k + 1, j, S, dp, 1)
			rf = self.f(k + 1, j, S, dp, 0)
			if S[k] == '&':
				if isTrue:
					count = (count + lt * rt) % 1003
				else:
					count = (count + lf * rt + lt * rf + lf * rf) % 1003
			if S[k] == '|':
				if isTrue:
					count = (count + lt * rt + lf * rt + lt * rf) % 1003
				else:
					count = (count + lf * rf) % 1003
			if S[k] == '^':
				if isTrue:
					count = (count + lf * rt + lt * rf) % 1003
				else:
					count = (count + lf * rf + lt * rt) % 1003
		dp[i][j][isTrue] = count % 1003
		return dp[i][j][isTrue]


class Solution:

	def countWays(self, N, S):
		true = [[0] * (N + 1) for _ in range(N + 1)]
		false = [[0] * (N + 1) for _ in range(N + 1)]
		for i in range(1, N + 1):
			if S[i - 1] == 'T':
				true[i][i] = 1
			else:
				false[i][i] = 1
		for length in range(3, N + 1, 2):
			for start in range(1, N - length + 2, 2):
				end = start + length - 1
				for k in range(start + 1, end, 2):
					operator = S[k - 1]
					if operator == '&':
						true[start][end] += true[start][k - 1] * true[k + 1][end]
						false[start][end] += true[start][k - 1] * false[k + 1][end] + false[start][k - 1] * true[k + 1][end] + false[start][k - 1] * false[k + 1][end]
					elif operator == '|':
						true[start][end] += true[start][k - 1] * true[k + 1][end] + true[start][k - 1] * false[k + 1][end] + false[start][k - 1] * true[k + 1][end]
						false[start][end] += false[start][k - 1] * false[k + 1][end]
					elif operator == '^':
						true[start][end] += true[start][k - 1] * false[k + 1][end] + false[start][k - 1] * true[k + 1][end]
						false[start][end] += true[start][k - 1] * true[k + 1][end] + false[start][k - 1] * false[k + 1][end]
		return true[1][N] % 1003


class Solution:

	def countWays(self, N, S):
		mod = 1003
		dp = []
		for i in range(201):
			temp = []
			for j in range(201):
				x = [-1] * 2
				temp.append(x)
			dp.append(temp)

		def solve(S, i, j, isTrue):
			if i > j:
				dp[i][j][isTrue] = 0
				return 0
			if i == j:
				if isTrue:
					if S[i] == 'T':
						dp[i][j][isTrue] = 1
					else:
						dp[i][j][isTrue] = 0
				elif S[i] == 'F':
					dp[i][j][isTrue] = 1
				else:
					dp[i][j][isTrue] = 0
				return dp[i][j][isTrue]
			if dp[i][j][isTrue] != -1:
				return dp[i][j][isTrue]
			ans = 0
			for k in range(i + 1, j, 2):
				if S[k] == '|':
					if isTrue:
						ans += (solve(S, i, k - 1, 1) * solve(S, k + 1, j, 1) + solve(S, i, k - 1, 1) * solve(S, k + 1, j, 0) + solve(S, i, k - 1, 0) * solve(S, k + 1, j, 1)) % mod
					else:
						ans += solve(S, i, k - 1, 0) * solve(S, k + 1, j, 0) % mod
				elif S[k] == '&':
					if isTrue:
						ans += solve(S, i, k - 1, 1) * solve(S, k + 1, j, 1) % mod
					else:
						ans += (solve(S, i, k - 1, 0) * solve(S, k + 1, j, 0) + solve(S, i, k - 1, 0) * solve(S, k + 1, j, 1) + solve(S, i, k - 1, 1) * solve(S, k + 1, j, 0)) % mod
				elif isTrue:
					ans += (solve(S, i, k - 1, 0) * solve(S, k + 1, j, 1) + solve(S, i, k - 1, 1) * solve(S, k + 1, j, 0)) % mod
				else:
					ans += (solve(S, i, k - 1, 1) * solve(S, k + 1, j, 1) + solve(S, i, k - 1, 0) * solve(S, k + 1, j, 0)) % mod
			dp[i][j][isTrue] = ans % mod
			return dp[i][j][isTrue]
		return solve(S, 0, N - 1, 1)


class Solution:
	t = [[[-1 for _ in range(2)] for _ in range(201)] for _ in range(201)]

	def solve(self, s, i, j, state):
		if i > j:
			return 0
		if self.t[i][j][state] != -1:
			return self.t[i][j][state]
		if i == j:
			if state == True:
				return 1 if s[i] == 'T' else 0
			else:
				return 1 if s[i] == 'F' else 0
		count = 0
		for k in range(i + 1, j, 2):
			lt = self.solve(s, i, k - 1, True)
			lf = self.solve(s, i, k - 1, False)
			rt = self.solve(s, k + 1, j, True)
			rf = self.solve(s, k + 1, j, False)
			if s[k] == '&':
				if state:
					count += lt * rt
				else:
					count += lf * rf + lf * rt + lt * rf
			elif s[k] == '|':
				if state:
					count += lt * rt + lt * rf + lf * rt
				else:
					count += lf * rf
			elif s[k] == '^':
				if state:
					count += lt * rf + lf * rt
				else:
					count += lt * rt + lf * rf
		self.t[i][j][state] = count % 1003
		return self.t[i][j][state]

	def countWays(self, N, S):
		self.t = [[[-1 for _ in range(2)] for _ in range(201)] for _ in range(201)]
		return self.solve(S, 0, N - 1, True)


from functools import lru_cache

@lru_cache(maxsize=None)
def helper(s, i, j, exp):
	if i > j:
		return False
	if i == j:
		if exp == True:
			return s[i] == 'T'
		else:
			return s[i] == 'F'
	count = 0
	for k in range(i + 1, j):
		lt = helper(s, i, k - 1, True)
		lf = helper(s, i, k - 1, False)
		rt = helper(s, k + 1, j, True)
		rf = helper(s, k + 1, j, False)
		if s[k] == '|':
			if exp == True:
				count += lt * rf + rt * lf + rt * lt
			else:
				count += rf * lf
		elif s[k] == '&':
			if exp == True:
				count += lt * rt
			else:
				count += lt * rf + rt * lf + rf * lf
		elif exp == True:
			count += lt * rf + rt * lf
		else:
			count += lt * rt + lf * rf
	return count % 1003

class Solution:

	def countWays(self, N, S):
		if S == 'T':
			return 1
		return helper(S, 0, N - 1, True)


from functools import lru_cache

class Solution:

	def countWays(self, N, expr):
		MOD = 10 ** 3 + 3

		@lru_cache(None)
		def fun(i=0, j=N - 1, isTrue=1):
			if i > j:
				return 0
			if i == j:
				return int(expr[i] == ['F', 'T'][isTrue])
			ways = 0
			for k in range(i + 1, j, 2):
				(lT, lF, rT, rF) = map(fun, (i, i, k + 1, k + 1), (k - 1, k - 1, j, j), (1, 0, 1, 0))
				if expr[k] == '&':
					ways += [lF * (rF + rT) + rF * lT, lT * rT][isTrue]
				elif expr[k] == '|':
					ways += [lF * rF, lT * (rF + rT) + rT * lF][isTrue]
				else:
					ways += [lT * rT + lF * rF, lT * rF + lF * rT][isTrue]
				ways %= MOD
			return ways
		return fun()


class Solution:

	def countWays(self, N, S):
		d1 = dict()

		def dfs(i, j):
			if i == j:
				if S[i] == 'T':
					return (1, 0)
				else:
					return (0, 1)
			if d1.get((i, j)) != None:
				return d1[i, j]
			(T, F) = (0, 0)
			for k in range(i + 1, j, 2):
				(a, b) = dfs(i, k - 1)
				(c, d) = dfs(k + 1, j)
				if S[k] == '|':
					T = T + a * c + a * d + b * c
					F = F + b * d
				if S[k] == '&':
					T = T + a * c
					F = F + b * c + a * d + b * d
				if S[k] == '^':
					T = T + a * d + c * b
					F = F + a * c + b * d
			d1[i, j] = (T, F)
			return (T, F)
		(a, b) = dfs(0, N - 1)
		return a % 1003


class Solution:

	def countWays(self, n, s):
		dp = [[[-1] * 2 for i in range(n)] for j in range(n)]

		def findsol(i, j, istrue, s):
			if i > j:
				return 0
			if i == j:
				if istrue == 1:
					if s[i] == 'T':
						return 1
					else:
						return 0
				elif s[i] == 'F':
					return 1
				else:
					return 0
			if dp[i][j][istrue] != -1:
				return dp[i][j][istrue]
			ways = 0
			for ind in range(i + 1, j, 2):
				lt = findsol(i, ind - 1, 1, s) % 1003
				lf = findsol(i, ind - 1, 0, s) % 1003
				rt = findsol(ind + 1, j, 1, s) % 1003
				rf = findsol(ind + 1, j, 0, s) % 1003
				if s[ind] == '&':
					if istrue == 1:
						ways += lt * rt
					else:
						ways += lf * rt + rf * lt + lf * rf
					ways = ways % 1003
				elif s[ind] == '|':
					if istrue == 1:
						ways += lt * rf + lf * rt + lt * rt
					else:
						ways += lf * rf
					ways = ways % 1003
				else:
					if istrue == 1:
						ways += lt * rf + lf * rt
					else:
						ways += lt * rt + rf * lf
					ways = ways % 1003
			dp[i][j][istrue] = ways
			return ways
		return findsol(0, n - 1, 1, s)


class Solution:

	def countWays(self, N, S):
		sDict = {}

		def solve(i, j, isTrue):
			key = str(i) + '_' + str(j) + '_' + str(isTrue)
			if i > j:
				sDict[key] = 0
				return 0
			elif i == j:
				if isTrue and S[i] == 'T':
					sDict[key] = sDict.get(key, 0) + 1
					return 1
				elif not isTrue and S[i] == 'F':
					sDict[key] = sDict.get(key, 0) + 1
					return 1
				else:
					sDict[key] = 0
					return 0
			if key in sDict:
				return sDict[key]
			temp = 0
			for k in range(i + 1, j, 2):
				key1 = str(i) + '_' + str(k - 1) + '_' + str(1)
				key2 = str(i) + '_' + str(k - 1) + '_' + str(0)
				key3 = str(k + 1) + '_' + str(j) + '_' + str(1)
				key4 = str(k + 1) + '_' + str(j) + '_' + str(0)
				if key1 in sDict:
					lt = sDict[key1]
				else:
					lt = solve(i, k - 1, 1)
					sDict[key1] = lt
				if key2 in sDict:
					lf = sDict[key2]
				else:
					lf = solve(i, k - 1, 0)
					sDict[key2] = lf
				if key3 in sDict:
					rt = sDict[key3]
				else:
					rt = solve(k + 1, j, 1)
					sDict[key3] = rt
				if key4 in sDict:
					rf = sDict[key4]
				else:
					rf = solve(k + 1, j, 0)
					sDict[key4] = rf
				if S[k] == '&':
					if isTrue:
						temp = temp + lt * rt
					else:
						temp = temp + lt * rf + lf * rf + lf * rt
				elif S[k] == '|':
					if isTrue:
						temp = temp + lt * rf + lt * rt + lf * rt
					else:
						temp = temp + lf * rf
				elif S[k] == '^':
					if isTrue:
						temp = temp + lt * rf + lf * rt
					else:
						temp = temp + lt * rt + lf * rf
				sDict[key] = temp
			return sDict[key] % 1003
		return solve(0, N - 1, 1)


class Solution:

	def __init__(self):
		self.dp = []
		for i in range(201):
			self.l = []
			for j in range(201):
				self.l += [[-1] * 2]
			self.dp += [self.l]

	def countWays(self, N, S):
		return self.solve(S, 1, 0, N - 1)

	def solve(self, s, i, b, e):
		if b == e:
			if s[b] == 'T' and i == 1 or (s[b] == 'F' and i == 0):
				return 1
			else:
				return 0
		elif self.dp[b][e][i] != -1:
			return self.dp[b][e][i]
		s1 = 0
		for j in range(b, e + 1):
			if s[j] == '|':
				if i == 1:
					s1 += self.solve(s, 1, b, j - 1) * (self.solve(s, 1, j + 1, e) + self.solve(s, 0, j + 1, e))
					s1 += self.solve(s, 0, b, j - 1) * self.solve(s, 1, j + 1, e)
				else:
					s1 += self.solve(s, 0, b, j - 1) * self.solve(s, 0, j + 1, e)
			elif s[j] == '&':
				if i == 0:
					s1 += self.solve(s, 1, b, j - 1) * self.solve(s, 0, j + 1, e)
					s1 += self.solve(s, 0, b, j - 1) * (self.solve(s, 1, j + 1, e) + self.solve(s, 0, j + 1, e))
				else:
					s1 += self.solve(s, 1, b, j - 1) * self.solve(s, 1, j + 1, e)
			elif s[j] == '^':
				if i == 0:
					s1 += self.solve(s, 1, b, j - 1) * self.solve(s, 1, j + 1, e)
					s1 += self.solve(s, 0, b, j - 1) * self.solve(s, 0, j + 1, e)
				else:
					s1 += self.solve(s, 1, b, j - 1) * self.solve(s, 0, j + 1, e)
					s1 += self.solve(s, 0, b, j - 1) * self.solve(s, 1, j + 1, e)
		self.dp[b][e][i] = s1 % 1003
		return s1 % 1003


class Solution:

	def countWays(self, N, S):
		mod = 1003

		def helper(s, i, j, exp, t):
			if i > j:
				return 0
			if i == j:
				if exp:
					return 1 if s[i] == 'T' else 0
				else:
					return 1 if s[i] == 'F' else 0
			if t[exp][i][j] != -1:
				return t[exp][i][j]
			count = 0
			for k in range(i + 1, j):
				lt = helper(s, i, k - 1, 1, t)
				lf = helper(s, i, k - 1, 0, t)
				rt = helper(s, k + 1, j, 1, t)
				rf = helper(s, k + 1, j, 0, t)
				if s[k] == '|':
					if exp:
						count += lt * rf + rt * lf + rt * lt
					else:
						count += rf * lf
				elif s[k] == '&':
					if exp:
						count += lt * rt
					else:
						count += lt * rf + rt * lf + rf * lf
				elif exp:
					count += lt * rf + rt * lf
				else:
					count += lt * rt + lf * rf
			t[exp][i][j] = count % mod
			return count % mod
		t = [[[-1 for i in range(202)] for j in range(202)] for _ in range(2)]
		return helper(S, 0, N - 1, 1, t)
0


class Solution:

	def countWays(self, N, S):
		Tcount = [[0] * N for _ in range(N)]
		Fcount = [[0] * N for _ in range(N)]
		for i in range(0, N, 2):
			if S[i] == 'T':
				Tcount[i][i] = 1
			else:
				Fcount[i][i] = 1
		for L in range(3, N + 1, 2):
			for i in range(0, N - L + 1, 2):
				j = i + L - 1
				for k in range(i, j - 1, 2):
					op = S[k + 1]
					(lt, rt) = (Tcount[i][k], Tcount[k + 2][j])
					(lf, rf) = (Fcount[i][k], Fcount[k + 2][j])
					if op == '&':
						Tcount[i][j] += lt * rt
						Fcount[i][j] += lf * rf + lf * rt + lt * rf
					if op == '|':
						Tcount[i][j] += lt * rt + lf * rt + lt * rf
						Fcount[i][j] += lf * rf
					if op == '^':
						Tcount[i][j] += lf * rt + lt * rf
						Fcount[i][j] += lt * rt + lf * rf
		return Tcount[0][N - 1] % 1003


import sys
sys.setrecursionlimit(100000)

class Solution:

	def countWays(self, N, S):

		def check(i, j, IsTrue, dp):
			if i > j:
				return 0
			if i == j:
				if IsTrue == 1:
					if S[i] == 'T':
						return 1
				elif S[i] == 'F':
					return 1
			if dp[i][j][IsTrue] != -1:
				return dp[i][j][IsTrue]
			count = 0
			for k in range(i + 1, j, 2):
				LT = check(i, k - 1, 1, dp)
				LF = check(i, k - 1, 0, dp)
				RT = check(k + 1, j, 1, dp)
				RF = check(k + 1, j, 0, dp)
				if S[k] == '&':
					if IsTrue == 1:
						count += LT * RT
					else:
						count += LF * RF + LF * RT + LT * RF
				elif S[k] == '|':
					if IsTrue == 1:
						count += RT * LT + RT * LF + LT * RF
					else:
						count += LF * RF
				elif IsTrue == 1:
					count += RT * LF + LT * RF
				else:
					count += RT * LT + RF * LF
			dp[i][j][IsTrue] = count % 1003
			return count % 1003
		n = len(S)
		dp = [[[-1 for i in range(2)] for j in range(n + 1)] for k in range(n + 1)]
		return check(0, n - 1, 1, dp)


class Solution:

	def countWays(self, N, S):

		def solve(string, i, j, isTrue, dp):
			if i > j:
				return 0
			key = str(i) + str(j) + str(isTrue)
			if key in dp:
				return dp[key]
			if i == j:
				if isTrue:
					if string[i] == 'T':
						dp[key] = 1
					else:
						dp[key] = 0
				elif string[i] == 'F':
					dp[key] = 1
				else:
					dp[key] = 0
				return dp[key]
			ans = 0
			for k in range(i + 1, j, 2):
				lT = solve(string, i, k - 1, True, dp)
				lF = solve(string, i, k - 1, False, dp)
				rT = solve(string, k + 1, j, True, dp)
				rF = solve(string, k + 1, j, False, dp)
				if string[k] == '&':
					if isTrue:
						ans += lT * rT
					else:
						ans += lT * rF + lF * rT + lF * rF
				elif string[k] == '|':
					if isTrue:
						ans += lT * rT + lT * rF + lF * rT
					else:
						ans += lF * rF
				elif isTrue:
					ans += lT * rF + lF * rT
				else:
					ans += lT * rT + lF * rF
			dp[key] = ans % 1003
			return dp[key]
		n = len(S)
		dp = {}
		ans = solve(S, 0, n - 1, True, dp)
		return ans


class Solution:

	def countWays(self, n, s):
		mod = int(1003)
		dp = [[[-1] * 2 for i in range(n + 2)] for j in range(n + 2)]

		def f(i, j, needTrue):
			if i > j:
				return 0
			if i == j:
				if needTrue:
					return int(s[i] == 'T')
				else:
					return int(s[i] == 'F')
			if dp[i][j][needTrue] != -1:
				return dp[i][j][needTrue]
			ways = 0
			for k in range(i + 1, j, 2):
				(lt, rt) = (f(i, k - 1, 1), f(k + 1, j, 1))
				(lf, rf) = (f(i, k - 1, 0), f(k + 1, j, 0))
				if s[k] == '&':
					if needTrue:
						ways += lt * rt
					else:
						ways += lt * rf + lf * rt + lf * rf
				elif s[k] == '|':
					if needTrue:
						ways += lt * rf + lf * rt + lt * rt
					else:
						ways += lf * rf
				elif needTrue:
					ways += lt * rf + lf * rt
				else:
					ways += lf * rf + lt * rt
				ways = ways % mod
			dp[i][j][needTrue] = ways
			return ways
		return f(0, n - 1, 1)


class Solution:

	def countWays(self, n, S):
		T = [[0 for i in range(n)] for j in range(n)]
		F = [[0 for i in range(n)] for j in range(n)]
		for i in range(n):
			if S[i] == 'T':
				T[i][i] = 1
			elif S[i] == 'F':
				F[i][i] = 1
		for L in range(3, n + 1, 2):
			for i in range(0, n - L + 1, 2):
				j = i + L - 1
				for k in range(i + 1, j, 2):
					tik = T[i][k - 1] + F[i][k - 1]
					tkj = T[k + 1][j] + F[k + 1][j]
					if S[k] == '&':
						T[i][j] += T[i][k - 1] * T[k + 1][j]
						F[i][j] += tik * tkj - T[i][k - 1] * T[k + 1][j]
					elif S[k] == '|':
						F[i][j] += F[i][k - 1] * F[k + 1][j]
						T[i][j] += tik * tkj - F[i][k - 1] * F[k + 1][j]
					elif S[k] == '^':
						T[i][j] += F[i][k - 1] * T[k + 1][j] + T[i][k - 1] * F[k + 1][j]
						F[i][j] += T[i][k - 1] * T[k + 1][j] + F[i][k - 1] * F[k + 1][j]
		return T[0][n - 1] % 1003


from functools import lru_cache

class Solution:

	def countWays(self, N, S):
		mod = 1003

		@lru_cache(None)
		def recurs_sol(left, right):
			if left > right:
				return (0, 0)
			if left == right:
				return (1 if S[left] == 'T' else 0, 1 if S[left] == 'F' else 0)
			trues = falses = 0
			for k in range(left + 1, right, 2):
				(left_true, left_false) = recurs_sol(left, k - 1)
				(right_true, right_false) = recurs_sol(k + 1, right)
				if S[k] == '|':
					trues += left_true * right_true + left_true * right_false + left_false * right_true
					falses += left_false * right_false
				elif S[k] == '&':
					trues += left_true * right_true
					falses += left_false * right_false + left_true * right_false + left_false * right_true
				elif S[k] == '^':
					trues += left_true * right_false + left_false * right_true
					falses += left_true * right_true + left_false * right_false
				trues %= mod
				falses %= mod
			return (trues % mod, falses % mod)
		return recurs_sol(0, N - 1)[0]


class Solution:

	def countWays(self, N, S):
		i = 0
		j = N - 1
		maps = {}
		dp = [[[-1 for _ in range(2)] for _ in range(N + 1)] for _ in range(N + 1)]
		return solve(S, i, j, 1, dp)

def solve(S, i, j, istrue, dp):
	if i > j:
		return 0
	if i == j:
		if istrue:
			if S[i] == 'T':
				return 1
			else:
				return 0
		elif S[i] == 'F':
			return 1
		else:
			return 0
	if dp[i][j][istrue] != -1:
		return dp[i][j][istrue]
	ans = 0
	for k in range(i + 1, j, 2):
		leftT = solve(S, i, k - 1, 1, dp)
		leftF = solve(S, i, k - 1, 0, dp)
		rightT = solve(S, k + 1, j, 1, dp)
		rightF = solve(S, k + 1, j, 0, dp)
		if S[k] == '^':
			if istrue:
				ans += leftT * rightF + leftF * rightT
			else:
				ans += leftT * rightT + leftF * rightF
		elif S[k] == '&':
			if istrue:
				ans += leftT * rightT
			else:
				ans += leftT * rightF + leftF * rightT + leftF * rightF
		elif S[k] == '|':
			if istrue:
				ans += leftT * rightF + leftF * rightT + leftT * rightT
			else:
				ans += leftF * rightF
	dp[i][j][istrue] = ans % 1003
	return dp[i][j][istrue]


class Solution:

	def countWays(self, N, S):
		(string, operators) = ('', '')
		for i in S:
			if i == 'T' or i == 'F':
				string += i
			else:
				operators += i
		dp_true = [[0 for i in range(len(string))] for j in range(len(string))]
		dp_false = [[0 for i in range(len(string))] for j in range(len(string))]
		for k in range(len(string)):
			(i, j) = (0, k)
			while j < len(string):
				if k == 0:
					if string[i] == 'T':
						dp_true[i][j] = 1
						dp_false[i][j] = 0
					else:
						dp_true[i][j] = 0
						dp_false[i][j] = 1
				else:
					for var in range(i, j):
						left_true_count = dp_true[i][var]
						right_true_count = dp_true[var + 1][j]
						left_false_count = dp_false[i][var]
						right_false_count = dp_false[var + 1][j]
						if operators[var] == '&':
							dp_true[i][j] += left_true_count * right_true_count
							dp_false[i][j] += left_true_count * right_false_count + left_false_count * right_true_count + left_false_count * right_false_count
						elif operators[var] == '|':
							dp_true[i][j] += left_true_count * right_true_count + left_true_count * right_false_count + left_false_count * right_true_count
							dp_false[i][j] += left_false_count * right_false_count
						else:
							dp_true[i][j] += left_true_count * right_false_count + left_false_count * right_true_count
							dp_false[i][j] += left_true_count * right_true_count + left_false_count * right_false_count
				i += 1
				j += 1
		return dp_true[0][-1] % 1003


class Solution:

	def countWays(self, N, S):
		(string, operators) = ('', '')
		for i in S:
			if i == 'T' or i == 'F':
				string += i
			else:
				operators += i
		dpt = [[0 for i in range(len(string))] for j in range(len(string))]
		dpf = [[0 for i in range(len(string))] for j in range(len(string))]
		for k in range(len(string)):
			(i, j) = (0, k)
			while j < len(string):
				if k == 0:
					if string[i] == 'T':
						dpt[i][j] = 1
						dpf[i][j] = 0
					else:
						dpt[i][j] = 0
						dpf[i][j] = 1
				else:
					for var in range(i, j):
						ltc = dpt[i][var]
						rtc = dpt[var + 1][j]
						lfc = dpf[i][var]
						rfc = dpf[var + 1][j]
						if operators[var] == '&':
							dpt[i][j] += ltc * rtc
							dpf[i][j] += ltc * rfc + lfc * rtc + lfc * rfc
						elif operators[var] == '|':
							dpt[i][j] += ltc * rtc + ltc * rfc + lfc * rtc
							dpf[i][j] += lfc * rfc
						else:
							dpt[i][j] += ltc * rfc + lfc * rtc
							dpf[i][j] += ltc * rtc + lfc * rfc
				i += 1
				j += 1
		return dpt[0][-1] % 1003


class Solution:

	def countWays(self, n, s):
		mod = 1003
		dp = {}

		def fun(i, j, isTrue):
			if i > j:
				return 0
			if i == j:
				if isTrue:
					return 1 if s[i] == 'T' else 0
				else:
					return 1 if s[i] == 'F' else 0
			if (i, j, isTrue) in dp:
				return dp[i, j, isTrue]
			true = false = 0
			for k in range(i + 1, j, 2):
				lT = fun(i, k - 1, True)
				lF = fun(i, k - 1, False)
				rT = fun(k + 1, j, True)
				rF = fun(k + 1, j, False)
				if s[k] == '&':
					true += lT * rT
					false += lT * rF + lF * rT + lF * rF
				elif s[k] == '|':
					true += lT * rF + lF * rT + lT * rT
					false += lF * rF
				else:
					true += lT * rF + lF * rT
					false += lT * rT + lF * rF
			if isTrue:
				dp[i, j, True] = true
			else:
				dp[i, j, False] = false
			return dp[i, j, isTrue]
		return fun(0, n - 1, True) % mod


import sys
sys.setrecursionlimit(100000)

class Solution:

	def __count_ways_helper(self, i, j, string):
		if i == j:
			self.dp[i][j] = [int(string[i] == 'T'), int(string[i] == 'F')]
			return self.dp[i][j]
		if self.dp[i][j] == None:
			self.dp[i][j] = [0, 0]
			for k in range(i, j + 1):
				if string[k] != 'T' and string[k] != 'F':
					(left_true_count, left_false_count) = self.__count_ways_helper(i, k - 1, string)
					(right_true_count, right_false_count) = self.__count_ways_helper(k + 1, j, string)
					if string[k] == '&':
						self.dp[i][j][0] += left_true_count * right_true_count
						self.dp[i][j][1] += left_true_count * right_false_count + left_false_count * right_true_count + left_false_count * right_false_count
					elif string[k] == '|':
						self.dp[i][j][0] += left_true_count * right_false_count + left_false_count * right_true_count + left_true_count * right_true_count
						self.dp[i][j][1] += left_false_count * right_false_count
					elif string[k] == '^':
						self.dp[i][j][0] += left_true_count * right_false_count + left_false_count * right_true_count
						self.dp[i][j][1] += left_false_count * right_false_count + left_true_count * right_true_count
		return self.dp[i][j]

	def countWays(self, N, S):
		self.dp = [[None for j in range(N)] for i in range(N)]
		return self.__count_ways_helper(0, N - 1, S)[0] % 1003


mod = 1003

class Solution:

	def recur(self, i, j, isTrue, S, dp):
		if i > j:
			return 0
		if i == j:
			if isTrue:
				return 1 if S[i] == 'T' else 0
			else:
				return 1 if S[i] == 'F' else 0
		if dp[isTrue][i][j] != -1:
			return dp[isTrue][i][j]
		ways = 0
		for ind in range(i + 1, j, 2):
			lT = self.recur(i, ind - 1, 1, S, dp)
			lF = self.recur(i, ind - 1, 0, S, dp)
			rT = self.recur(ind + 1, j, 1, S, dp)
			rF = self.recur(ind + 1, j, 0, S, dp)
			if S[ind] == '&':
				if isTrue:
					ways += rT * lT
				else:
					ways += rT * lF + rF * lT + rF * lF
			elif S[ind] == '|':
				if isTrue:
					ways += lT * rT + lT * rF + lF * rT
				else:
					ways += rF * lF
			elif S[ind] == '^':
				if isTrue:
					ways += lT * rF + lF * rT
				else:
					ways += lT * rT + lF * rF
		dp[isTrue][i][j] = ways % mod
		return ways % mod

	def countWays(self, N, S):
		dp = [[[-1 for i in range(N)] for j in range(N)] for k in range(2)]
		return self.recur(0, N - 1, 1, S, dp)


class Solution:

	def countWays(self, N, S):

		def solve(i, j, flag):
			if i > j:
				return 0
			if i == j:
				if flag:
					if S[i] == 'T':
						return 1
				elif S[i] == 'F':
					return 1
			if dp[i][j][flag] != -1:
				return dp[i][j][flag]
			count = 0
			for k in range(i + 1, j, 2):
				left_t = solve(i, k - 1, True)
				left_f = solve(i, k - 1, False)
				right_t = solve(k + 1, j, True)
				right_f = solve(k + 1, j, False)
				if S[k] == '|':
					if flag:
						count += left_t * right_t + left_f * right_t + left_t * right_f
					else:
						count += left_f * right_f
				if S[k] == '&':
					if flag:
						count += left_t * right_t
					else:
						count += left_f * right_f + left_f * right_t + left_t * right_f
				if S[k] == '^':
					if flag:
						count += left_t * right_f + left_f * right_t
					else:
						count += left_t * right_t + left_f * right_f
			dp[i][j][flag] = count % MOD
			return dp[i][j][flag]
		MOD = 1003
		dp = [[[-1] * 2 for j in range(N + 1)] for i in range(N + 1)]
		return solve(0, N - 1, True)


def fun(i, j, isTrue, s, dp):
	if i > j:
		return 0
	if dp[i][j][isTrue] != -1:
		return dp[i][j][isTrue]
	if i == j:
		if isTrue:
			return (s[i] == 'T') + 0
		else:
			return (s[i] == 'F') + 0
	ways = 0
	for k in range(i + 1, j, 2):
		lt = fun(i, k - 1, 1, s, dp)
		lf = fun(i, k - 1, 0, s, dp)
		rt = fun(k + 1, j, 1, s, dp)
		rf = fun(k + 1, j, 0, s, dp)
		if s[k] == '&':
			if isTrue:
				ways += lt * rt
			else:
				ways += lt * rf + rt * lf + rf * lf
		if s[k] == '|':
			if isTrue:
				ways += lt * rt + lt * rf + rt * lf
			else:
				ways += rf * lf
		if s[k] == '^':
			if isTrue:
				ways += lf * rt + lt * rf
			else:
				ways += lt * rt + rf * lf
		ways = ways % 1003
	dp[i][j][isTrue] = ways
	return ways

class Solution:

	def countWays(self, N, S):
		dp = [[[-1] * 2 for i in range(N)] for j in range(N)]
		return fun(0, N - 1, True, S, dp)


class Solution:

	def countWays(self, N, S):

		def solve(s, i, j, isbool):
			if i > j:
				return False
			if i == j:
				if isbool == True:
					return 1 if s[i] == 'T' else 0
				else:
					return 1 if s[i] == 'F' else 0
			tmp = str(i) + ' ' + str(j) + ' ' + str(isbool)
			if dp[i][j][isbool] != -1:
				return dp[i][j][isbool] % 1003
			ans = 0
			for k in range(i + 1, j, 2):
				lf = solve(s, i, k - 1, False)
				lt = solve(s, i, k - 1, True)
				rf = solve(s, k + 1, j, False)
				rt = solve(s, k + 1, j, True)
				if s[k] == '&':
					if isbool == True:
						ans += lt * rt
					else:
						ans += lt * rf + rt * lf + lf * rf
				if s[k] == '|':
					if isbool == True:
						ans += lt * rt + lt * rf + rt * lf
					else:
						ans += lf * rf
				if s[k] == '^':
					if isbool == True:
						ans += lt * rf + lf * rt
					else:
						ans += lt * rt + lf * rf
			dp[i][j][isbool] = ans
			return dp[i][j][isbool] % 1003
		dp = [[[-1] * 2 for i in range(N + 1)] for j in range(N + 1)]
		return solve(S, 0, N - 1, True)


class Solution:

	def countWays(self, n, str):
		s1 = ''
		s2 = ''
		for i in range(n):
			if str[i] == 'T' or str[i] == 'F':
				s1 += str[i]
			else:
				s2 += str[i]
		n = len(s1)
		mod = 1003
		truedp = [[0] * n for i in range(n)]
		falsedp = [[0] * n for i in range(n)]
		for g in range(0, n):
			for (i, j) in zip(range(0, n), range(g, n)):
				if g == 0:
					if s1[i] == 'T':
						truedp[i][j] = 1
						falsedp[i][j] = 0
					else:
						truedp[i][j] = 0
						falsedp[i][j] = 1
				elif g == 1:
					if s2[i] == '&':
						if s1[i] == 'T' and s1[j] == 'T':
							truedp[i][j] = 1
							falsedp[i][j] = 0
						else:
							truedp[i][j] = 0
							falsedp[i][j] = 1
					elif s2[i] == '|':
						if s1[i] == 'T' or s1[j] == 'T':
							truedp[i][j] = 1
							falsedp[i][j] = 0
						else:
							truedp[i][j] = 0
							falsedp[i][j] = 1
					elif s1[i] == 'T' and s1[j] == 'T' or (s1[i] == 'F' and s1[j] == 'F'):
						truedp[i][j] = 0
						falsedp[i][j] = 1
					else:
						truedp[i][j] = 1
						falsedp[i][j] = 0
				else:
					for k in range(i, j):
						ltc = truedp[i][k]
						rtc = truedp[k + 1][j]
						lfc = falsedp[i][k]
						rfc = falsedp[k + 1][j]
						if s2[k] == '&':
							truedp[i][j] += ltc * rtc
							falsedp[i][j] += ltc * rfc + lfc * rtc + lfc * rfc
						elif s2[k] == '|':
							truedp[i][j] += ltc * rtc + ltc * rfc + lfc * rtc
							falsedp[i][j] += lfc * rfc
						else:
							truedp[i][j] += ltc * rfc + lfc * rtc
							falsedp[i][j] += ltc * rtc + lfc * rfc
		return truedp[0][n - 1] % mod


class Solution:

	def countWays(self, N, S):
		dp = [[[-1, -1] for i in range(N)] for j in range(N)]

		def recursive(dp, S, i=0, j=N - 1):
			if i == j:
				if S[i] == 'T':
					dp[i][j] = [1, 0]
				else:
					dp[i][j] = [0, 1]
				return dp[i][j]
			if dp[i][j] != [-1, -1]:
				return dp[i][j]
			dp[i][j] = [0, 0]
			for prtIdx in range(i, j + 1):
				if S[prtIdx] != 'T' and S[prtIdx] != 'F':
					(left_True, left_False) = recursive(dp, S, i, prtIdx - 1)
					(right_True, right_False) = recursive(dp, S, prtIdx + 1, j)
					if S[prtIdx] == '&':
						dp[i][j][0] += left_True * right_True
						dp[i][j][1] += left_True * right_False + left_False * right_True + left_False * right_False
					elif S[prtIdx] == '|':
						dp[i][j][0] += left_True * right_True + left_True * right_False + left_False * right_True
						dp[i][j][1] += left_False * right_False
					else:
						dp[i][j][0] += left_True * right_False + left_False * right_True
						dp[i][j][1] += left_True * right_True + left_False * right_False
					dp[i][j][0] = dp[i][j][0] % 1003
					dp[i][j][1] = dp[i][j][1] % 1003
			return dp[i][j]
		return recursive(dp, S)[0] % 1003


class Solution:

	def countWays(self, N, S):
		s = S

		def fun(s, i, j, bool):
			if i > j:
				return 0
			elif i == j:
				if bool == True and s[i] == 'T':
					return 1
				elif bool == False and s[i] == 'F':
					return 1
				else:
					return 0
			res = 0
			if (i, j, bool) in dp:
				return dp[i, j, bool]
			for k in range(i + 1, j, 2):
				lt = fun(s, i, k - 1, True)
				lf = fun(s, i, k - 1, False)
				rt = fun(s, k + 1, j, True)
				rf = fun(s, k + 1, j, False)
				if s[k] == '^':
					if bool == True:
						res += lt * rf + lf * rt
					else:
						res += lt * rt + lf * rf
				elif s[k] == '|':
					if bool == True:
						res += lt * rt + lf * rt + lt * rf
					else:
						res += lf * rf
				elif bool == True:
					res += lt * rt
				else:
					res += lf * rf + lf * rt + lt * rf
			dp[i, j, bool] = res
			return res
		dp = {}
		return fun(s, 0, len(s) - 1, True) % 1003


class Solution:

	def helper(self, s, i, j, isTrue, dp):
		if i > j:
			return 0
		if i == j:
			if isTrue == 1:
				if s[i] == 'T':
					return 1
				else:
					return 0
			elif isTrue == 0:
				if s[i] == 'F':
					return 1
				else:
					return 0
		key = str(i) + '-' + str(j) + '-' + str(isTrue)
		if dp.get(key, -1) != -1:
			return dp[key]
		ans = 0
		for k in range(i + 1, j, 2):
			leftTrue = self.helper(s, i, k - 1, 1, dp)
			leftFalse = self.helper(s, i, k - 1, 0, dp)
			rightTrue = self.helper(s, k + 1, j, 1, dp)
			rightFalse = self.helper(s, k + 1, j, 0, dp)
			if s[k] == '&':
				if isTrue == 1:
					ans += leftTrue * rightTrue
				else:
					ans += leftTrue * rightFalse + leftFalse * rightTrue + leftFalse * rightFalse
			elif s[k] == '|':
				if isTrue == 1:
					ans += leftTrue * rightFalse + leftFalse * rightTrue + leftTrue * rightTrue
				else:
					ans += leftFalse * rightFalse
			elif isTrue == 1:
				ans += leftTrue * rightFalse + leftFalse * rightTrue
			else:
				ans += leftTrue * rightTrue + leftFalse * rightFalse
		dp[key] = ans % 1003
		return dp[key]

	def countWays(self, N, S):
		dp = {}
		return self.helper(S, 0, N - 1, 1, dp)


class Solution:

	def countWays(self, n, s):

		def boolean(i, j, isTrue, s, dp):
			if i > j:
				return 0
			if i == j:
				if isTrue == 1:
					return int(s[i] == 'T')
				else:
					return int(s[i] == 'F')
			if dp[i][j][isTrue] != -1:
				return dp[i][j][isTrue]
			ways = 0
			mod = 1003
			for ind in range(i + 1, j, 2):
				lT = boolean(i, ind - 1, 1, s, dp)
				lF = boolean(i, ind - 1, 0, s, dp)
				rT = boolean(ind + 1, j, 1, s, dp)
				rF = boolean(ind + 1, j, 0, s, dp)
				if s[ind] == '&':
					if isTrue:
						ways = (ways + rT * lT % mod) % mod
					else:
						ways = (ways + lF * rT % mod + lT * rF % mod + lF * rF % mod) % mod
				elif s[ind] == '|':
					if isTrue:
						ways = (ways + lT * rF % mod + lF * rT % mod + lT * rT % mod) % mod
					else:
						ways = (ways + lF * rF % mod) % mod
				elif isTrue:
					ways = (ways + lT * rF % mod + lF * rT % mod) % mod
				else:
					ways = (ways + lT * rT % mod + lF * rF % mod) % mod
			dp[i][j][isTrue] = ways % mod
			return ways % mod
		dp = []
		for i in range(n + 1):
			temp = []
			for j in range(n + 1):
				isTrueOrFalse = []
				for j in range(2):
					isTrueOrFalse.append(-1)
				temp.append(isTrueOrFalse)
			dp.append(temp)
		i = 0
		j = n - 1
		isTrue = 1
		res = boolean(i, j, isTrue, s, dp)
		return res


class Solution:

	def countWays(self, N, S):
		tc = {}
		fc = {}

		def dTCount(t):
			if t[1] - t[0] == 1:
				if S[t[0]] == 'T':
					tc[t] = 1
				else:
					tc[t] = 0
			elif t not in tc.keys():
				total = 0
				for i in range(t[0] + 1, t[1], 2):
					lslice = (t[0], i)
					rslice = (i + 1, t[1])
					if S[i] == '&':
						total += dTCount(lslice) * dTCount(rslice)
					elif S[i] == '|':
						total += dTCount(lslice) * dTCount(rslice) + dFCount(lslice) * dTCount(rslice) + dTCount(lslice) * dFCount(rslice)
					else:
						total += dFCount(lslice) * dTCount(rslice) + dTCount(lslice) * dFCount(rslice)
				tc[t] = total
			return tc[t]

		def dFCount(t):
			if t[1] - t[0] == 1:
				if S[t[0]] == 'F':
					fc[t] = 1
				else:
					fc[t] = 0
			elif t not in fc.keys():
				total = 0
				for i in range(t[0] + 1, t[1], 2):
					lslice = (t[0], i)
					rslice = (i + 1, t[1])
					if S[i] == '&':
						total += dFCount(lslice) * dFCount(rslice) + dFCount(lslice) * dTCount(rslice) + dTCount(lslice) * dFCount(rslice)
					elif S[i] == '|':
						total += dFCount(lslice) * dFCount(rslice)
					else:
						total += dFCount(lslice) * dFCount(rslice) + dTCount(lslice) * dTCount(rslice)
				fc[t] = total
			return fc[t]

		def TCount(S):
			total = 0
			if S == 'T':
				total = 1
			else:
				for i in range(1, len(S), 2):
					if S[i] == '&':
						total += TCount(S[0:i]) * TCount(S[i + 1:])
					elif S[i] == '|':
						total += TCount(S[0:i]) * TCount(S[i + 1:]) + FCount(S[0:i]) * TCount(S[i + 1:]) + TCount(S[0:i]) * FCount(S[i + 1:])
					else:
						total += FCount(S[0:i]) * TCount(S[i + 1:]) + TCount(S[0:i]) * FCount(S[i + 1:])
			return total

		def FCount(S):
			total = 0
			if S == 'F':
				total = 1
			else:
				for i in range(1, len(S), 2):
					if S[i] == '&':
						total += FCount(S[0:i]) * FCount(S[i + 1:]) + FCount(S[0:i]) * TCount(S[i + 1:]) + TCount(S[0:i]) * FCount(S[i + 1:])
					elif S[i] == '|':
						total += FCount(S[0:i]) * FCount(S[i + 1:])
					else:
						total += TCount(S[0:i]) * TCount(S[i + 1:]) + FCount(S[0:i]) * FCount(S[i + 1:])
			return total
		return dTCount((0, N)) % 1003


class Solution:

	def countWays(self, N, S):
		memo = {}

		def helper(s, i, j, exp):
			if i > j:
				return False
			if i == j:
				if exp == True:
					return 1 if s[i] == 'T' else 0
				else:
					return 1 if s[i] == 'F' else 0
			if (i, j, exp) in memo:
				return memo[i, j, exp]
			count = 0
			for k in range(i + 1, j):
				lt = helper(s, i, k - 1, True)
				lf = helper(s, i, k - 1, False)
				rt = helper(s, k + 1, j, True)
				rf = helper(s, k + 1, j, False)
				if s[k] == '|':
					if exp == True:
						count += (lt * rf + rt * lf + rt * lt) % 1003
					else:
						count += rf * lf % 1003
				elif s[k] == '&':
					if exp == True:
						count += lt * rt % 1003
					else:
						count += (lt * rf + rt * lf + rf * lf) % 1003
				elif exp == True:
					count += (lt * rf + rt * lf) % 1003
				else:
					count += (lt * rt + lf * rf) % 1003
			memo[i, j, exp] = count % 1003
			return count % 1003
		return helper(S, 0, N - 1, True)


class Solution:

	def countWays(self, N, s):
		if s[0] == 'T' and N == 1:
			return 1

		def recursion(i, j, isTrue):
			if i > j:
				return 0
			if dp[i][j][isTrue] != -1:
				return dp[i][j][isTrue]
			if i == j:
				if isTrue:
					if s[i] == 'T':
						return True
					else:
						return False
				elif s[i] == 'F':
					return True
				else:
					return False
			ways = 0
			for k in range(i + 1, j, 2):
				LT = recursion(i, k - 1, 1)
				LF = recursion(i, k - 1, 0)
				RT = recursion(k + 1, j, 1)
				RF = recursion(k + 1, j, 0)
				if isTrue:
					if s[k] == '&':
						ways += LT * RT
					elif s[k] == '^':
						ways += LF * RT + LT * RF
					elif s[k] == '|':
						ways += LT * RT + LF * RT + LT * RF
				elif s[k] == '&':
					ways += LT * RF + LF * RT + LF * RF
				elif s[k] == '^':
					ways += LT * RT + LF * RF
				elif s[k] == '|':
					ways += LF * RF
			dp[i][j][isTrue] = ways % 1003
			return dp[i][j][isTrue]
		dp = [[[-1] * 2 for i in range(N + 1)] for i in range(N + 1)]
		return recursion(0, N - 1, 1)


class Solution:

	def countWays(self, N, s):
		Power = pow(10, 9) + 7

		def recursion(i, j, isTrue):
			if i > j:
				return 0
			if dp[i][j][isTrue] != -1:
				return dp[i][j][isTrue]
			if i == j:
				if isTrue:
					if s[i] == 'T':
						return 1
					else:
						return 0
				elif s[i] == 'F':
					return 1
				else:
					return 0
			ways = 0
			for k in range(i + 1, j, 2):
				LT = recursion(i, k - 1, 1)
				LF = recursion(i, k - 1, 0)
				RT = recursion(k + 1, j, 1)
				RF = recursion(k + 1, j, 0)
				if isTrue:
					if s[k] == '&':
						ways += LT * RT
					elif s[k] == '^':
						ways += LT * RF + LF * RT
					elif s[k] == '|':
						ways += LT * RF + LF * RT + LT * RT
				elif s[k] == '&':
					ways += LF * RF + LT * RF + LF * RT
				elif s[k] == '^':
					ways += LF * RF + RT * LT
				elif s[k] == '|':
					ways += LF * RF
			dp[i][j][isTrue] = ways % 1003
			return dp[i][j][isTrue]
		dp = [[[-1] * 2 for i in range(N + 1)] for i in range(N + 1)]
		return recursion(0, N - 1, 1)


mod = 1003

class Solution:

	def countWays(self, n, S):
		dp = [[[0 for _ in range(2)] for _ in range(n)] for _ in range(n)]
		for i in range(n - 1, -1, -1):
			for j in range(i, n):
				if i == j:
					if S[i] == 'F':
						dp[i][j][0] = 1
						dp[i][j][1] = 0
					elif S[i] == 'T':
						dp[i][j][0] = 0
						dp[i][j][1] = 1
				else:
					for ind in range(i + 1, j, 2):
						lt = dp[i][ind - 1][1] % mod
						lf = dp[i][ind - 1][0] % mod
						rt = dp[ind + 1][j][1] % mod
						rf = dp[ind + 1][j][0] % mod
						if S[ind] == '&':
							dp[i][j][1] = (dp[i][j][1] + lt * rt) % mod
							dp[i][j][0] = (dp[i][j][0] + (lf * rt + rf * lt + lf * rf)) % mod
						elif S[ind] == '|':
							dp[i][j][0] = (dp[i][j][0] + lf * rf) % mod
							dp[i][j][1] = (dp[i][j][1] + (lt * rt + lt * rf + lf * rt)) % mod
						else:
							dp[i][j][0] = (dp[i][j][0] + (lt * rt + lf * rf)) % mod
							dp[i][j][1] = (dp[i][j][1] + (lf * rt + rf * lt)) % mod
		return dp[0][n - 1][1]


class Solution:

	def countWays(self, N, S):

		def helper(s, i, j, exp, dp):
			m = 1003
			if i > j:
				return 0
			if i == j:
				if exp == 1:
					if s[i] == 'T':
						return 1
					return 0
				else:
					if s[i] == 'F':
						return 1
					return 0
			if dp[i][j][exp] != -1:
				return dp[i][j][exp]
			ans = 0
			for k in range(i + 1, j, 2):
				if dp[i][k - 1][1] == -1:
					lt = helper(s, i, k - 1, 1, dp)
					dp[i][k - 1][1] = lt
				else:
					lt = dp[i][k - 1][1]
				if dp[i][k - 1][0] == -1:
					lf = helper(s, i, k - 1, 0, dp)
					dp[i][k - 1][0] = lf
				else:
					lf = dp[i][k - 1][0]
				if dp[k + 1][j][1] == -1:
					rt = helper(s, k + 1, j, 1, dp)
					dp[k + 1][j][1] = rt
				else:
					rt = dp[k + 1][j][1]
				if dp[k + 1][j][0] == -1:
					rf = helper(s, k + 1, j, 0, dp)
					dp[k + 1][j][0] = rf
				else:
					rf = dp[k + 1][j][0]
				if s[k] == '|':
					if exp == 1:
						ans += lt * rt + lf * rt + lt * rf
					else:
						ans += lf * rf
				elif s[k] == '&':
					if exp == 1:
						ans += lt * rt
					else:
						ans += lf * rf + lf * rt + lt * rf
				elif s[k] == '^':
					if exp == 1:
						ans += lt * rf + rt * lf
					else:
						ans += lt * rt + rf * lf
			dp[i][j][exp] = ans % 1003
			return dp[i][j][exp]
		dp = [[[-1 for i in range(2)] for j in range(N)] for k in range(N)]
		ans = helper(S, 0, N - 1, 1, dp)
		return ans


class Solution:

	def countWays(self, N, S):

		def solve(s, i, j, b):
			if i > j:
				return 0
			elif i == j:
				if b == 1:
					if s[i] == 'T':
						return 1
					else:
						return 0
				elif s[i] == 'F':
					return 1
				else:
					return 0
			if t[i][j][b] != -1:
				return t[i][j][b]
			temp = 0
			for k in range(i + 1, j, 2):
				if t[i][k - 1][1] != -1:
					lt = t[i][k - 1][1]
				else:
					lt = solve(s, i, k - 1, 1)
				if t[i][k - 1][0] != -1:
					lf = t[i][k - 1][0]
				else:
					lf = solve(s, i, k - 1, 0)
				if t[k + 1][j][1] != -1:
					rt = t[k + 1][j][1]
				else:
					rt = solve(s, k + 1, j, 1)
				if t[k + 1][j][0] != -1:
					rf = t[k + 1][j][0]
				else:
					rf = solve(s, k + 1, j, 0)
				if s[k] == '&':
					if b == 1:
						temp += lt * rt
					else:
						temp += lt * rf + lf * rt + lf * rf
				elif s[k] == '|':
					if b == 1:
						temp += lt * rf + lf * rt + lt * rt
					else:
						temp += lf * rf
				elif s[k] == '^':
					if b == 1:
						temp += lt * rf + rt * lf
					else:
						temp += lt * rt + lf * rf
				t[i][j][b] = temp
			return temp
		t = [[[-1 for x in range(2)] for x in range(N + 1)] for x in range(N + 1)]
		return solve(S, 0, N - 1, 1) % 1003


class Solution:

	def solve(self, s, i, j, flag, dp):
		if i > j:
			return 0
		if i == j:
			if flag:
				return int(s[i] == 'T')
			else:
				return int(s[i] == 'F')
		if dp[i][j][flag] != -1:
			return dp[i][j][flag]
		ans = 0
		for ind in range(i + 1, j, 2):
			lt = self.solve(s, i, ind - 1, 1, dp)
			lf = self.solve(s, i, ind - 1, 0, dp)
			rt = self.solve(s, ind + 1, j, 1, dp)
			rf = self.solve(s, ind + 1, j, 0, dp)
			if s[ind] == '&':
				if flag:
					ans += lt * rt
				else:
					ans += lf * rf + rt * lf + lt * rf
			elif s[ind] == '|':
				if flag:
					ans += lt * rt + lt * rf + rt * lf
				else:
					ans += lf * rf
			elif flag:
				ans += lf * rt + rf * lt
			else:
				ans += lf * rf + lt * rt
		dp[i][j][flag] = ans
		return dp[i][j][flag]

	def tabular(self, s):
		n = len(s)
		dp = [[[0 for i in range(2)] for j in range(n + 1)] for k in range(n + 1)]
		for i in range(n):
			for j in range(n):
				for flag in range(2):
					if i == j:
						if flag:
							dp[i][j][flag] = int(s[i] == 'T')
						else:
							dp[i][j][flag] = int(s[i] == 'F')
		for i in range(n - 1, -1, -1):
			for j in range(n):
				if i >= j:
					continue
				else:
					for flag in range(2):
						ans = 0
						for ind in range(i + 1, j, 2):
							lt = dp[i][ind - 1][1]
							lf = dp[i][ind - 1][0]
							rt = dp[ind + 1][j][1]
							rf = dp[ind + 1][j][0]
							if s[ind] == '&':
								if flag:
									ans += lt * rt
								else:
									ans += lf * rf + rt * lf + lt * rf
							elif s[ind] == '|':
								if flag:
									ans += lt * rt + lt * rf + rt * lf
								else:
									ans += lf * rf
							elif flag:
								ans += lf * rt + rf * lt
							else:
								ans += lf * rf + lt * rt
						dp[i][j][flag] = ans
		return dp[0][n - 1][1]

	def countWays(self, N, S):
		return self.tabular(S) % 1003
		dp = [[[-1 for i in range(2)] for j in range(N + 1)] for k in range(N + 1)]
		return self.solve(S, 0, N - 1, 1, dp) % 1003


def solve(s, i, j, isTrue, dp):
	if i > j:
		return 0
	if i == j:
		if isTrue == True:
			return 1 if s[i] == 'T' else 0
		else:
			return 1 if s[i] == 'F' else 0
	if dp[i][j][isTrue] != -1:
		return dp[i][j][isTrue]
	ans = 0
	for k in range(i + 1, j, 2):
		if dp[i][k - 1][True] != -1:
			LT = dp[i][k - 1][True]
		else:
			LT = solve(s, i, k - 1, True, dp)
		if dp[i][k - 1][False] != -1:
			LF = dp[i][k - 1][False]
		else:
			LF = solve(s, i, k - 1, False, dp)
		if dp[k + 1][j][True] != -1:
			RT = dp[k + 1][j][True]
		else:
			RT = solve(s, k + 1, j, True, dp)
		if dp[k + 1][j][False] != -1:
			RF = dp[k + 1][j][False]
		else:
			RF = solve(s, k + 1, j, False, dp)
		if s[k] == '&':
			if isTrue == True:
				ans = ans + LT * RT
			else:
				ans += LF * RT + LF * RF + LT * RF
		elif s[k] == '|':
			if isTrue == True:
				ans += LT * RT + LT * RF + LF * RT
			else:
				ans += LF * RF
		elif s[k] == '^':
			if isTrue == True:
				ans += LF * RT + LT * RF
			else:
				ans += LT * RT + LF * RF
	dp[i][j][isTrue] = ans % 1003
	return ans % 1003

class Solution:

	def countWays(self, N, S):
		dp = [[[-1 for k in range(2)] for i in range(N + 1)] for j in range(N + 1)]
		return solve(S, 0, N - 1, True, dp)


def parenthesis_count(Str, i, j, isTrue, dp):
	if i > j:
		return 0
	if i == j:
		if isTrue == 1:
			return 1 if Str[i] == 'T' else 0
		else:
			return 1 if Str[i] == 'F' else 0
	if dp[i][j][isTrue] != -1:
		return dp[i][j][isTrue]
	temp_ans = 0
	for k in range(i + 1, j, 2):
		if dp[i][k - 1][1] != -1:
			leftTrue = dp[i][k - 1][1]
		else:
			leftTrue = parenthesis_count(Str, i, k - 1, 1, dp)
		if dp[i][k - 1][0] != -1:
			leftFalse = dp[i][k - 1][0]
		else:
			leftFalse = parenthesis_count(Str, i, k - 1, 0, dp)
		if dp[k + 1][j][1] != -1:
			rightTrue = dp[k + 1][j][1]
		else:
			rightTrue = parenthesis_count(Str, k + 1, j, 1, dp)
		if dp[k + 1][j][0] != -1:
			rightFalse = dp[k + 1][j][0]
		else:
			rightFalse = parenthesis_count(Str, k + 1, j, 0, dp)
		if Str[k] == '&':
			if isTrue == 1:
				temp_ans = temp_ans + leftTrue * rightTrue
			else:
				temp_ans = temp_ans + leftTrue * rightFalse + leftFalse * rightTrue + leftFalse * rightFalse
		elif Str[k] == '|':
			if isTrue == 1:
				temp_ans = temp_ans + leftTrue * rightTrue + leftTrue * rightFalse + leftFalse * rightTrue
			else:
				temp_ans = temp_ans + leftFalse * rightFalse
		elif Str[k] == '^':
			if isTrue == 1:
				temp_ans = temp_ans + leftTrue * rightFalse + leftFalse * rightTrue
			else:
				temp_ans = temp_ans + leftTrue * rightTrue + leftFalse * rightFalse
		dp[i][j][isTrue] = temp_ans
	return temp_ans % 1003

class Solution:

	def countWays(self, N, S):
		dp = [[[-1 for k in range(2)] for i in range(N + 1)] for j in range(N + 1)]
		return parenthesis_count(S, 0, N - 1, 1, dp)


class Solution:

	def ways(self, s, i, n, memo, mod):
		key = (i, n)
		if key in memo:
			return memo[key]
		if i == n:
			if s[i] == 'T':
				memo[key] = (1, 0)
				return (1, 0)
			else:
				memo[key] = (0, 1)
				return (0, 1)
		true = 0
		false = 0
		k = i + 1
		while k < n:
			(Tp1, Fp1) = self.ways(s, i, k - 1, memo, mod)
			(Tp2, Fp2) = self.ways(s, k + 1, n, memo, mod)
			if s[k] == '|':
				true = (true + Tp1 % mod * Tp2 % mod % mod + Tp1 % mod * Fp2 % mod % mod + Fp1 % mod * Tp2 % mod % mod) % mod
				false = (false + Fp1 % mod * Fp2 % mod % mod) % mod
			elif s[k] == '&':
				true = (true + Tp1 % mod * Tp2 % mod % mod) % mod
				false = false + Fp1 * Fp2 + Tp1 * Fp2 + Fp1 * Tp2
			elif s[k] == '^':
				true = (true + Tp1 % mod * Fp2 % mod % mod + Fp1 % mod * Tp2 % mod % mod) % mod
				false = (false + Tp1 % mod * Tp2 % mod % mod + Fp1 % mod * Fp2 % mod % mod) % mod
			k += 2
		memo[key] = (true, false)
		return (true, false)

	def countWays(self, N, S):
		memo = {}
		mod = 1003
		return self.ways(S, 0, N - 1, memo, mod)[0]


class Solution:

	def countWays(self, N, S):
		mod = 1003
		(boolean, operaters) = ('', '')
		for i in S:
			if i == 'T' or i == 'F':
				boolean += i
			else:
				operaters += i
		n = len(boolean)
		dpt = [[0 for i in range(n)] for j in range(n)]
		dpf = [[0 for j in range(n)] for i in range(n)]
		for g in range(n):
			i = 0
			j = g
			while j < n and i < n:
				if g == 0:
					if boolean[i] == 'T':
						dpt[i][j] = 1
						dpf[i][j] = 0
					elif boolean[i] == 'F':
						dpt[i][j] = 0
						dpf[i][j] = 1
				else:
					for k in range(i, j):
						lTc = dpt[i][k]
						rTc = dpt[k + 1][j]
						lFc = dpf[i][k]
						rFc = dpf[k + 1][j]
						if operaters[k] == '&':
							dpt[i][j] += lTc * rTc
							dpf[i][j] += lTc * rFc + lFc * rTc + lFc * rFc
						elif operaters[k] == '|':
							dpt[i][j] += lTc * rTc + lTc * rFc + rTc * lFc
							dpf[i][j] += lFc * rFc
						elif operaters[k] == '^':
							dpt[i][j] += lTc * rFc + lFc * rTc
							dpf[i][j] += lTc * rTc + lFc * rFc
				i += 1
				j += 1
		return dpt[0][-1] % mod


class Solution:

	def countWays(self, N, S):
		d = {}

		def solve(s, i, j, istrue):
			if i > j:
				return 0
			if i == j:
				if s[i] == istrue:
					return 1
				else:
					return 0
			ans = 0
			key = ''
			key += str(i) + ' ' + str(j) + ' ' + istrue
			if key in d:
				return d[key]
			for k in range(i + 1, j, 2):
				lt = solve(s, i, k - 1, 'T')
				lf = solve(s, i, k - 1, 'F')
				rt = solve(s, k + 1, j, 'T')
				rf = solve(s, k + 1, j, 'F')
				if s[k] == '&':
					if istrue == 'T':
						ans += lt * rt
					else:
						ans += lt * rf + rt * lf + rf * lf
				elif s[k] == '|':
					if istrue == 'T':
						ans += lt * rf + rt * lf + lt * rt
					else:
						ans += lf * rf
				elif s[k] == '^':
					if istrue == 'T':
						ans += lt * rf + lf * rt
					else:
						ans += lt * rt + lf * rf
			d[key] = ans
			return ans
		i = 0
		j = N - 1
		return solve(S, i, j, 'T') % 1003


from functools import lru_cache

class Solution:

	def countWays(self, N, S):

		@lru_cache(None)
		def dp(i, j, isTrue):
			if i > j:
				return 0
			if i == j:
				if isTrue == 1:
					return 1 if S[i] == 'T' else 0
				else:
					return 1 if S[i] == 'F' else 0
			total_operation = 0
			for k in range(i + 1, j, 2):
				leftTrue = dp(i, k - 1, 1)
				leftFalse = dp(i, k - 1, 0)
				rightTrue = dp(k + 1, j, 1)
				rightFalse = dp(k + 1, j, 0)
				if S[k] == '&':
					if isTrue:
						total_operation += leftTrue * rightTrue
					else:
						total_operation += leftTrue * rightFalse + leftFalse * rightTrue + leftFalse * rightFalse
				elif S[k] == '|':
					if isTrue:
						total_operation += leftTrue * rightFalse + leftFalse * rightTrue + leftTrue * rightTrue
					else:
						total_operation += leftFalse * rightFalse
				elif S[k] == '^':
					if isTrue:
						total_operation += leftTrue * rightFalse + leftFalse * rightTrue
					else:
						total_operation += leftTrue * rightTrue + leftFalse * rightFalse
			return total_operation
		return dp(0, len(S) - 1, 1) % 1003


class Solution:

	def answer(self, i, j, istrue, s, dp):
		if i == j:
			if istrue == 1:
				if s[i] == 'T':
					return 1
				else:
					return 0
			elif s[i] == 'F':
				return 1
			else:
				return 0
		if dp[i][j][istrue] != -1:
			return dp[i][j][istrue]
		ways = 0
		for k in range(i + 1, j, 2):
			lt = self.answer(i, k - 1, 1, s, dp)
			lf = self.answer(i, k - 1, 0, s, dp)
			rt = self.answer(k + 1, j, 1, s, dp)
			rf = self.answer(k + 1, j, 0, s, dp)
			if s[k] == '&':
				if istrue == 1:
					ways += lt * rt
				else:
					ways += lt * rf + lf * rt + lf * rf
			elif s[k] == '|':
				if istrue == 1:
					ways += lt * rf + lf * rt + lt * rt
				else:
					ways += lf * rf
			elif s[k] == '^':
				if istrue == 1:
					ways += lt * rf + lf * rt
				else:
					ways += lt * rt + lf * rf
		dp[i][j][istrue] = ways
		return ways % 1003

	def countWays(self, N, s):
		dp = [[[0 for x in range(2)] for x in range(N)] for x in range(N)]
		for i in range(N):
			for istrue in range(2):
				if istrue == 1:
					if s[i] == 'T':
						dp[i][i][istrue] = 1
				elif s[i] == 'F':
					dp[i][i][istrue] = 1
		for i in range(N - 1, -1, -1):
			for j in range(i + 1, N):
				for istrue in range(2):
					ways = 0
					for k in range(i + 1, j, 2):
						lt = dp[i][k - 1][1]
						lf = dp[i][k - 1][0]
						rt = dp[k + 1][j][1]
						rf = dp[k + 1][j][0]
						if s[k] == '&':
							if istrue == 1:
								ways += lt * rt
							else:
								ways += lt * rf + lf * rt + lf * rf
						elif s[k] == '|':
							if istrue == 1:
								ways += lt * rf + lf * rt + lt * rt
							else:
								ways += lf * rf
						elif s[k] == '^':
							if istrue == 1:
								ways += lt * rf + lf * rt
							else:
								ways += lt * rt + lf * rf
					dp[i][j][istrue] = ways
		return dp[0][N - 1][1] % 1003


m = 1003

class Solution:

	def solve(self, S, i, j, istrue, dp):
		if i > j:
			return False
		if i == j:
			if istrue == 1:
				return 1 if S[i] == 'T' else 0
			else:
				return 1 if S[i] == 'F' else 0
		if dp[i][j][istrue] != -1:
			return dp[i][j][istrue]
		ans = 0
		for k in range(i + 1, j, 2):
			lt = self.solve(S, i, k - 1, 1, dp)
			lf = self.solve(S, i, k - 1, 0, dp)
			rt = self.solve(S, k + 1, j, 1, dp)
			rf = self.solve(S, k + 1, j, 0, dp)
			if S[k] == '&':
				if istrue:
					ans = ans + lt * rt
				else:
					ans = ans + lt * rf + lf * rt + lf * rf
			elif S[k] == '|':
				if istrue:
					ans = ans + lt * rf + rt * lf + lt * rt
				else:
					ans = ans + lf * rf
			elif S[k] == '^':
				if istrue:
					ans = ans + lf * rt + lt * rf
				else:
					ans = ans + lf * rf + rt * lt
		dp[i][j][istrue] = ans
		return dp[i][j][istrue]

	def countWays(self, N, S):
		i = 0
		j = N - 1
		istrue = 1
		dp = [[[-1 for i in range(2)] for k in range(N)] for l in range(N)]
		ans = self.solve(S, i, j, istrue, dp)
		return ans % m