AGC003F Fraction of Fractal

题意：给出一张 的黑白点阵。定义其为初始图。

定义 级分型为单独一个黑格。

定义 级分型：将初始图的每个黑格替换为 级分型，而将白格替换为纯白的，和 级分型同样大小的区域。

求 级分型中黑格形成的四联通块个数，答案对 取模。

保证 级分型中的黑格四连通。

，，时限 。

---

• 初始图上下连通，左右也连通。

  答案是 。

• 初始图上下不连通，左右也不连通。

  设 为初始图中的黑格个数，答案是 。

• 初始图仅上下连通或仅左右连通。

  考虑仅上下联通的情况，另一种情况只需翻转初始图。

  此时，只有上下两个相邻的初始图之间可能联通，以初始图为单元，边集为森林（若干条竖链）。

  于是，联通块个数等于点数减边数，即 上下相邻的初始图对数。

  记 为初始图中上下相邻的黑格对数， 为跨越上下边界的相邻的黑格对数。

  对于 级分型，记 为分型中上下相邻的初始图对数， 为跨越上下边界相邻的初始图对数， 为含有的初始图数目。

  则有如下递推关系：

  不难用矩阵快速幂加速计算。