Cuber QQ got a table of infinite size. He will consider the table rows numbered from top to bottom through , and the columns numbered from left to right through . Then he'll denote the cell in row x and column y as (x, y).

Initially, there are n trucks at cell respectively. The goal is that each of the trucks have to go to one of the n destinations, located at cell . Cuber QQ has to make sure that there are no two trucks at the same destination. In another word, any two paths of the trucks are non-intersecting (no common points).

Each truck can go from cell (x, y) to one of two cells (x + 1, y) and (x, y - 1). And the truck can't have any chance of meeting any other trucks along the way.

Now can you help Cuber QQ to find the number of ways that trucks can achieve this goal.

The first line contains one integer n (), where n is the number of trucks.

The second line contains n integers  (, ), which are the trucks' initial positions.

Print the number of ways modulo 998244353 on the only line of output.

3
1 2 3

4