Implementation with bitwise operations on arbitrary-precision integers is easier.

(Hint)

• Receive the input as binary integers (“#” represents 1, “.” represents 0)
• As the input is two-dimensional, you may think we have multiple binary integers, but
• Vertical movement can also be represented by bit shift operations, e.g., one vertical movement is equivalent to multiplying by \(2^{20}\)
• The overlapping rule corresponds to the bitwise OR operation
• Translating (both horizontally and vertically) corresponds to bit shift operations
• Coincidence can be easily checked by removing trailing zeroes
• To obtain a number after removing trailing zeroes, you can use a // (a & -a)

AC Code（PyPy 3）