题目描述

果园被划分成 $n$ 行 $m$ 列的方格，其中少数格子立着石墩，过不去。除草机从左上角 $(1,1)$ 出发，每步走到上下左右相邻的一个没有石墩的格子，并且要求每个能走的格子恰好走一次，最后恰好停在右下角 $(n,m)$。

请你数一数这样的行驶路线一共有多少条。

输入格式

第一行两个整数 $n,m$。

接下来 $n$ 行，每行一个长度为 $m$ 的字符串，. 表示空地，# 表示石墩。

保证 $(1,1)$ 和 $(n,m)$ 都是空地。

输出格式

一行一个整数，表示路线条数。一条都没有时输出 0。

输入输出样例 #1

输入 #1

3 4
....
....
....

输出 #1

4

说明

数据范围

• 对于 $100\%$ 的数据，$1\le n,m\le 8$，$n\times m\le 30$，石墩不超过 $6$ 个。