#hhkb2020e. [hhkb2020_e]Lamps

[hhkb2020_e]Lamps

有一个 n×mn \times m 的二维网格,ai,ja_{i, j} 表示网格的第 ii 行 第 jj 列,其中 . 表示空地,# 表示墙。

你可以在任意一个空地放置一个射灯,它会沿着上下左右四个方向照亮碰到墙壁之前的所有空地。

很显然的,假设一共有 kk 个空地,那么一共有 2k2^k 种放置射灯的方案,你需要统计每个方案中至少被一盏灯照到的空地个数,并求这个个数的总和。并将答案对 109+710^9+7 取模。