Many people know that when we think deeply about something, it even begins to show up in our dreams. Much like the story of structure of carbon attributed to Kekule. The rule of three has haunted Robert for weeks now, and has crept into his subconscious.

Robert finds himself in an N dimensional space, on a cube land of N dimensions and side 1 unit. The land is haunted by the mythological hounds Gwyllgi, three of them. Each of the 2^N vertices of the cube land is hunting ground of one of the three Gwyllgi, except those vertices that are equidistant from all three. These neutral grounds are the only places where Langdon can stand on the cube. Help Langdon find these safe grounds while he thinks of his next move to escape the cube land.

Note that the distances are Manhattan distances, the smallest distance that you need to cover if movement is restricted parallel to one of the axis. Eg, distance between (0,0,0,0) and (1,0,1,1) is 3.

Input

Input consists of three lines, each line has a binary string of equal length (=N).

Each string represents coordinates of a Gwyllgi in the N dimensional space, 0 meaning coordinate 0 and 1 meaning coordinate 1.

Eg : if the input is

001
111
101

It means that in the 3D space, first Gwyllgi is at coordinate (0, 0, 1), second one at (1, 1, 1) and third one at (1, 0, 1)

Output

Output a single line containing number of vertices of the cube land that are safe. Since the number can be large, output the value modulo 1000000007 (10⁹+7)

EXAMPLE

Input
111
001
100

Output
2

Explanation

Points (1, 0, 1) and (0, 1, 0) are equidistant from the three points.

Constraints

2<=N<=100000