Given a boolean expression 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.

For Example:

The expression is “T | T & F ^ T”, it evaluates true

in 4 ways ((T|T)&(F^T)), (T|(T&(F^T))), (((T|T)&F)^T)

and (T|((T&F)^T)).

Return No_of_ways Mod 1003.

Input:

First line contains the test cases T. 1<=T<=500

Each test case have two lines

First is length of string N. 1<=N<=100

Second line is string S (boolean expression).

Output:

No of ways Mod 1003.

Example:

Input:

2

7

T|T&F^T

5

T^F|F

Output:

4

2