Komorebi is a primary student who is learning how to draw a mountain.

First of all, he gets an grid, and he can paint some cells black and others white. Let's define a grid is good if:

1. All the black cells are connected.

2. For every column of the grid, if there are black cells, all the black cells must be connected and there must be one on the bottom.

Let's call the height of the highest black cell in the -th column . Specially, if there isn't any black cell in the -th column, then . To make the good graph more likely to be a mountain, the graph should satisfy that there at least exists a pair of integers :

1. 

2. All the () are non-decreasing.

3. All the () are non-increasing.

4. All the () are equal.

Komorebi wants to know how many kinds of mountain graphs he can draw by his grid. Can you help him?