题目描述 $n \times m$ 草地，某些格子被标记为禁牧（#）。在可放牧格子中选一些放牛，要求任意两头牛不相邻（上下左右）。求方案数对 $10^9$ 取模的结果（一头不放也算一种）。 输入格式 第一行两个整数 $n, m$；接下来 $n$ 行每行一个长度为 $m$ 的串（. 可放、# 禁）。 输出格式 一行一个整数。 数据范围 $$1 \le n \le 12,\ 1 \le m \le 12$$