389. Strange Planet
Time limit per test: 0.25
second(s)
Memory limit: 262144
kilobytes
input: standard
output: standard
Once upon a time, there was an
ndimensional space. And there was a planet, quite a strange planet.
One of its strange features was its form —
ndimensional hypercube with unit length side. And there was
a strange town in each vertex of the planet. Territory of the planet was divided between three aggressive kingdoms.
But several towns preserved their independence — let's call them neutral. An
ith town was neutral if
d_{1}(
i)=d
_{2}(
i)=d
_{3}(
i),
where
d_{j}(
i) is the distance between
ith town and the capital of
jth kingdom. All distances are measured using Manhattan metrics,
because the planet was really strange. You should calculate amount of neutral towns in order to estimate trading potential of the planet.
Answer can be quite big, so output it modulo 10
^{9}+7.
Input
First three lines describe the positions of the capitals.
Each description is an
nbit string (
).
Output
You should output the amount of the neutral towns modulo 10
^{9}+7.
Example(s)
sample input

sample output

01
01
10

2

sample input

sample output

01
01
11

0
