AT_code_festival_china_g Ammunition Dumps

在一个大小为 $R \times C$ 的二维网格里，某些格子上放置了炸药仓库。 仓库一旦着火，过一段时间后就会爆炸。当一个仓库爆炸时，火焰会像“+”字形扩散，直到遇到其他仓库为止。火焰无法穿过这些仓库到达后面的格子。 被火焰波及的仓库可能会被点燃，也可能不会。如果一个仓库被火焰波及但没有立刻着火，它仍可能在另一次波及中起火。 一旦某个仓库爆炸，它不会再被点燃，但仍会阻挡火焰的传播。 最开始，你在其中一个炸药仓库上点燃火焰，最终所有仓库都会爆炸。 在这个过程中，任意两个仓库不会同时爆炸（尽管它们可能会同时着火）。 请计算所有仓库爆炸的可能方案数量，并输出结果对 $1000000009(10^9+9)$ 取模后的值。 每种爆炸方案可以用一组仓库对来表示，其中每对代表一个仓库是如何被另一个仓库引燃的。如果两种方案中至少有一对仓库不同，则这两种方案被视为不同的。

输入格式如下： > $R$ $C$ $s_{(1,1)}$$s_{(1,2)}$ .. $s_{(1,C)}$ $s_{(2,1)}$$s_{(2,2)}$ .. $s_{(2,C)}$ : $s_{(R,1)}$$s_{(R,2)}$ .. $s_{(R,C)}$ $a$ $b$ - 第一行包含两个整数 $R, C\ (1 \leq R, C \leq 16)$，表示网格的行数和列数。 - 接下来的 $R$ 行描述了仓库的位置。每一行是一个长度为 $C$ 的字符串，由 `.` 和 `W` 组成。第 $i$ 行第 $j$ 列的字符表示位于 $(i,j)$ 的格子。字符 `.` 表示空格，`W` 表示仓库。 - 最后一行包含两个整数 $a, b\ (1 \leq a \leq R, 1 \leq b \leq C)$，这是你最初点燃的仓库的位置。确保这个位置有一个仓库。 - 至少有一个仓库。

请输出一行，表示所有仓库可能爆炸方案的数量，并对 $1000000009$ 取模。输出末尾需要有一个换行符。 ### 示例 ``` 242986351 ``` 请不要忘记将结果对 $1,000,000,009$ 进行取模。 ### 例子解释 在示例中，其中有一种爆炸方式如下图所示。总共有 $4$ 种可能的爆炸方案。在这种方案中，位于 $(1,3)$ 和 $(3,1)$ 的仓库由位于 $(1,1)$ 的仓库引燃，而位于 $(3,3)$ 的仓库是由 $(3,1)$ 的仓库引燃的。 ### 例子 在某些情况下，并不是所有的仓库都能最终爆炸。 **本翻译由 AI 自动生成**

### Problem There is a $ 2 $-dimensional grid of size $ R\ \times\ C $. There are many explosives warehouses on some of the cells. When a warehouse catches fire, it finally explodes at some time in the future. When a warehouse explodes, it blasts in a $ + $ shape with fire extending on all four side. Blast fire extends until it reaches other warehouse. Blast fire won't reach the cells behind those warehouses. A warehouse exposed to blast fire may catch fire or may not catch fire. A warehouse that once exposed to blast fire but didn't catch fire then, can be exposed to another blast fire. In that case, it's same as before, the warehouse may catch fire or may not catch fire. An exploded warehouse won't catch fire anymore but still blocks the blast fire. At first, you lit fire on one explosives warehouse. Finally, all warehouses had exploded. During that disaster, no warehouses exploded at the same time. (Some of the warehouses could have caught fire at the same time.) Calculate the number of possible ways of exploding that all warehouses explodes. As the answer can be rather large, print it as a remainder after dividing it by number $ 1000000009(10^9+9) $. Ways of exploding is a set of pairs of warehouses. Each pair is a warehouse which caught fire and the warehouse which put fire on the former warehouse by exploding. When two ways of exploding have at least one different pair of warehouses, they are distinct. ### Ouput Example 4 ``` 242986351 ``` Don't forget to output the remainder after dividing the number by $ 1,000,000,009 $. ### Sample Explanation 1 For example, there is one way of exploding like below. Including this way, there are $ 4 $ ways of exploding. !\[\](/img/other/code\_festival\_2014\_china/G\_sample1.png) In this way, the warehouses at $ (1,3) $ and $ (3,1) $ caught fire from warehouse at $ (1,1) $, and the warehouse at $ (3,3) $ caught fire from warehouse of $ (3,1) $ ### Sample Explanation 2 Not all warehouses can explode in this case.