“优美八边形”（nice octagon）是一个面积非零的凸图形，其边数最多为 8 条，且每条边要么平行于坐标轴，要么与坐标轴成 $45^\circ$ 角。所有平行于坐标轴的边必须具有整数长度；所有其他边必须具有 $\sqrt{2}$ 的整数倍长度。下图展示了一些优美八边形的例子。

假设我们沿逆时针方向绕优美八边形的边行走。我们观察到它是由长度为 1 和 $\sqrt{2}$ 的线段组成的，这些线段连接了行走路径上相邻的两个网格点。因此，根据线段的方向，这些线段被分为 8 个不同的类别：北、东北、东、东南、南、西南、西和西北。

假设给定每种类别线段的最大可用数量，请问你能构成多少个不同的优美八边形？

输入格式

输入的第一行也是唯一一行包含 8 个用空格分隔的整数，分别表示北、东北、东、东南、南、西南、西和西北方向线段的最大数量。

输出格式

输出符合要求的优美八边形数量，对 $10^9 + 7$ 取模。

数据范围

• 令 $N$ 为输入中 8 个数值的最大值。
• $N \le 1\,000\,000\,000$
• 如果两个优美八边形可以通过平移（但不能通过旋转）相互得到，则认为它们是相同的。特别地，两个优美八边形相同，当且仅当它们在 8 种方向上使用的线段数量分别相同。

样例

样例输入 1

1 0 1 0 1 0 1 0

样例输出 1

1

样例输入 2

1 1 1 1 1 1 1 1

样例输出 2

19

样例输入 3

2 2 2 2 2 2 2 2

样例输出 3

228

样例输入 4

1 2 3 4 4 3 2 1

样例输出 4

135

样例输入 5

100 100 100 100 100 100 100 100

样例输出 5

636061137

说明

在第一个样例中，唯一的优美八边形是一个 $1 \times 1$ 的正方形。

在第二个样例中，共有 19 个优美八边形。