二次元王国里的震撼、震撼!警方抓获了一名高度危险的歹徒,他是臭名昭著的“Pihters”团伙的成员。法律部门表示,这名歹徒开车从该团伙总部出发时撞上了一个冰淇淋摊。摊位、汽车和总部在二维王国中各占据一处。
歹徒的汽车配备了 GPS 发射器。发射机显示,汽车从指挥部到停车位的途中一共进行了 n 次动作。运动可以将汽车从点 (x, y) 移动到以下四个点之一:到点 (x - 1, y)(我们将用字母“L”标记)、到点 (x + 1, y) - “R”、到点 (x, y - 1) - “D”、到点 (x, y + 1) - “U”。
GPS 发射器非常不准确,并且无法保留汽车运动的准确顺序。相反,它会记录汽车可能的运动。每个记录都是以下类型之一的字符串:“UL”、“UR”、“DL”、“DR”或“ULDR”。每个这样的字符串都意味着汽车进行了与该字符串的一个字符相对应的单个运动。例如,字符串“UL”表示汽车移动了“U”或“L”。
你已经收到了日志,其中记录了歹徒从总部到摊位的可能活动。日志记录按时间顺序给出。假设冰淇淋摊位于点 (0, 0),您的任务是打印可以包含帮派总部的不同点的数量(即汽车起源的不同可能位置的数量)。
输入
第一行包含一个整数n (1 ≤ n ≤ 2·105) — 汽车从总部到摊位的行驶次数。
以下 n 行中的每一行都描述了汽车可能的运动。确保每个可能的移动都是以下字符串之一:“UL”、“UR”、“DL”、“DR”或“ULDR”。
所有动作均按时间顺序给出。
请不要使用 %lld 说明符在 C++ 中读取或写入 64 位整数。最好使用 cin 和 cout 流或 %I64d 说明符。
输出
打印一个整数——该团伙总部的不同可能位置的数量。
示例
输入 #1
3 UR UL ULDR
输出 #1
9
输入 #2
2 DR DL
输出 #2
4
注意
下图展示了第一个样本中该团伙总部的九个可能位置:
例如,以下动作可以让小车从点 (1, 0) 到达点 (0, 0):