import java.util.*;
 
class Ideone {
 
	public static void main(String[] args){
		char[] symbols = {'T', 'T', 'F', 'T'};
		char[] operators =  {'|', '&', '^'};
 
		int n = symbols.length;
		int[][] F = new int[n][n];
		int[][] T = new int[n][n];
 
		for(int i=0; i<n; i++){
			F[i][i] = symbols[i] == 'F' ? 1 : 0;
			T[i][i] = symbols[i] == 'T' ? 1 : 0;
		}
 
		for(int gap=1; gap<n; gap++){
			for(int i=0, j=gap; j<n; j++, i++){
				T[i][j] = 0;
				F[i][j] = 0;
 
				for(int g=0; g<gap;g++){
					// Find place of parenthesization using current value of gap
	                int k = i + g;					
 
					// Store Total[i][k] and Total[k+1][j]
					int tik = T[i][k] + F[i][k];
					int tkj = T[k+1][j] + F[k+1][j];
 
					// Follow the recursive formulas according to the current operator
					if (operators[k] == '&'){
						T[i][j] += T[i][k]*T[k+1][j];
						F[i][j] += (tik*tkj - T[i][k]*T[k+1][j]);
					}
 
					if (operators[k] == '|'){
						F[i][j] += F[i][k]*F[k+1][j];
						T[i][j] += (tik*tkj - F[i][k]*F[k+1][j]);
					}
 
					if (operators[k] == '^'){
						T[i][j] += F[i][k]*T[k+1][j] + T[i][k]*F[k+1][j];
						F[i][j] += T[i][k]*T[k+1][j] + F[i][k]*F[k+1][j];
					}
				}
			}
		}
		System.out.println("Number of paranthesis => "+ T[0][n-1]);
	}
}