乌龟

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

给定一个 $n\times m$ 的网格，部分格子是障碍。两只乌龟都从 $(1,1)$ 出发，每步只能向右或向下走到非障碍格，并最终到达 $(n,m)$。

除起点和终点外，两条路径不得共用任何格子。求无序路径对的数量，答案对 $10^9+7$ 取模。

输入格式

第一行两个整数 $n,m$。接下来 $n$ 行，每行一个长度为 $m$ 的字符串：. 表示可通行，# 表示障碍。保证 $(1,1)$ 和 $(n,m)$ 可通行。

输出格式

输出一行一个整数，表示答案。

样例输入 1

4 5
.....
.###.
.###.
.....

样例输出 1

1

数据范围

• $2\le n,m\le3000$。

计分方式

本题按测试点独立计分，同子任务内测试点等分。