Skip to content

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了,可以的话,请您参考添加页面,与大家一起分享你的题解!