This problem is derived from the previous problem, Problem 5. In this problem, we consider the set of all the binary square matrices of size $n\times n$, denoted by $\mathcal B_{n,n}$. Suppose $M\in\mathcal B_{n,n}$ and $P\in \mathcal B_{2,2}$, we define $mch(P,M)$ as the number of occurences of $P$ as blocks in $M$. If $mch(P,M)=0$, we say $M$ avoids $P$.
For example, $P=\begin{pmatrix}1&1\\1&1\end{pmatrix}\in \mathcal B_{2,2}$ and $M=\begin{pmatrix}0&0&1&1\\1&0&1&1\\1&1&1&1\\1&1&1&0\end{pmatrix}\in \mathcal B_{4,4}$.
We see $mch(P,M)=4$. Note that occurences could be overlapped. In this example, there are two occurences in the third and fourth column.
$a(n)$ is the number of elements in $\mathcal B_{n,n}$ avoiding $P=\begin{pmatrix}0&1\\1&1\end{pmatrix}$.
For example, $a(1)=2$, $a(2)=15$.
Find $a(n)$.