A. Штаб
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Сенсация, сенсация в двумерном государстве! Был пойман особо опасный преступник — один из членов знаменитой банды «Пихстеры». Как сообщает отдел по борьбе с преступностью, задержанный ехал на своей машине из главного штаба банды в киоск с мороженым, где и был пойман. Каждый объект двумерного государства (киоск с мороженым, машина, штаб) представляет собой точку на плоскости.

Машина преступника была оборудована GPS передатчиком. Данные передатчика показали, что на пути от штаба до киоска с мороженым машина совершила ровно n перемещений. За одно перемещение машина из точки (x, y) может попасть в одну из четырех точек: перемещение в точку (x - 1, y) будем обозначать буквой «L», в точку (x + 1, y) — «R», в точку (x, y - 1) — «D», в точку (x, y + 1) — «U».

Из-за большой погрешности GPS передатчик, установленный на машине, не сохраняет точную последовательность перемещений машины. Вместо точных перемещений в журнал GPS записываются возможные перемещения в виде одной из строк: «UL», «UR», «DL», «DR» или «ULDR». Каждая такая строка обозначает, что было совершено ровно одно перемещение, соответствующее какому-то одному символу строки. Например, строка «UL» обозначает, что было совершено либо перемещение «U», либо перемещение «L».

Вам задан журнал возможных перемещений преступника от штаба банды до киоска в хронологическом порядке. Зная, что киоск с мороженым находится в точке с координатами (0, 0), определите в скольки различных точках может находиться штаб банды (то есть, требуется найти количество возможных позиций старта машины).

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

В первой строке записано единственное целое число n (1 ≤ n ≤ 2·105) — количество перемещений машины от штаба до киоска.

Каждая из следующих n строк обозначает возможное перемещение машины. Гарантируется, что каждое возможное перемещение это одна из строк: «UL», «UR», «DL», «DR» или «ULDR».

Все перемещения заданы в хронологическом порядке.

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

Выведите единственное целое число — количество различных возможных положений штаба банды.

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

Примеры
Входные данные
3
UR
UL
ULDR
Выходные данные
9
Входные данные
2
DR
DL
Выходные данные
4
Примечание

Рисунок ниже показывает девять возможных положений штаба банды из первого примера:

Например, из точки (1, 0), машина может доехать до точки (0, 0), совершая следующие перемещения: