D. Drowsy Robots
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

At X-Camp Academy, students don't just learn to code. In fact, coding is merely 5% of what X-Camp helps students to begin with. Instead, they spend most of their time learning to tackle challenges through algorithms and problem-solving. Many of the methodologies are used in the state-of-the-art research and development of artificial intelligence and other technology or science.

Today's task is straight out of a robotics competition: A fleet of $$$n$$$ autonomous delivery robots are standing in a line, where the $$$i$$$-th robot is currently at position $$$x = i$$$.

But a software bug means they will all be moving at the same speed! At time $$$t = 0$$$ seconds, all robots will start moving to the left (in the negative $$$x$$$ direction) at a constant speed of $$$1$$$ unit per second. If they keep going at this rate, they'll get to their destinations at the wrong time and disrupt the entire system. Fortunately, you have a specialized slow-motion gun that can selectively reduce their speed.

When you fire your slow-motion gun, all robots at positions $$$x \geq 0$$$ have their current speeds halved. You are only allowed to fire at positive integer times, i.e. when $$$t$$$ is an integer and $$$t \gt 0$$$. You are allowed to fire multiple times simultaneously.

You are also given an integer sequence $$$1 \leq a_1 \leq a_2 \leq \ldots \leq a_n$$$. Your goal is to fire the gun exactly $$$a_n$$$ times, so that for all $$$1 \leq i \leq n$$$, the $$$i$$$-th robot gets hit by the ray gun exactly $$$a_i$$$ times.

How many ways are there to achieve the goal? Two ways are different if you fire the gun a different number of times at time $$$t$$$, for some $$$t \gt 0$$$. We can show that the answer is finite, but it may be large, so output the remainder modulo $$$998\,244\,353$$$.

Input

The first line contains $$$n$$$ ($$$1 \leq n \leq 100$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots a_n$$$ ($$$1 \leq a_1 \leq a_2 \leq \ldots \leq a_n \leq 100$$$).

Output

Print the answer, modulo $$$998\,244\,353$$$.

Examples
Input
1
1
Output
1
Input
5
1 1 1 2 2
Output
2
Input
5
100 100 100 100 100
Output
1
Input
2
2 5
Output
84
Input
6
1 2 5 6 8 8
Output
22020096
Input
4
2 3 20 25
Output
846561846
Note

In the first test, the only solution is to fire the gun once at time $$$t=1$$$.

In the second test, we again have to fire the gun once at $$$t=1$$$. But we have $$$2$$$ options for the second time we fire the gun. We can either fire a second time at $$$t=6$$$ or $$$t=7$$$. Note that we cannot fire between $$$2 \leq t \leq 5$$$, otherwise robot $$$3$$$ would get hit a second time. And we cannot fire after $$$t \leq 8$$$, otherwise robot $$$4$$$ would only get hit once.

In the third test, the only option is to fire the gun $$$100$$$ times at $$$t=1$$$.