Welcome to ZOJ
74 - ZOJ Monthly, January 2009 - G
Street Lamp

Time Limit: 1 Second      Memory Limit: 32768 KB

there are N parallel streets, each with M street lamps, everyday when it's about to dawn, you'll have to turn all of them off, the problem is, the lamps are wired in a strange way and turning off one lamp could affect others lamps' on-off states! All the lamps of the same street are wired one by one, so turning on or off would make the lamp before it and after it change state (from on to off and vice versa), however, for the jth lamp of the ith street, it could also affect the states of the jth lamp of the i-1th street and the i+1th street, or perhaps it wouldn't. Given a state of the wirings of the street lamps, find how many ways there are to turn all the lamps off! Each switch of a lamp can be used at most once.


For each case,the first line containing 2 integers: 0 < N,M <=10. Then 2N-1 lines followed, describing the lamps and the wires between them. Each line is a street with m lamps, 'o' represent a lit lamp while '*' represent a lamp that already be turned off, '|' and '-' represent a wire that connecting two neighboring lamps.


For each case, output an integer in a single line repesent how many ways there are to turn all the lamps off!

Sample Input

2 2
2 2
| |
4 4
| | | |
| | | |
| | | |

Sample Output


Author: WANG, Yelei
Source: ZOJ Monthly, January 2009
Submit    Status