For Valentine's Day, Hanbyeol's chocolate shop is selling hexagonal chocolates topped with almonds. The interior angles of the hexagonal chocolate are all $120^\circ$, and the lengths of each side are integers. One almond is shaped like two equilateral triangles with side length $1$ joined together along an edge. The almonds must cover the chocolate completely without overlapping or extending beyond the boundaries of the chocolate.

To make the almond chocolate look attractive, Hanbyeol has already placed $6$ almonds such that each covers two triangles containing one of the vertices of the hexagon.

Find the number of ways to fill the remaining part of the chocolate.

Input

The first line contains $6$ integers $a_i$ representing the lengths of the sides of the hexagonal chocolate in clockwise order, separated by spaces. $(2 \le a_i \le 6;$ $1 \le i \le 6)$ The given input forms a valid hexagon.

Output

Output the answer to the problem modulo $1\,000\,000\,007$ on the first line. $1\,000\,000\,007$ is a prime number.

Examples

Input 1

2 2 2 2 2 2

Output 1

1

Note

In the example, there is only one way to fill the remaining space with almonds without any gaps, as shown in the figure below.