output_description: Print the number of the ways to paint the squares, modulo 10^9+7.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
      h_1 h_2 ... h_N
attempt: #include <bits/stdc++.h>
  #include <ext/pb_ds/assoc_container.hpp>
  #include <ext/pb_ds/tree_policy.hpp>
  using namespace std;
  using namespace __gnu_pbds;
  #define ll long long
  #define ld long double
  #define pb push_back
  #define all(x) (x).begin(), (x).end()
  #define SZ(x) (int)(x).size()
  template <typename T> using ord_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
  mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  
  const int N = 105, MOD = 1e9 + 7;
  int n, h[N], mn[N][N], dp[2][N][N], same[N][N], g[N][N], p[N];
  
  int bp(int x, int y) {
  	int res = 1;
  	while (y) {
  		if (y & 1)
  			res = (ll)res * x % MOD;
  		x = (ll)x * x % MOD;
  		y /= 2;
  	}
  	return res;
  }
  
  void add(int & x, int y) {
  	x += y;
  	if (x >= MOD) x -= MOD;
  }
  
  int get(int l, int r) {
  	if (l > r) return 1;
  	int & res = g[l][r];
  	if (res != -1) return res;
  	return res = (ll)bp(2, max(0, h[l] - max(h[l - 1], mn[l + 1][r + 1]))) * get(l + 1, r) % MOD;
  }
  
  int solve(int f, int l, int r) {
  	if (l > r) return 1;
  	int & res = dp[f][l][r];
  	if (res != -1) return res;
  	res = 0;
  	if (f == 0) {
  		for (int i = l; i <= r; i++)
  			add(res, (ll)get(l, i) * solve(1, i + 1, r) % MOD);
  	}	else {
  		for (int i = l + 1; i <= r; i++)
  			add(res, (ll)same[l][i] * solve(0, i + 1, r) % MOD);
  	}
  	return res;
  }
  
  int main() {
  	ios_base::sync_with_stdio(false), cin.tie(NULL);
  	#ifdef LOCAL
  		freopen("input.txt", "r", stdin);
  	#endif
  	
  	memset(& g, -1, sizeof(g));
  	memset(& dp, -1, sizeof(dp));
  	cin >> n;
  	int mul = 0;
  	for (int i = 1; i <= n; i++) {
  		cin >> h[i];
  		if (h[i] == 1) mul++, h[i] = 0;
  	}
  	for (int r = n + 1; r >= 1; r--) {
  		mn[r][r] = h[r];
  		for (int l = r - 1; l >= 1; l--) {
  			mn[l][r] = min(h[l], mn[l + 1][r]);
  		}
  	}
  	p[0] = 1;
  	for (int i = 1; i <= n; i++) {
  		for (int j = 0; j <= i - 2; j++) {
  			add(p[i], p[j]);
  		}
  	}
  	for (int l = 1; l <= n; l++) {
  		for (int r = l; r <= n; r++) {
  			same[l][r] = 1;
  			for (int k = l; k <= r; k++) {
  				int hl = (k == l) ? 0 : h[k - 1];
  				int hr = (k == r) ? 0 : h[k + 1];
  				same[l][r] = (ll)same[l][r] * bp(2, max(0, h[k] - max(hl, hr))) % MOD;
  			}
  			same[l][r] = (ll)same[l][r] * p[r - l + 1] % MOD;
  		}
  	}
  	int last = 0, res = 1;
  	for (int i = 1; i <= n + 1; i++) {
  		if (h[i] == 0) {
  			if (last + 1 <= i - 1) {
  				int cur = (solve(0, last + 1, i - 1) + solve(1, last + 1, i - 1)) % MOD;
  				cur = cur * 2 % MOD;
  				cur = (cur - get(last + 1, i - 1) + MOD) % MOD;
  				res = (ll)res * cur % MOD;
  			}
  			last = i;
  		}
  	}
  	cout << (ll)res * bp(2, mul) % MOD;
  }
  
problem_description: Statement
  
  Let us consider a grid of squares with 10^9 rows and N columns. Let (i, j) be
  the square at the i-th column (1 \leq i \leq N) from the left and j-th row (1
  \leq j \leq 10^9) from the bottom.
  
  Snuke has cut out some part of the grid so that, for each i = 1, 2, ..., N,
  the bottom-most h_i squares are remaining in the i-th column from the left.
  Now, he will paint the remaining squares in red and blue. Find the number of
  the ways to paint the squares so that the following condition is satisfied:
  
    * Every remaining square is painted either red or blue.
    * For all 1 \leq i \leq N-1 and 1 \leq j \leq min(h_i, h_{i+1})-1, there are exactly two squares painted red and two squares painted blue among the following four squares: (i, j), (i, j+1), (i+1, j) and (i+1, j+1).
  
  Since the number of ways can be extremely large, print the count modulo
  10^9+7.
samples: [{"input": "9\n    2 3 5 4 1 2 4 2 1", "output": "12800\n    \n\nOne of the ways to paint the squares is shown below:\n\n    \n    \n      #\n      ##  #\n     ###  #\n    #### ###\n    #########\n    \n\n* * *"}, {"input": "2\n    2 2", "output": "6\n    \n\nThere are six ways to paint the squares, as follows:\n\n    \n    \n    ## ## ## ## ## ##\n    ## ## ## ## ## ##\n    \n\n* * *"}, {"input": "5\n    2 1 2 1 2", "output": "256\n    \n\nEvery way to paint the squares satisfies the condition.\n\n* * *"}, {"input": "9\n    27 18 28 18 28 45 90 45 23", "output": "844733013\n    \n\nRemember to print the number of ways modulo 10^9 + 7."}]