XOR (^): Result is true if one side is true and the other is false.

Repeat this recursively for all sub-expressions and return the total count of valid parenthesizations that lead to True.

Use memoization (3D DP table) to optimize overlapping subproblems.

Since the result can be large, return it modulo 10⁹ + 7.

Code

#include <bits/stdc++.h>
using namespace std;

#define ll long long
const int mod = 1000000007;

// Function to evaluate the number of ways to parenthesize the expression to get True or False
int f(int i, int j, int isTrue, string &exp) {
    // Base case 1: If i > j, it's an invalid expression, return 0.
    if (i > j) return 0;
    
    // Base case 2: If i and j are the same, evaluate the single character.
    if (i == j