E. Сережа и квадраты
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Сережа нарисовал n точек на плоскости, точка номер i (1 ≤ i ≤ n) имеет координаты (i, 0). После этого Сережа подписал каждую точку маленькой или большой буквой латинского алфавита. Сережа очень не любит букву «x», поэтому он не использует ее, чтобы подписывать точки. Сережа считает, что точки подписаны красиво, если выполнены следующие условия:

  • все точки можно разбить на пары так, что каждая точка будет принадлежать ровно одной паре;
  • в каждой паре к точке с меньшей абсциссой будет приписана маленькая латинская буква, а к точке с большей абсциссой будет приписана соответствующая большая латинская буква;
  • если на каждой полученной паре будет построен квадрат такой, что точки пары будут противоположными точками квадрата, а отрезок между ними будет диагональю квадрата, то среди полученных квадратов не будет пары пересекающихся или касающихся.

Маленький Петя стер некоторые маленькие и все большие буквы, приписанные к точкам. Теперь Сереже интересно, сколько существует способов вернуть стертые буквы, чтобы точки были подписаны красиво.

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

В первой строке содержится целое число n (1 ≤ n ≤ 105) — количество точек. Во второй строке задана последовательность, состоящая из n маленьких латинских букв и знаков вопроса — последовательность букв, приписанных к точкам, в порядке от точек с меньшими абсциссами к точкам с большими. Знаки вопроса обозначают точки, у которых Петя стер подписанные буквы.

Гарантируется, что во входной строке отсутствует буква «x».

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

В единственную строку выведите остаток от деления ответа на задачу на число 4294967296. Если не существует ни одного способа вернуть стертые буквы, то выведите число 0.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

Примеры
Входные данные
4
a???
Выходные данные
50
Входные данные
4
abc?
Выходные данные
0
Входные данные
6
abc???
Выходные данные
1