推了一晚上！和hyc一起萌萌哒地推絀来了！！

被摧残蹂躏的智商啊！！！

（请不要介意蒟蒻的内心独白。）

设a[i]为扫到第i行时的方案数

易知，对于一行1*4的格子只有一种方案把它铺满。

首先对于当前的第i行，如果它不和第i-1行有联系（也就是它是独立的一行）那么就有1*a[i-1]=a[i-1]种方案。

如果第i行和第i-1行有联系（2荇间互相联系）那么共有一下四种方案：

如果第i行、第i-1行、第i-2行都有联系（3行间两两联系），那么共有两种方案（此图以及的轴对称图形）：

如果第i行、第i-1行、第i-2行、第i-3行都有联系（4行间两两联系）那么共有三种方案（上面两种方案加下面一种）：

一直递推下去，我们鈳以发现：

该递推式可以转化为矩阵乘法：