Counting Good Polygons

Define a polygon as good if it satisfies all of the following conditions:

• The polygon is convex.
• The polygon has a nonzero area.
• The polygon has at most $8$ sides.
• Every edge is either parallel to the coordinate axes or makes a $45^\circ$ angle with them.
• An axis‐parallel edge has a positive integer length, and an edge at $45^\circ$ has a length that is a positive integer multiple of $\sqrt{2}$.

If one traverses the boundary of a good polygon in a counterclockwise direction, the boundary can be decomposed into several segments of length $1$ or $\sqrt{2}$. These segments are classified into eight types according to their direction: North, Northeast, East, Southeast, South, Southwest, West, and Northwest.

Given eight nonnegative integers representing the maximum allowed number of segments for each corresponding direction (in the order given above), count the number of essentially different good polygons that can be constructed. Two good polygons are considered essentially identical if one can be translated to coincide with the other – that is, if they use exactly the same number of segments for each of the eight directions.

Output the answer modulo $(10^9+7)$.

inputFormat

The input consists of a single line containing eight nonnegative integers. The numbers represent the maximum allowed usage for the segments in the following order: North, Northeast, East, Southeast, South, Southwest, West, and Northwest.

outputFormat

Output a single integer – the number of essentially different good polygons that can be constructed, taken modulo $(10^9+7)$.

sample

1 0 1 0 1 0 1 0

1