Col. Sheffard is going to make a training for Cpt. Plice. The colonel has a polygon containing infinite number of closed doors placed one by one in a row. Initially Cpt. Plice stands in front of the first door. The captain is able to perform the following two commands:
-
open the first closed door and go to the front of the next closed door (mark this command as '(' ),
-
go to the front of the last of currently opened doors and close it (mark this command as ')' ).
A sequence of commands is valid if the following conditions are met:
-
there is at least one opened door when the command ')' should be performed (in particular, the first command shouldn't be ')'),
-
all the doors are closed after performing all commands from the sequence (the captain stands in front of the first door).
Col. Sheffard received a template − a rectangular grid with
n rows and
m columns where each cell contains one of the commands, i.e. '
(' or '
)'. The colonel has to choose a training plan for the captain − select a non-empty rectangle from the grid, each row of the rectangle will be an independent training for the captain. The training plan is valid, if
each row of the selected rectangle is a valid sequence of commands.
You are to find the number of ways to select a valid training plan for a given grid. The selected rectangle should be continuous, i.e. without holes. Plans are different if they have different positions of their corners even if their contents are the same.
Output
Output a single integer − the number of rectangles on the template, corresponding to a valid training plan. Two rectangles with equal content but different positions of corners should be counted both.