// #pragma GCC target("avx")  // CPU 処理並列化
// #pragma GCC optimize("O3")  // CPU 処理並列化
// #pragma GCC optimize("unroll-loops")  // 条件処理の呼び出しを減らす
// #define BEGIN_STACK_EXTEND(size) void * stack_extend_memory_ = malloc(size);void * stack_extend_origin_memory_;char * stack_extend_dummy_memory_ = (char*)alloca((1+(int)(((long long)stack_extend_memory_)&127))*16);*stack_extend_dummy_memory_ = 0;asm volatile("mov %%rsp, %%rbx\nmov %%rax, %%rsp":"=b"(stack_extend_origin_memory_):"a"((char*)stack_extend_memory_+(size)-1024));
// #define END_STACK_EXTEND asm volatile("mov %%rax, %%rsp"::"a"(stack_extend_origin_memory_));free(stack_extend_memory_);

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
#include<numeric>
#include<unordered_set>
#include<unordered_map>
#include<complex>
using namespace std;
const long long mod=998244353;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const double EPS=1e-11;
const double INF=1e+10;
const double PI=acos(-1.0);
const int C_SIZE = 3100000;
const int UF_SIZE = 3100000;
namespace{
	long long fact[C_SIZE];
	long long finv[C_SIZE];
	long long inv[C_SIZE];
	inline long long Comb(int a,int b){
	 	if(a<b||b<0)return 0;
	 	return fact[a]*finv[b]%mod*finv[a-b]%mod;
	}
	void init_C(int n){
		fact[0]=finv[0]=inv[1]=1;
		for(int i=2;i<n;i++){
			inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
		}
		for(int i=1;i<n;i++){
			fact[i]=fact[i-1]*i%mod;
			finv[i]=finv[i-1]*inv[i]%mod;
		}
	}
	long long pw(long long a,long long b){
		if(a<0LL)return 0;
		if(b<0LL)return 0;
		long long ret=1;
		while(b){
			if(b%2)ret=ret*a%mod;
			a=a*a%mod;
			b/=2;
		}
		return ret;
	}
	long long pw_mod(long long a,long long b,long long M){
		if(a<0LL)return 0;
		if(b<0LL)return 0;
		long long ret=1;
		while(b){
			if(b%2)ret=ret*a%M;
			a=a*a%M;
			b/=2;
		}
		return ret;
	}
	int pw_mod_int(int a,int b,int M){
		if(a<0)return 0;
		if(b<0)return 0;
		int ret=1;
		while(b){
			if(b%2)ret=(long long)ret*a%M;
			a=(long long)a*a%M;
			b/=2;
		}
		return ret;
	}
	int ABS(int a){return max(a,-a);}
	long long ABS(long long a){return max(a,-a);}
	double ABS(double a){return max(a,-a);}
	int sig(double r) { return (r < -EPS) ? -1 : (r > +EPS) ? +1 : 0; }
	int UF[UF_SIZE];
	void init_UF(int n){
		for(int i=0;i<n;i++)UF[i]=-1;
	}
	int FIND(int a){
		if(UF[a]<0)return a;
		return UF[a]=FIND(UF[a]);
	}
	void UNION(int a,int b){
		a=FIND(a);b=FIND(b);if(a==b)return;
		if(UF[a]>UF[b])swap(a,b);
		UF[a]+=UF[b];UF[b]=a;
	}
}
// ここから編集しろ
long long dp[410][410][410];
long long dp2[410][410];
long long dp3[410][410];

int p[410];
int rt[410][410];
long long e2[410];
void calc(int n,int L,int R){
	if(p[L]<n){
		dp[n][L][0]=1;
		return;
	}
	int at=L;
	vector<pair<int,int> > v;
	while(at<R){
		v.push_back(make_pair(at,rt[n][at]));
		at=rt[n][at];
	}
	for(int i=0;i<v.size();i++){
		calc(n+1,v[i].first,v[i].second);
	}
	for(int i=0;i<=v.size();i++){
		for(int j=0;j<=R-L;j++){
			dp2[i][j]=0;
		}
	}
	dp2[0][0]=1;
	for(int i=0;i<v.size();i++){
		for(int j=0;j<=R-L;j++){
			if(!dp2[i][j])continue;
			for(int l=0;l<=v[i].second-v[i].first;l++){
				dp2[i+1][j+l]=(dp2[i+1][j+l]+dp2[i][j]*dp[n+1][v[i].first][l])%mod;
			}
		}
	}
	for(int i=0;i<=R-L;i++)for(int j=0;j<=R-L;j++)dp3[i][j]=0;
	dp3[0][0]=1;
	for(int i=L;i<R;i++){
		for(int j=0;j<=i-L;j++){
			dp3[i-L+1][j]=(dp3[i-L+1][j]+dp3[i-L][j])%mod;
			dp3[i-L+1][j+1]=(dp3[i-L+1][j+1]+dp3[i-L][j]*e2[p[i]-n])%mod;
		}
	}
	int sz=v.size();
	for(int i=0;i<=R-L;i++){
		if(i==0){
			dp[n][L][i]=(dp[n][L][i]+dp2[sz][i])%mod;

		}else{
			dp[n][L][i]=(dp[n][L][i]+dp2[sz][i]*e2[i])%mod;
			dp[n][L][i]=(dp[n][L][i]+mod-dp2[sz][i]*e2[R-L]%mod)%mod;
		}
	}
	for(int i=1;i<=R-L;i++){
		if(i%2==0)dp[n][L][i]=(dp[n][L][i]+dp3[R-L][i]*e2[R-L]%mod)%mod;
			else dp[n][L][i]=(dp[n][L][i]+mod-dp3[R-L][i]*e2[R-L]%mod)%mod;
	}
	// for(int i=0;i<=R-L;i++){
		// printf("%d %d %d %d: %lld\n",n,L,R,i,dp[n][L][i]*16%mod);
	// }
}
int main(){
	init_C(2100);
	int a;scanf("%d",&a);
	for(int i=0;i<a;i++){
		scanf("%d",p+i);
	}
	e2[0]=1;
	for(int i=1;i<410;i++)e2[i]=e2[i-1]*d2%mod;
	// for(int i=0;i<410;i++){
	// 	for(int j=0;j<410;j++){
	// 		for(int k=0;k<410;k++)
	// 			dp[i][j][k]=-1;
	// 	}
	// }
	for(int i=1;i<=a;i++){
		for(int j=a-1;j>=0;j--){
			if(p[j]<=i||p[j+1]<=i){
				rt[i][j]=j+1;
			}else{
				rt[i][j]=rt[i][j+1];
			}
		}
	}
	calc(1,0,a);
	long long ret=0;
	int T=0;
	for(int i=0;i<a;i++)T+=p[i];
	for(int i=0;i<=a;i++){
		if(i%2==0){
			ret=(ret+dp[1][0][i])%mod;
		}else{
			ret=(ret+dp[1][0][i])%mod;
		}
	}
	ret=ret*pw(2,T)%mod;
	printf("%lld\n",ret);
}
### Prompt

Generate 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
// #pragma GCC target("avx")  // CPU 処理並列化
// #pragma GCC optimize("O3")  // CPU 処理並列化
// #pragma GCC optimize("unroll-loops")  // 条件処理の呼び出しを減らす
// #define BEGIN_STACK_EXTEND(size) void * stack_extend_memory_ = malloc(size);void * stack_extend_origin_memory_;char * stack_extend_dummy_memory_ = (char*)alloca((1+(int)(((long long)stack_extend_memory_)&127))*16);*stack_extend_dummy_memory_ = 0;asm volatile("mov %%rsp, %%rbx\nmov %%rax, %%rsp":"=b"(stack_extend_origin_memory_):"a"((char*)stack_extend_memory_+(size)-1024));
// #define END_STACK_EXTEND asm volatile("mov %%rax, %%rsp"::"a"(stack_extend_origin_memory_));free(stack_extend_memory_);

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
#include<numeric>
#include<unordered_set>
#include<unordered_map>
#include<complex>
using namespace std;
const long long mod=998244353;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const double EPS=1e-11;
const double INF=1e+10;
const double PI=acos(-1.0);
const int C_SIZE = 3100000;
const int UF_SIZE = 3100000;
namespace{
	long long fact[C_SIZE];
	long long finv[C_SIZE];
	long long inv[C_SIZE];
	inline long long Comb(int a,int b){
	 	if(a<b||b<0)return 0;
	 	return fact[a]*finv[b]%mod*finv[a-b]%mod;
	}
	void init_C(int n){
		fact[0]=finv[0]=inv[1]=1;
		for(int i=2;i<n;i++){
			inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
		}
		for(int i=1;i<n;i++){
			fact[i]=fact[i-1]*i%mod;
			finv[i]=finv[i-1]*inv[i]%mod;
		}
	}
	long long pw(long long a,long long b){
		if(a<0LL)return 0;
		if(b<0LL)return 0;
		long long ret=1;
		while(b){
			if(b%2)ret=ret*a%mod;
			a=a*a%mod;
			b/=2;
		}
		return ret;
	}
	long long pw_mod(long long a,long long b,long long M){
		if(a<0LL)return 0;
		if(b<0LL)return 0;
		long long ret=1;
		while(b){
			if(b%2)ret=ret*a%M;
			a=a*a%M;
			b/=2;
		}
		return ret;
	}
	int pw_mod_int(int a,int b,int M){
		if(a<0)return 0;
		if(b<0)return 0;
		int ret=1;
		while(b){
			if(b%2)ret=(long long)ret*a%M;
			a=(long long)a*a%M;
			b/=2;
		}
		return ret;
	}
	int ABS(int a){return max(a,-a);}
	long long ABS(long long a){return max(a,-a);}
	double ABS(double a){return max(a,-a);}
	int sig(double r) { return (r < -EPS) ? -1 : (r > +EPS) ? +1 : 0; }
	int UF[UF_SIZE];
	void init_UF(int n){
		for(int i=0;i<n;i++)UF[i]=-1;
	}
	int FIND(int a){
		if(UF[a]<0)return a;
		return UF[a]=FIND(UF[a]);
	}
	void UNION(int a,int b){
		a=FIND(a);b=FIND(b);if(a==b)return;
		if(UF[a]>UF[b])swap(a,b);
		UF[a]+=UF[b];UF[b]=a;
	}
}
// ここから編集しろ
long long dp[410][410][410];
long long dp2[410][410];
long long dp3[410][410];

int p[410];
int rt[410][410];
long long e2[410];
void calc(int n,int L,int R){
	if(p[L]<n){
		dp[n][L][0]=1;
		return;
	}
	int at=L;
	vector<pair<int,int> > v;
	while(at<R){
		v.push_back(make_pair(at,rt[n][at]));
		at=rt[n][at];
	}
	for(int i=0;i<v.size();i++){
		calc(n+1,v[i].first,v[i].second);
	}
	for(int i=0;i<=v.size();i++){
		for(int j=0;j<=R-L;j++){
			dp2[i][j]=0;
		}
	}
	dp2[0][0]=1;
	for(int i=0;i<v.size();i++){
		for(int j=0;j<=R-L;j++){
			if(!dp2[i][j])continue;
			for(int l=0;l<=v[i].second-v[i].first;l++){
				dp2[i+1][j+l]=(dp2[i+1][j+l]+dp2[i][j]*dp[n+1][v[i].first][l])%mod;
			}
		}
	}
	for(int i=0;i<=R-L;i++)for(int j=0;j<=R-L;j++)dp3[i][j]=0;
	dp3[0][0]=1;
	for(int i=L;i<R;i++){
		for(int j=0;j<=i-L;j++){
			dp3[i-L+1][j]=(dp3[i-L+1][j]+dp3[i-L][j])%mod;
			dp3[i-L+1][j+1]=(dp3[i-L+1][j+1]+dp3[i-L][j]*e2[p[i]-n])%mod;
		}
	}
	int sz=v.size();
	for(int i=0;i<=R-L;i++){
		if(i==0){
			dp[n][L][i]=(dp[n][L][i]+dp2[sz][i])%mod;

		}else{
			dp[n][L][i]=(dp[n][L][i]+dp2[sz][i]*e2[i])%mod;
			dp[n][L][i]=(dp[n][L][i]+mod-dp2[sz][i]*e2[R-L]%mod)%mod;
		}
	}
	for(int i=1;i<=R-L;i++){
		if(i%2==0)dp[n][L][i]=(dp[n][L][i]+dp3[R-L][i]*e2[R-L]%mod)%mod;
			else dp[n][L][i]=(dp[n][L][i]+mod-dp3[R-L][i]*e2[R-L]%mod)%mod;
	}
	// for(int i=0;i<=R-L;i++){
		// printf("%d %d %d %d: %lld\n",n,L,R,i,dp[n][L][i]*16%mod);
	// }
}
int main(){
	init_C(2100);
	int a;scanf("%d",&a);
	for(int i=0;i<a;i++){
		scanf("%d",p+i);
	}
	e2[0]=1;
	for(int i=1;i<410;i++)e2[i]=e2[i-1]*d2%mod;
	// for(int i=0;i<410;i++){
	// 	for(int j=0;j<410;j++){
	// 		for(int k=0;k<410;k++)
	// 			dp[i][j][k]=-1;
	// 	}
	// }
	for(int i=1;i<=a;i++){
		for(int j=a-1;j>=0;j--){
			if(p[j]<=i||p[j+1]<=i){
				rt[i][j]=j+1;
			}else{
				rt[i][j]=rt[i][j+1];
			}
		}
	}
	calc(1,0,a);
	long long ret=0;
	int T=0;
	for(int i=0;i<a;i++)T+=p[i];
	for(int i=0;i<=a;i++){
		if(i%2==0){
			ret=(ret+dp[1][0][i])%mod;
		}else{
			ret=(ret+dp[1][0][i])%mod;
		}
	}
	ret=ret*pw(2,T)%mod;
	printf("%lld\n",ret);
}
```