Count the number of ways we can parenthesize the expression so that the value of expression evaluates to true.

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

No of ways Mod 1003.




#include <bits/stdc++.h>
#define endll "\n";
using namespace std;
typedef pair<int,int> pp;
#define fi first
#define se second
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    int t;cin>>t;
    while(t--){
        int n;
        cin>>n;
        string s,s1,s2;
        cin>>s;
//split string into two string in which one is operator and other chars of TorF;
        for(int i=0;i<s.length();i++){
            if(i&1)
             s2+=s[i];
            else
             s1+=s[i];
        }
// find length of symbol string.
        n=s1.length();
// create the 2d with type pair<int,int> of size of symbol
        pp dp[n][n];
//filling on basis of symbol
//if symbol is T then place (1,0)
//if symbol is F then place (0,1)
        for(int i=0;i<n;i++){
            if(s1[i]=='T')
            dp[i][i]={1,0};
            else
            dp[i][i]={0,1};
        }
        int a,b,c,d,e,f;
//iterating the from l=2 to l=n
//
        for(int l=2;l<=n;l++){
            for(int i=0;i+l-1<n;i++){
                int j=i+l-1;e=f=0;
                for(int k=i;k<j;k++){
                    a=dp[i][k].fi;//place value for T
                    b=dp[i][k].se;//place value for F
                    c=dp[k+1][j].fi;//place value for T
                    d=dp[k+1][j].se;//place value for F
                    if(s2[k]=='|'){
                        e+=a*c+a*d+c*b;//three combination for True(0&1,1&0,0&0)
                        f+=b*d;//one for false(0|0)
                    }
                    else if(s2[k]=='&'){
                        e+=a*c; //one  for true(1&1)
                        f+=a*d+b*c+b*d;//three combination for false(0&1,1&0,0&0)
                    }
                    else{
                        e+=a*d+b*c;//two combination for T(0&1,1&0)
                        f+=a*c+b*d;//two combination for F(0&0,1&1)
                    }
                }
                dp[i][j].fi=(e%1003);//taking mode and put value at dp[i][j].first for True
                dp[i][j].se=(f%1003);//taking mode and put value at dp[i][j].second for False
            }
        }
        cout<<dp[0][n-1].fi<<endll;//result finding only for true that is dp[0][n-1].first
    }
    return 0;
}