
ZOJ Problem Set  3466
There is a hive in the village. Like this. There are 8 columns(from A to H) in this hive. Different colums have the same number of grids. Every grid has its own coordinate, which is formed by two uppercases, representing the row index and the column index. The row index starts from A. And the hive has less than ten rows in total. The following figure shows a hive with two rows. There is honey in some grids. A naughty bee discovers this special hive and hopes to eat all honey in the hive. However, this strange bee sets some rules for itself while eating. They are descirbed as following:
Given the hive and the honey in it, how many different ways can this naughty bee eat all honey in the hive? InputThere are multiple test cases. For each case, there are two integers N(0 < N ≤ 10) and M(0 ≤ M ≤ N * 8) in the first line. N represents the size of the hive, which means there are N rows in the hive in total. All grids have honey in it except for those M grids listed in the following line. Each empty grid is described by its coordinate(using two uppercases). OutputFor each case, output the number of different ways the bee can eat all honey in the hive. It's guaranteed that the answer does not exceed 2^{63}  1. Sample Input3 5 BB CD BF AH CG Sample Output3 HintThe following figure shows all different ways for the sample. The black grids represent those which are initially empty. Author: MO, Luyi Contest: ZOJ Monthly, January 2011 