Дана строка, задающая булево выражение без скобок. В выражении используются только:

• операнды T — истина и F — ложь;
• бинарные операторы & — И, | — ИЛИ и ^ — исключающее ИЛИ.

Операнды и операторы в строке чередуются.

Разрешается полностью расставить скобки всеми возможными способами, не меняя порядок символов в выражении. Разные способы расстановки скобок могут приводить к разному порядку вычисления и, следовательно, к разному итоговому значению.

Требуется найти количество способов расставить скобки так, чтобы всё выражение вычислялось в истину, то есть в T.

Так как ответ может быть очень большим, выведите его по модулю 10^9 + 7.

Входные данные

В единственной строке задано выражение нечётной длины, состоящее из символов T, F, &, |, ^.

Гарантируется, что:

• операнды и операторы чередуются;
• первый и последний символы — операнды.

Выходные данные

Выведите одно целое число — количество способов полностью расставить скобки так, чтобы значение выражения было равно T, по модулю 10^9 + 7.

Ограничения

• число операндов m удовлетворяет 1 <= m <= 200;
• модуль равен 10^9 + 7.

Примеры

Пример 1

Входные данные

T

Выходные данные

1

Пример 2

Входные данные

T^F

Выходные данные

1