← 返回题目列表

Codeforces · 498/E

E. 楼梯和线路

中文机器翻译题面 查看原题

网格上有一个数字,代表由 7 级台阶组成的楼梯。高度为 i 的楼梯的宽度是 wi 的平方。形式上,该图形是通过连续连接大小为 wi × i 的矩形而创建的,使得 wi 边位于一条直线上。因此,例如,如果所有 wi = 1,则图形将如下所示(不同颜色代表不同的矩形):

如果 w = {5, 1, 0, 3, 0, 0, 1},那么它看起来像这样:

找出为图形内部方块的某些边框着色的方法数量,以便没有方块的四个边框全部着色。位于图形边界上的正方形的边界应被视为已绘制。与图形旋转不同的方式应该被认为是不同的。

输入

单行输入包含 7 个数字 w1, w2, ..., w7 (0 ≤ wi ≤ 105)。保证至少有一个 wi 不等于 0。

输出

在输出的单行中显示一个数字 — 问题的答案以 109 + 7 为模。

示例

输入 #1

0 1 0 0 0 0 0

输出 #1

1

输入 #2

0 2 0 0 0 0 0

输出 #2

7

输入 #3

1 1 1 0 0 0 0

输出 #3

9

输入#4

5 1 0 3 0 0 1

输出#4

411199181

注意

下面给出了绘制第三个样本的所有可能方法: