22082번 - Покраска здания 다국어

В одной компании решили перекрасить серую стену своего офиса длиной n метров в корпоративные цвета: синий и оранжевый. Для этого они купили инновационного робота-маляра.

Робот может красить стены в соответствии с записанной в него программой. Программа представляет собой последовательностью команд. Каждая команда задается двумя целыми числами и цветом и сообщает роботу, какой отрезок c стены в какой цвет необходимо покрасить. Например, стену с планом раскраски BBOOO можно получить при помощи программы, состоящей из двух команд: покрасить в синий с первого метра по пятый, а затем — в оранжевый с третьего по пятый.

Одному из программистов компании поручили написать программу, исполнив которую, робот окрашивал бы стены в соответствие с заданной схемой. Он с легкостью справился с заданием и даже написал программу, содержащую в себе минимально возможное количество команд. После этого он задался вопросом: сколько всего существует программ такой же длины, которые покрасят стену в сответствии с планом раскраски?

В первой строке задано число T — количество тестов. Далее следуют описания T тестов.

В единстенной строке теста дана строка, состоящая из букв B и O, где буква на i-й позиции отвечает за то, в синий или в оранжевый цвет нужно покрасить i-й метр стены.

Суммарная длина строк не превышает 500000.

Для каждого из T тестовых примеров выведите одно число — количество программ программ минимальной длины, приводящих к покраске забора соответствующим образом. Так как ответ может быть большим, то выведите ответ по модулю 10⁹ + 7.