网格上有一个数字,代表由 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
注意
下面给出了绘制第三个样本的所有可能方法: