### 问题描述 众所周知，威震华夏的武圣关云长拥有将红牌当杀的技能！除了武力过人之外，二爷在排兵布阵上也是颇有造诣。 现有规模为 $n×n$（$2 \leq n \leq 12$）的方阵地形，二爷需要在其上合理分配兵力来埋伏曹军。此地形上分布有树林点和空地点，树林点用 $1$ 表示，空地点用 $0$ 表示。现在二爷可以在此地形上埋伏军队，限制如下： 1. 军队不能埋伏在空地点上，只能埋伏在树林点上。 2. 任意两支军队的埋伏点不能相邻（交战时容易造成误判）。 二爷希望你能计算出所有埋伏方案的总数（包括根本不埋伏军队，故作疑兵），并对 $10^{8}$ 取模，最后输出。 ### 输入格式 第 $1$ 行一个整数 $n$，表示方阵的边长。 第 $2$ 到第 $n+1$ 行，每行包含 $n$ 个用空格隔开的整数，描述了每块土地的状态。第 $i+1$ 行描述了第 $i$ 行的土地，所有整数均为 $0$ 或 $1$，是 $1$ 的话，表示这个点是树林，可以埋伏军队，$0$ 则表示这个点是空地，不能埋伏军队。 ### 输出格式 一个整数，即埋伏军队总方案数除以 $10^{8}$ 的余数。 ### 样例输入 ```text 2 1 1 0 1 ``` ### 样例输出 ```text 5 ``` ### 说明 方案 $1$：左上角埋伏。 方案 $2$：右上角埋伏。 方案 $3$：右下角埋伏。 方案 $4$：左上角和右下角埋伏。 方案 $5$：不埋伏。 ### 评测数据规模 对于所有评测数据，$2 \leq n \leq 12$。