CF589E.Training with Doors

上校将为下士进行训练。上校有一个房间，里面有无数扇紧闭的门，一扇接一扇地排成一行。上校能够执行以下两个命令：

1.打开第一扇关着的门，走到下一扇关着门的前面（将此命令标记为“（”）

2.走到当前打开的最后一扇门的前面并将其关闭（将此命令标记为“）”）。

如果满足以下条件，则命令序列有效：

1.当应该执行命令“）”时，至少有一扇门是打开的（第一个命令不应该是“）”）

2.执行完序列中的所有命令后，所有门都关闭了（船长站在第一扇门前）。

上校收到了一个字符网格——一个有n行和m列的网格，其中每个元素包含一个命令，即“（”或“）”。上校必须为上尉选择一个训练计划——从字符网格中选择一个矩形X。如果所选矩形X的每一行都是有效的命令序列，则训练计划有效。

你需要给出有多少满足的矩形X。所选的矩形X应该是完整的的(即中间没有空格)。即使所包含的命令相同，如果它们的位置不同，那也算不同的矩形。

第一行包含两个整数n和m(1<=n,m<=50000).n为字符网格的行数,m为列数.
每一行都只包含“（”或“）”

有多少不同的方法数(不同的，满足条件的矩形)

翻译:WAITER