//疯狂容斥……
//容斥0：枚举哪些格子没有被覆盖，然后对于一个位置如果行列都没有被钦定未被覆盖的格子，那么方案数是 2 。
//显然这个容斥的复杂度非常爆炸，而且也不是很好 DP 。
//容斥1：枚举哪些列里面有格子被钦定未被覆盖，那么这些列都不能放棋子了。设集合为 $S$ 。
//那么此时考虑一个极长行连续段的贡献，假设里面有 $p$ 个格子在 $S$ 里，那么贡献有两种：
//1. 这 $p$ 个格子都没有钦定未覆盖，所以剩下的格子可以随便放，方案数 $2^{len-p}$ 。
//2. 枚举里面有几个格子被钦定，方案数是 $\sum\limits_{i=1}^{p} {p\choose i}(-1)^i=-[p\ne 0]$ 。
//但是这样算出来的结果仍然是错的，因为某一些在 $S$ 里的列可能还是没有钦定的格子。
//容斥2：在容斥1的基础上再套一个容斥，枚举集合 $T\subseteq S$ ，表示 $T$ 里面没有被钦定的格子。
//设一个极长行连续段里面有 $q$ 个格子在 $T$ 里面，那么第二种的贡献变成了 $-[p\ne q]$ 。
//注意到此时贡献只和 $p,[p\ne q]$ 有关，所以 DP 的状态数可能不会太大，来尝试设计一个 DP 。
//每次从 $h$ 最小的位置切开来，下面会形成一个矩形，上面会被分裂成一些子问题，并且子问题形成树形结构，并且矩形里的行连续段的 $p,q$ 就是由上面的加起来，再算上独有的列。
//于是可以设 $dp_{x,p,0/1}$ ，$p$ 表示 $S$ 的大小，$0/1$ 表示是否有 $p\ne q$ 。
//转移就是无脑从儿子用背包合并过来。对于独有的列也可以看做是一个特殊的儿子。
//然后此时每一行的方案数都是相同的，直接快速幂即可。
//复杂度 $O(n^2\log n)$ ，预处理一些东西可以变成 $O(n^2)$ 。
#include<bits/stdc++.h>
clock_t t=clock();
namespace my_std{
	using namespace std;
	#define pii pair<int,int>
	#define fir first
	#define sec second
	#define MP make_pair
	#define rep(i,x,y) for (int i=(x);i<=(y);i++)
	#define drep(i,x,y) for (int i=(x);i>=(y);i--)
	#define go(x) for (int i=head[x];i;i=edge[i].nxt)
	#define templ template<typename T>
	#define sz 666
	#define mod 998244353ll
	typedef long long ll;
	typedef double db;
//	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//	templ inline T rnd(T l,T r) {return uniform_int_distribution<T>(l,r)(rng);}
	templ inline bool chkmax(T &x,T y){return x<y?x=y,1:0;}
	templ inline bool chkmin(T &x,T y){return x>y?x=y,1:0;}
	templ inline void read(T& t)
	{
		t=0;char f=0,ch=getchar();double d=0.1;
		while(ch>'9'||ch<'0') f|=(ch=='-'),ch=getchar();
		while(ch<='9'&&ch>='0') t=t*10+ch-48,ch=getchar();
		if(ch=='.'){ch=getchar();while(ch<='9'&&ch>='0') t+=d*(ch^48),d*=0.1,ch=getchar();}
		t=(f?-t:t);
	}
//	template<typename T,typename... Args>inline void read(T& t,Args&... args){read(t); read(args...);}
	char __sr[1<<21],__z[20];int __C=-1,__zz=0;
	inline void Ot(){fwrite(__sr,1,__C+1,stdout),__C=-1;}
	inline void print(register int x)
	{
		if(__C>1<<20)Ot();if(x<0)__sr[++__C]='-',x=-x;
		while(__z[++__zz]=x%10+48,x/=10);
		while(__sr[++__C]=__z[__zz],--__zz);__sr[++__C]='\n';
	}
	void file()
	{
		#ifdef NTFOrz
		freopen("a.in","r",stdin);
		#endif
	}
	inline void chktime()
	{
		#ifdef NTFOrz
		cout<<(clock()-t)/1000.0<<'\n';
		#endif
	}
	#ifdef mod
	ll ksm(ll x,int y){ll ret=1;for (;y;y>>=1,x=x*x%mod) if (y&1) ret=ret*x%mod;return ret;}
	ll inv(ll x){return ksm(x,mod-2);}
	#else
	ll ksm(ll x,int y){ll ret=1;for (;y;y>>=1,x=x*x) if (y&1) ret=ret*x;return ret;}
	#endif
//	inline ll mul(ll a,ll b){ll d=(ll)(a*(double)b/mod+0.5);ll ret=a*b-d*mod;if (ret<0) ret+=mod;return ret;}
}
using namespace my_std;

ll fac[sz],_fac[sz];
void init(){_fac[0]=fac[0]=1;rep(i,1,sz-1) _fac[i]=inv(fac[i]=fac[i-1]*i%mod);}
ll C(int n,int m){return n>=m&&m>=0?fac[n]*_fac[m]%mod*_fac[n-m]%mod:0;}

int n;
int h[sz];

ll dp[sz][sz][2],d[sz][2],tmp[sz][2]; int id;

void merge(int x,int &s1,int s2)
{
	rep(i,0,s1+s2) tmp[i][0]=tmp[i][1]=0;
	rep(i,0,s1) rep(j,0,s2) rep(a,0,1) rep(b,0,1) (tmp[i+j][a|b]+=dp[x][i][a]*d[j][b]%mod)%=mod;
	s1+=s2; rep(i,0,s1) rep(k,0,1) dp[x][i][k]=tmp[i][k];
}
int solve(int l,int r,int lw)
{
	int mn=1e9;
	rep(i,l,r) chkmin(mn,h[i]);
	int cc=0;
	rep(i,l,r) cc+=(h[i]==mn);
	int x=++id,s=0; dp[x][0][0]=1;
	for (int L=l,R;L<=r;L=R+1)
	{
		if (h[L]==mn) { R=L; d[0][0]=1,d[0][1]=0,d[1][0]=mod-1,d[1][1]=1; merge(x,s,1); continue; }
		for (R=L;R<r&&h[R+1]!=mn;++R);
		int v=solve(L,R,mn);
		rep(i,0,R-L+1) rep(k,0,1) d[i][k]=dp[v][i][k];
		merge(x,s,R-L+1);
	}
	rep(i,0,s) rep(k,0,1) dp[x][i][k]=dp[x][i][k]*ksm(ksm(2,r-l+1-i)-k,mn-lw)%mod;
	return x;
}

int main()
{
	file();
	init();
	read(n);
	rep(i,1,n) read(h[i]);
	int x=solve(1,n,0);
	ll ans=0;
	rep(i,0,n) rep(k,0,1) (ans+=dp[x][i][k])%=mod;
	cout<<ans;
	return 0;
}
### Prompt

Your task is to create a cpp solution to the following problem:

Let us consider a grid of squares with N rows and N columns. Arbok has cut out some part of the grid so that, for each i = 1, 2, \ldots, N, the bottommost h_i squares are remaining in the i-th column from the left. Now, he wants to place rooks into some of the remaining squares.

A rook is a chess piece that occupies one square and can move horizontally or vertically, through any number of unoccupied squares. A rook can not move through squares that have been cut out by Arbok.

Let's say that a square is covered if it either contains a rook, or a rook can be moved to this square in one move.

Find the number of ways to place rooks into some of the remaining squares so that every remaining square is covered, modulo 998244353.

Constraints

* 1 \leq N \leq 400
* 1 \leq h_i \leq N
* All input values are integers.

Input

Input is given from Standard Input in the following format:


N
h_1 h_2 ... h_N


Output

Print the number of ways to place rooks into some of the remaining squares so that every remaining square is covered, modulo 998244353.

Examples

Input

2
2 2


Output

11


Input

3
2 1 2


Output

17


Input

4
1 2 4 1


Output

201


Input

10
4 7 4 8 4 6 8 2 3 6


Output

263244071

### Response

```cpp
//疯狂容斥……
//容斥0：枚举哪些格子没有被覆盖，然后对于一个位置如果行列都没有被钦定未被覆盖的格子，那么方案数是 2 。
//显然这个容斥的复杂度非常爆炸，而且也不是很好 DP 。
//容斥1：枚举哪些列里面有格子被钦定未被覆盖，那么这些列都不能放棋子了。设集合为 $S$ 。
//那么此时考虑一个极长行连续段的贡献，假设里面有 $p$ 个格子在 $S$ 里，那么贡献有两种：
//1. 这 $p$ 个格子都没有钦定未覆盖，所以剩下的格子可以随便放，方案数 $2^{len-p}$ 。
//2. 枚举里面有几个格子被钦定，方案数是 $\sum\limits_{i=1}^{p} {p\choose i}(-1)^i=-[p\ne 0]$ 。
//但是这样算出来的结果仍然是错的，因为某一些在 $S$ 里的列可能还是没有钦定的格子。
//容斥2：在容斥1的基础上再套一个容斥，枚举集合 $T\subseteq S$ ，表示 $T$ 里面没有被钦定的格子。
//设一个极长行连续段里面有 $q$ 个格子在 $T$ 里面，那么第二种的贡献变成了 $-[p\ne q]$ 。
//注意到此时贡献只和 $p,[p\ne q]$ 有关，所以 DP 的状态数可能不会太大，来尝试设计一个 DP 。
//每次从 $h$ 最小的位置切开来，下面会形成一个矩形，上面会被分裂成一些子问题，并且子问题形成树形结构，并且矩形里的行连续段的 $p,q$ 就是由上面的加起来，再算上独有的列。
//于是可以设 $dp_{x,p,0/1}$ ，$p$ 表示 $S$ 的大小，$0/1$ 表示是否有 $p\ne q$ 。
//转移就是无脑从儿子用背包合并过来。对于独有的列也可以看做是一个特殊的儿子。
//然后此时每一行的方案数都是相同的，直接快速幂即可。
//复杂度 $O(n^2\log n)$ ，预处理一些东西可以变成 $O(n^2)$ 。
#include<bits/stdc++.h>
clock_t t=clock();
namespace my_std{
	using namespace std;
	#define pii pair<int,int>
	#define fir first
	#define sec second
	#define MP make_pair
	#define rep(i,x,y) for (int i=(x);i<=(y);i++)
	#define drep(i,x,y) for (int i=(x);i>=(y);i--)
	#define go(x) for (int i=head[x];i;i=edge[i].nxt)
	#define templ template<typename T>
	#define sz 666
	#define mod 998244353ll
	typedef long long ll;
	typedef double db;
//	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//	templ inline T rnd(T l,T r) {return uniform_int_distribution<T>(l,r)(rng);}
	templ inline bool chkmax(T &x,T y){return x<y?x=y,1:0;}
	templ inline bool chkmin(T &x,T y){return x>y?x=y,1:0;}
	templ inline void read(T& t)
	{
		t=0;char f=0,ch=getchar();double d=0.1;
		while(ch>'9'||ch<'0') f|=(ch=='-'),ch=getchar();
		while(ch<='9'&&ch>='0') t=t*10+ch-48,ch=getchar();
		if(ch=='.'){ch=getchar();while(ch<='9'&&ch>='0') t+=d*(ch^48),d*=0.1,ch=getchar();}
		t=(f?-t:t);
	}
//	template<typename T,typename... Args>inline void read(T& t,Args&... args){read(t); read(args...);}
	char __sr[1<<21],__z[20];int __C=-1,__zz=0;
	inline void Ot(){fwrite(__sr,1,__C+1,stdout),__C=-1;}
	inline void print(register int x)
	{
		if(__C>1<<20)Ot();if(x<0)__sr[++__C]='-',x=-x;
		while(__z[++__zz]=x%10+48,x/=10);
		while(__sr[++__C]=__z[__zz],--__zz);__sr[++__C]='\n';
	}
	void file()
	{
		#ifdef NTFOrz
		freopen("a.in","r",stdin);
		#endif
	}
	inline void chktime()
	{
		#ifdef NTFOrz
		cout<<(clock()-t)/1000.0<<'\n';
		#endif
	}
	#ifdef mod
	ll ksm(ll x,int y){ll ret=1;for (;y;y>>=1,x=x*x%mod) if (y&1) ret=ret*x%mod;return ret;}
	ll inv(ll x){return ksm(x,mod-2);}
	#else
	ll ksm(ll x,int y){ll ret=1;for (;y;y>>=1,x=x*x) if (y&1) ret=ret*x;return ret;}
	#endif
//	inline ll mul(ll a,ll b){ll d=(ll)(a*(double)b/mod+0.5);ll ret=a*b-d*mod;if (ret<0) ret+=mod;return ret;}
}
using namespace my_std;

ll fac[sz],_fac[sz];
void init(){_fac[0]=fac[0]=1;rep(i,1,sz-1) _fac[i]=inv(fac[i]=fac[i-1]*i%mod);}
ll C(int n,int m){return n>=m&&m>=0?fac[n]*_fac[m]%mod*_fac[n-m]%mod:0;}

int n;
int h[sz];

ll dp[sz][sz][2],d[sz][2],tmp[sz][2]; int id;

void merge(int x,int &s1,int s2)
{
	rep(i,0,s1+s2) tmp[i][0]=tmp[i][1]=0;
	rep(i,0,s1) rep(j,0,s2) rep(a,0,1) rep(b,0,1) (tmp[i+j][a|b]+=dp[x][i][a]*d[j][b]%mod)%=mod;
	s1+=s2; rep(i,0,s1) rep(k,0,1) dp[x][i][k]=tmp[i][k];
}
int solve(int l,int r,int lw)
{
	int mn=1e9;
	rep(i,l,r) chkmin(mn,h[i]);
	int cc=0;
	rep(i,l,r) cc+=(h[i]==mn);
	int x=++id,s=0; dp[x][0][0]=1;
	for (int L=l,R;L<=r;L=R+1)
	{
		if (h[L]==mn) { R=L; d[0][0]=1,d[0][1]=0,d[1][0]=mod-1,d[1][1]=1; merge(x,s,1); continue; }
		for (R=L;R<r&&h[R+1]!=mn;++R);
		int v=solve(L,R,mn);
		rep(i,0,R-L+1) rep(k,0,1) d[i][k]=dp[v][i][k];
		merge(x,s,R-L+1);
	}
	rep(i,0,s) rep(k,0,1) dp[x][i][k]=dp[x][i][k]*ksm(ksm(2,r-l+1-i)-k,mn-lw)%mod;
	return x;
}

int main()
{
	file();
	init();
	read(n);
	rep(i,1,n) read(h[i]);
	int x=solve(1,n,0);
	ll ans=0;
	rep(i,0,n) rep(k,0,1) (ans+=dp[x][i][k])%=mod;
	cout<<ans;
	return 0;
}
```