题目描述

定义满足以下条件的多边形为好的：

• 多边形是凸的；
• 多边形的面积非零；
• 多边形中至多有 $8$ 条边；
• 多边形中，每条边要么平行于坐标轴，要么与坐标轴成 $45^{\circ}$ 角。
• 平行于坐标轴的边的长度为正整数；
• 与坐标轴成 $45^{\circ}$ 角的边的长度为 $\sqrt 2$ 的正整数倍。

下图给出了好的多边形的示例。

设想沿逆时针方向环绕整个多边形一圈，会发现多边形由若干条长度为 $1$ 或 $\sqrt 2$ 的线段拼成。根据遍历的方向我们将线段分成八类：北/东北/东/东南/南/西南/西/西北。

给定这八类线段最多能使用的数量，求出能够构造出多少种本质不同的好的多边形。只需要求出答案对 $(10^9+7)$ 取模后的结果。

本质不同定义为：如果不能通过平移让两个多边形重合，那么这两个多边形本质不同。换句话说，两个好的多边形相同，当且仅当它们使用的八类线段数量完全相同。

输入格式

一行八个非负整数，分别表示 北/东北/东/东南/南/西南/西/西北 这八类线段最多能使用的数量。

输出格式

输出一行一个非负整数，表示答案对 $(10^9+7)$ 取模后的结果。

1 0 1 0 1 0 1 0

1

1 1 1 1 1 1 1 1

19

2 2 2 2 2 2 2 2

228

1 2 3 4 4 3 2 1

135

100 100 100 100 100 100 100 100

636061137

提示

样例解释

• 样例 $1$ 解释：只有 $1\times 1$ 的方形是好的。
• 样例 $2$ 解释：有 $19$ 种好的多边形。

数据范围

对于 $100\%$ 的数据，保证输入的数是 $[0,10^9]$ 间的整数。

子任务 $0$ 为样例。

下表中，记 $N$ 为输入数的最大值。

子任务编号	$N\le$	特殊性质	得分
$1$	$10^9$	$\text{A}$	$9$
$2$	$100$		$17$
$3$	$2\times 10^3$		$29$
$4$	$2\times 10^5$
$5$	$10^9$		$16$

• 特殊性质 $\text{A}$：没有与坐标轴成 $45^{\circ}$ 角的线段。

请注意本题对于「本质不同」的定义。