1. Идея

Нужно посчитать, сколькими способами можно полностью расставить скобки в булевом выражении так, чтобы результат был T.

Порядок символов менять нельзя, можно только выбирать, какая операция выполняется последней на каждом подвыражении. Это типичная задача на динамическое программирование по подотрезкам.

Для каждого отрезка операндов будем хранить:

• dpT[l][r] — число способов вычислить подвыражение от операнда l до операнда r в T;
• dpF[l][r] — число способов вычислить то же подвыражение в F.

Тогда ответом будет dpT[0][m - 1], где m — число операндов.

2. Наблюдения

1. Удобно отделить операнды и операторы

Строка имеет вид:

• на чётных позициях стоят T или F,
• на нечётных — &, |, ^.

Поэтому можно разбить строку на два массива:

• vals — операнды,
• ops — операторы.

Например, для строки T^F&T:

• vals = [T, F, T]
• ops = [^, &]

2. База динамики очень простая

Если подвыражение состоит из одного операнда vals[i], то:

• dpT[i][i] = 1, если это T,
• dpF[i][i] = 1, если это F.

Других способов нет.

3. Последняя операция разбивает отрезок на две части

Если рассматривается отрезок операндов от l до r, то последняя операция может быть любой между ними. Пусть она стоит после операнда k, тогда выражение разбивается так:

• левая часть: от l до k
• правая часть: от k + 1 до r

Их значения уже должны быть посчитаны ранее.

4. Для каждого оператора есть свои сочетания истинности

Пусть:

• слева LT способов получить T, LF способов получить F,
• справа RT способов получить T, RF способов получить F.

Тогда:

Для &

Истина получается только из T & T:

• в T: LT * RT
• в F: LT * RF + LF * RT + LF * RF

Для |

Ложь получается только из F | F:

• в T: LT * RT + LT * RF + LF * RT
• в F: LF * RF

Для ^

Истина получается, когда значения разные:

• в T: LT * RF + LF * RT
• в F: LT * RT + LF * RF

3. Алгоритм

1. Считываем строку.
2. Разделяем её на массив операндов vals и массив операторов ops.
3. Создаём две таблицы dpT и dpF размера m x m, заполненные нулями.
4. Заполняем базу для отрезков длины 1.
5. Перебираем длину отрезка len от 2 до m.
6. Для каждого отрезка [l, r]:
   • пробуем все позиции k, где может стоять последняя операция;
   • берём значения из левой и правой частей;
   • в зависимости от оператора ops[k] добавляем число способов в waysT и waysF.
7. Записываем:
   • dpT[l][r] = waysT
   • dpF[l][r] = waysF
8. Выводим dpT[0][m - 1].

Все вычисления делаем по модулю 10^9 + 7.

4. Почему это работает

Докажем корректность идеи.

Рассмотрим произвольное подвыражение, состоящее из операндов с индексами от l до r.

Любая полная расстановка скобок в этом подвыражении определяет, какая операция будет выполнена последней. Эта последняя операция обязательно находится между некоторыми соседними частями: после операнда k, где l <= k < r.

Значит, любая расстановка скобок однозначно разбивается на:

• способ расставить скобки в левой части [l, k],
• способ расставить скобки в правой части [k + 1, r],
• последнюю операцию ops[k].

Если известно, сколько способов левая и правая части могут давать T и F, то можно точно посчитать, сколько комбинаций даст T и сколько даст F после применения оператора.

Мы перебираем все возможные k, то есть все возможные последние операции. При этом:

• ни один способ не пропускается,
• ни один способ не учитывается дважды, потому что у каждой полной скобочной структуры последняя операция ровно одна.

База тоже верна: выражение из одного операнда имеет ровно один результат — либо T, либо F.

Так как более длинные отрезки считаются через более короткие, динамика корректно заполняется, и в конце dpT[0][m - 1] действительно равно числу способов получить истину для всего выражения.

5. Сложность

Пусть m — число операндов.

• Есть O(m^2) отрезков.
• Для каждого отрезка перебираем точку разбиения k, то есть до O(m) вариантов.

Итоговая сложность:

• по времени: O(m^3)
• по памяти: O(m^2)

При m <= 200 это полностью укладывается в ограничения.

6. Код на C++17

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() {
    const long long MOD = 1000000007LL;

    string s;
    cin >> s;

    vector<char> val;
    vector<char> op;

    for (int i = 0; i < (int)s.size(); i++) {
        if (i % 2 == 0) {
            val.push_back(s[i]);
        } else {
            op.push_back(s[i]);
        }
    }

    int m = (int)val.size();

    vector<vector<long long>> dpT(m, vector<long long>(m, 0));
    vector<vector<long long>> dpF(m, vector<long long>(m, 0));

    for (int i = 0; i < m; i++) {
        if (val[i] == 'T') {
            dpT[i][i] = 1;
        } else {
            dpF[i][i] = 1;
        }
    }

    for (int len = 2; len <= m; len++) {
        for (int l = 0; l + len - 1 < m; l++) {
            int r = l + len - 1;

            long long waysT = 0;
            long long waysF = 0;

            for (int k = l; k < r; k++) {
                long long LT = dpT[l][k];
                long long LF = dpF[l][k];
                long long RT = dpT[k + 1][r];
                long long RF = dpF[k + 1][r];
                char c = op[k];

                if (c == '&') {
                    waysT = (waysT + LT * RT) % MOD;
                    waysF = (waysF + LT * RF + LF * RT + LF * RF) % MOD;
                } else if (c == '|') {
                    waysT = (waysT + LT * RT + LT * RF + LF * RT) % MOD;
                    waysF = (waysF + LF * RF) % MOD;
                } else if (c == '^') {
                    waysT = (waysT + LT * RF + LF * RT) % MOD;
                    waysF = (waysF + LT * RT + LF * RF) % MOD;
                }
            }

            dpT[l][r] = waysT % MOD;
            dpF[l][r] = waysF % MOD;
        }
    }

    cout << dpT[0][m - 1] % MOD << '\n';
    return 0;
}

7. Код на Python 3

MOD = 10**9 + 7

s = input().strip()

vals = []
ops = []

for i, ch in enumerate(s):
    if i % 2 == 0:
        vals.append(ch)
    else:
        ops.append(ch)

m = len(vals)

dpT = [[0] * m for _ in range(m)]
dpF = [[0] * m for _ in range(m)]

for i in range(m):
    if vals[i] == 'T':
        dpT[i][i] = 1
    else:
        dpF[i][i] = 1

for length in range(2, m + 1):
    for l in range(0, m - length + 1):
        r = l + length - 1
        waysT = 0
        waysF = 0

        for k in range(l, r):
            LT = dpT[l][k]
            LF = dpF[l][k]
            RT = dpT[k + 1][r]
            RF = dpF[k + 1][r]
            op = ops[k]

            if op == '&':
                waysT = (waysT + LT * RT) % MOD
                waysF = (waysF + LT * RF + LF * RT + LF * RF) % MOD
            elif op == '|':
                waysT = (waysT + LT * RT + LT * RF + LF * RT) % MOD
                waysF = (waysF + LF * RF) % MOD
            else:
                waysT = (waysT + LT * RF + LF * RT) % MOD
                waysF = (waysF + LT * RT + LF * RF) % MOD

        dpT[l][r] = waysT
        dpF[l][r] = waysF

print(dpT[0][m - 1] % MOD)