“优美八边形”（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 | 9 | 没有可用的对角线段。 |
| 2 | 17 | $N \le 100$ |
| 3 | 29 | $N \le 2\,000$ |
| 4 | 29 | $N \le 200\,000$ |
| 5 | 16 | 无额外限制。 |
样例
样例输入 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 个优美八边形。