Двоичная матрица - это матрица, состоящая исключительно из нулей и единиц. Рассмотрим следующие преобразования, которые можно выполнить над двоичной матрицей:

• Поменять местами любые два ряда
• Поменять местами любые два столбца
• Обратить все элементы одного ряда (1 становятся 0, а 0 становятся 1)
• Обратить все элементы одного столбца

Две бинарные матрицы $A$ и $B$ будем считать эквивалентными, если существует последовательность преобразований, которые при выполнении над $A$, дают в результате $B$. Например, следующие две матрицы эквивалентны:

$A=\begin{pmatrix} 1 & 0 & 1 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \\ \end{pmatrix} \quad B=\begin{pmatrix} 0 & 0 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \\ \end{pmatrix}$

через последовательность из двух преобразований "Обратить все элементы столбца 3" и "Поменять местами ряды 1 и 2".

Определим $c(n)$ как максимальное количество двоичных матриц $n\times n$, из которых никакие две не эквивалентны. Например, $c(3)=3$. Вам также дано, что $c(5)=39$ и $c(8)=656108$.

Найдите $c(20)$. В качестве ответа приведите остаток от деления полученного результата на $1\,001\,001\,011$.