14226: 【原4226】积木大赛

题目

题目描述

author: Mark Douglas 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4226

Description

Mark 喜欢玩积木。

Mark 是纸片人，所以他的积木可以看做二维平面上的格子。积木共有 \(N\) 列，左起第 \(i\) 列的高度为 \(h_i\)。现在 Mark 要对这些积木进行染色，染色需满足以下两条规则。

• 积木只能被染成红色或蓝色。
• 任意一个 \(2 \times 2\) 的子矩形中必须恰好有 2 个红色、2 个蓝色的积木，不足 \(2 \times 2\)的部分无限制。

Mark 想知道有多少种合法的染色方案，由于答案很大，你只需要告诉他答案对 \(10^9 + 7\) 取模后的结果。

Input Format

输入共\(2\)行

第一行一个整数\(N\)，表示积木的列数

接下来一行，共\(N\)个整数，第\(i\)个整数代表第\(i\)列积木的高度

Output Format

输出一个整数，代表答案对 \(10^9 + 7\) 取模后的结果。

Sample Input

6
1 1 4 5 1 4

Sample Output

4608

Limits

对于\(30 \% \)的数据，\(1 \leq N \leq 5, 1 \leq h_i \leq 4\)

对于\(60 \% \)的数据，\(1 \leq N \leq 100, 1 \leq h_i \leq 10^9\)

对于\(100 \% \)的数据，\(1 \leq N \leq 100000, 1 \leq h_i \leq 10^9\)

Oops! 本题目还没有解答！

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！