A binary matrix is a matrix consisting entirely of s and s. Consider the following transformations that can be performed on a binary matrix:
- Swap any two rows
- Swap any two columns
- Flip all elements in a single row (s become s, s become s)
- Flip all elements in a single column
Two binary matrices and will be considered equivalent if there is a sequence of such transformations that when applied to yields . For example, the following two matrices are equivalent:
via the sequence of two transformations "Flip all elements in column 3" followed by "Swap rows 1 and 2".
Define to be the maximum number of binary matrices that can be found such that no two are equivalent. For example, . You are also given that and .
Find , and give your answer modulo .