寻宝

侠盗 Hank 经过千难万险终于来到了恶人岛，为了拿到恶人岛的宝座去帮助穷人，Hank 先对恶人岛进行了侦查，发现恶人岛有一个迷阵，宝藏摆在了迷阵的深处。迷阵由 M×N 个方 格组成，有的方格内有可以发现 Hank 的守卫，而有的方格内则是安全。为了展现自己的实 力，Hank 决定不仅要拿走恶人岛的宝藏，还要给他们留一封信，告诉恶人自己有 g 种方法 找到宝藏。现在要求你来帮助他实现这个目标。 迷阵越大，守卫越多。

输入格式

输入有一组测试数据，以两个非零整数 N 和 M 开始，两者均不大于20。N表示迷阵行数, M表示迷阵列数。接下来有 N 行, 每行包含 M 个字符,不同字符分别代表不同含义:

1. ‘@’：Hank 所在的位置；
2. ‘.’：可以安全通行的方格；
3. ‘#’：有守卫的方格；
4. ‘*’：宝藏所在位置。

输出格式

一个整数 g,表示 Hank 有 g 种方法可以找到宝藏。如果他不可能找到宝藏, 则输出-1。

8 8
.@##...#
#....#.#
#.#.##..
..#.###.
#.#...#.
..###.#.
...#.*..
.#...###

4

9 6
.#..#. 
.#.*.# 
.####. 
..#... 
..#... 
..#... 
..#... 
#.@.## 
.#..#.

-1

数据范围

时间限制: 1000ms

内存限制: 256MB