NC201928. Xor on Figures
描述
It’s always hard to write original problems, right?
Given an integer
and a 
grid, where the cell %7D)
contains a number 
initially. The grid is considered to be a torus, that is, the cell to the right of )
is %7D)
,and the cell below the )
is %7D)
. There is a lattice figure 
consisting of 
cells. Note that doesn’t have to be connected.
In each operation, we can place at some position on the grid (only translations are allowed, rotations and reflections are prohibited) and flip the number in each cell covered by . Here the number 
will be fliped to 
and vice versa.
More formally, let be the set of cells %2C(x_2%2Cy_2)%2C%5Cdots%2C(x_t%2Cy_t))
, you can choose any x,y with 
and flip the number in the cell %20%5Cbmod%202%5Ek)%2B1%2C((y%2By_i%E2%88%921)%20%5Cbmod%202%5Ek)%2B1))
for each 
.
Now we want to know how many patterns we can achieve with any number of operations from an all-zero board. Since the answer can be very large, you only need to output it modulo
.
Given an integer
In each operation, we can place
More formally, let
Now we want to know how many patterns we can achieve with any number of operations from an all-zero board. Since the answer can be very large, you only need to output it modulo
输入描述
The first line contains one integer.Each of the following
lines contains a binary string of length
-th character in the
-th line is
输出描述
Output one integer - the answer.
示例1
输入:
2 0101 0000 0101 0000
输出:
16