RLTHREE - Robert Langdon & The Rule of Three
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 2N 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 (109+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
Added by: | Piyush Kumar |
Date: | 2014-01-25 |
Time limit: | 2s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | IIT Bombay Coding GC |