You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

时间限制：2s 空间限制：256M

描述

给定一个迷宫。在迷宫中有一些障碍物无法通过，请计算出从左上角到右下角的移动方案总数。（一个位置不能经过两次，只能上下左右四个方向走）

输入格式

第一行包含两个整数 $n,m$ ，表示迷宫的大小。

接下来的n行，每行包含m个字符，代表迷宫。

＃代表障碍

*代表你可以去的位置

左上角和右下角用“*”表示

输出格式

一个整数。

样例1输入

5 6
*****#
*###*#
*###*#
*###*#
******

样例1输出

2

样例2输入

6 6
******
******
******
******
******
******

样例2输出

1262816

数据范围与提示

$1\le n,m \le 6$