{"problem":{"name":"Histogram Coloring","description":{"content":"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 b","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc026_d"},"statements":[{"statement_type":"Markdown","content":"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.\nSnuke 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:\n\n*   Every remaining square is painted either red or blue.\n*   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)$.\n\nSince the number of ways can be extremely large, print the count modulo $10^9+7$.\n\n## Constraints\n\n*   $1 \\leq N \\leq 100$\n*   $1 \\leq h_i \\leq 10^9$\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$h_1$ $h_2$ $...$ $h_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc026_d","tags":[],"sample_group":[["9\n2 3 5 4 1 2 4 2 1","12800\n\nOne of the ways to paint the squares is shown below:\n\n  #\n  ##  #\n ###  #\n#### ###\n#########"],["2\n2 2","6\n\nThere are six ways to paint the squares, as follows:\n\n## ## ## ## ## ##\n## ## ## ## ## ##"],["5\n2 1 2 1 2","256\n\nEvery way to paint the squares satisfies the condition."],["9\n27 18 28 18 28 45 90 45 23","844733013\n\nRemember to print the number of ways modulo $10^9 + 7$."]],"created_at":"2026-03-03 11:01:13"}}