It’s always hard to write original problems, right?
Given an integer and a grid, where the cell contains a number initially. The grid is considered to be a torus, that is, the cell to the right of is ,and the cell below the is . 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 , you can choose any x,y with and flip the number in the cell 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 .

The first line contains one integer .Each of the following  lines contains a binary string of length . A cell  is in the figure  if and only if the -th character in the -th line is .

Output one integer - the answer.

2
0101
0000
0101
0000

16